Advertisement
mhrivnak

Project Euler 14

Dec 15th, 2012
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.87 KB | None | 0 0
  1. #!/usr/bin/env python
  2.  
  3. # key is starting number, value is total hops
  4. cache = {}
  5.  
  6. def solve(n):
  7.     # key is total, value is starting number
  8.     winner = 0
  9.     winning_count = 0
  10.     for x in xrange(1,n):
  11.         count = get_seq_length(x)
  12.         if count > winning_count:
  13.             winner = x
  14.             winning_count = count
  15.     return winner
  16.  
  17. def get_seq_length(start):
  18.     count = 1
  19.     count_values = {}
  20.     value = start
  21.     while value > 1:
  22.         if value in cache:
  23.             count += (cache[value] - 1)
  24.             break
  25.         elif value % 2 == 0:
  26.             value = value / 2
  27.             count += 1
  28.         else:
  29.             count_values[count] = value
  30.             value = value * 3 + 1
  31.             count += 1
  32.  
  33.     for x in count_values:
  34.         cache[count_values[x]] = count - x + 1
  35.     return count
  36.    
  37. print solve(1000000)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement