Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For Project Euler problem 14 I wrote code that runs for longer than a minute to give the answer. After I studied about memoization, I wrote this code which runs for nearly 10 seconds on Cpython and nearly 3 seconds on PyPy. Can anyone suggest some optimization tips?

import time
d={}
c=0
def main():
    global c
    t=time.time()
    for x in range(2,1000000):
        c=0
        do(x,x)
    k=max(d.values())
    for a,b in d.items():
        if b==k:
            print(a,b)
            break

    print(time.time()-t)

def do(num,rnum):
    global d
    global c
    c+=1
    try:
        c+=d[num]-1
        d[rnum]=c
        return
    except:
        if num==1:
            d[rnum]=c
            return
        if num%2==0:
            num=num/2
            do(num,rnum)
        else:
            num=3*num+1
            do(num,rnum)

if __name__ == '__main__':
    main()
share|improve this question
up vote 4 down vote accepted

I think you're over complicating your solution, my approach would be something along these lines:

def recursive_collatz(n):
        if n in collatz_map:
                return collatz_map[n]
        if n % 2 == 0:
                x = 1 + recursive_collatz(int(n/2))
        else:
                x = 1 + recursive_collatz(int(3*n+1))
        collatz_map[n] = x
        return x

Basically define a memoization map (collatz_map), initialized to {1:1}, and use it to save each calculated value, if it's been seen before, simply return.

Then you just have to iterate from 1 to 1000000 and store two values, the largest Collatz value you've seen so far, and the number that gave you that value.

Something like:

largest_so_far = 1
highest = 0
for i in range(1,1000000):
    temp = recursive_collatz(i)
    if temp > largest_so_far:
        highest = i
        largest_so_far = temp

Using this approach I got:

Problem 14's answer is: 837799. Took 1.70620799065 seconds to calculate.

share|improve this answer

protected by Jamal May 1 at 4:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.