Python 3.3 vs. MSDOS Basic
Tim Daneliuk
tundra at tundraware.com
Wed Feb 20 09:21:54 EST 2013
On 02/19/2013 12:31 PM, Ian Kelly wrote:
> On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra at 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
More information about the Python-list
mailing list