# Optimizing Code for Project Euler Problem 14

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

-

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.

-

A bit faster version:

d:\python27\python test.py
(837799, 525)
10.3589999676

d:\python27\python test1.py
Index 837799, max value = 525, time 1.078000

using psyco:
d:\python25\python test1.py
Index 837799, max value = 525, time 0.078000


-

import time

try:
import psyco
psyco.full()
except:
pass

SIZE = 1000000
d = [0]*SIZE
d[1] = 1

def calc(n):
if n < SIZE:
if d[n]: return d[n]
if n & 1:
d[n] = 1 + calc(n + (n << 1) + 1)
return d[n]
d[n] = 1 + calc(n >> 1)
return d[n]
if n & 1:
return 1 + calc(n + (n << 1) + 1)
return 1 + calc(n >> 1)

def main():
stime = time.time()
mi = 1
mv = 1
for i in xrange(2,SIZE):
v = calc(i)
if v > mv:
mv = v
mi = i
print('Index %d, max value = %d, time %f' % (mi, mv, time.time()-stime))

if __name__ == '__main__':
main()


PS. I would suggest you to solve the similar SPOJ problem: http://www.spoj.pl/problems/PROBTNPO/

-

The following may take as much time as your code, but its length has been considerably shortened.

def main():
pool, used = set(range(2, 1000000)), {1: 1}
while pool:
number = pool.pop()
values = reversed(tuple(collatz_generator(number, used)))
length = dict(map(reversed, enumerate(values, used[next(values)] + 1)))
pool -= frozenset(length)
used.update(length)
table = dict(map(reversed, used.items()))
print(table[max(table)])

def collatz_generator(number, used):
while True:
yield number
if number in used:
break
number = 3 * number + 1 if number & 1 else number >> 1

if __name__ == '__main__':
main()

-