Python 3.3 vs. MSDOS Basic

Tim Daneliuk tundra at tundraware.com
Wed Feb 20 15:21:54 CET 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