Optimizing Code for Project Euler Problem 14

Question

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()

Answer 1

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.