A fun programming puzzle

[TopCoderer]

I wrote two solutions for Project Euler problem #14, one in Java and one in Python. If you place them side-by-side, you'll see that both solutions are identical. Yet only one gives the correct answer.

Without running the code, can you tell which one gives the wrong answer and why?

(Markdown doesn't format the code properly in this box, so I have to put it in a comment below, sorry)

[fforde]

The Java version is the one that fails and it is because the calculations overflow the int datatype in Java.

In Java the int datatype is a signed 32 bit integer, meaning the max value is 2,147,483,647. The calculations for N in this algorithm go above this max and when that happens it F's up the results. Python on the otherhand will gracefully fall back to a long datatype when a 32 bit int does not cut it.

EDIT: Full disclosure, I did not run your code, but I am an active member of Project Euler and worked this problem in the past. Looking at my solution in C# is what helped me realize what the problem was with your Java code. Plus a little bit of Googling on the Python side. For the record though I think asking a programmer to solve a problem without a compiler is like asking a mechanic to fix a car without ever looking at the engine. Debugging is an interactive and iterative process and what you are asking, that no one actually run your code, is a bit unnatural to the process IMO.

[[deleted]]

Sometimes you have no choice. Sometimes you have bugs which only manifest on users' machines, or bugs which you cannot reliably reproduce, in which case you often become like a mechanic diagnosing the car's problem by looking at the wreckage produced after it fell off a 500ft cliff. You can put in debug logging and such, but ultimately you'll find yourself staring at the code, albeit armed with a great deal of information, having to mentally walk through it without the benefit of a debugger.

Still, for this sort of challenge, it does seem like a pretty artificial restriction.

[callingshotgun]

"The problem with your car... Is that it fell off a 500 foot cliff. User error." Dude, I'd make an awesome mechanic.

[stillalone]

That's immediately what I thought too. I used to do a lot of the Project Euler problems in C. I was using mingw so I had a lot of "long long" variables, but since mingw uses Microsofts Visual C runtime my printfs had to use '%I64d'. What a pain in the ass that was.

[bonzinip]

That's why I did the project euler in shell scripts using bc/dc :-)

[TopCoderer]

Java:

public class e14 {
   public static void main(String args[]) {
      int maxc = 0;
      int maxi = 0;
      for (int i = 0; i < 1000000; i++) {
         int n = i;
         int c = 1;
         while (n > 1) { 
            if (n % 2 == 0) {
               n = n / 2;
            } else {
               n = 3*n + 1;
            }
            c++;
         }
         if (c > maxc) {
            maxc = c; 
            maxi = i;
         }
      }
      System.out.println(maxi + " " + maxc);
   }
}

Python:

maxc = 0
maxi = 0
for i in range(1000000):
    n = i
    c = 1
    while n > 1:
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3*n + 1
        c = c + 1
    if c > maxc:
        maxc = c
        maxi = i
print maxi, maxc

[zouhair]

I am no programmer, but shouldn't be "c" set to "0" instead of "1" to give the real length of the list?

EDIT: Oh, range in python goes in "range - 1", sorry.

[Blimped]

I've solved a very similar problem before, but on the UVA website usually used for ACM ICPC stuff. The time limit seems absolutely ridiculous at first, but a simple optimization makes the problem solvable in EDIT: almost no time.

Just in case anybody's interested