On 02/19/2013 12:31 PM, Ian Kelly wrote:
On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tun...@tundraware.com> wrote:
Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...
Very well:
def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]
def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
run_collatz(1000000)
(837799, 524)
It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
Thanks. I was specifically curious about your use of dynamic programming.
What about this algorithm makes it particularly an example of this? Is
it your use of memoization or something other than this?
--
-----------------------------------------------------------------------
Tim Daneliuk
--
http://mail.python.org/mailman/listinfo/python-list
