Project euler #14 メモ化

3日に1記事挫折しそうやばいやばい

今回はProject eulerを題材にメモ化について書きます。

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. 
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

nが偶数:n = 3n + 1
nが奇数:n = n/2
を繰り返して、nが1になるまでのステップが最大になるnは何か、（n <= 1000000）
という問題。

単純に書くと

max = 0
n = 0
upper = 1000000

def length(n):
    if n == 1:
        return 1
    elif n%2 == 0:
        return 1 + length(n >> 1) #n/2のシフト演算版
    else:
        return 1 + length(3*n+1)

for i in range(1, upper):
    step = length(i)
    if step > max:
        max = step
        n = i

こんなバカ正直に書くと、僕の環境では計算終了まで３０秒弱もかかります。
おそスギィ！！！！

メモ化手法

問題文に

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

とあるように、
n=13なら10ステップ、n=40なら9ステップ、n=20なら・・・と解が続いていきますね、

例としてあげたコードのように、1から総当たりで解を探していく場合、
n=5ならば6ステップという解が出ているのに、n=10の場合に、

10 → 5 → 16 → 8 → 4 → 2 → 1

のように計算し続けてステップ数を数えるのは非効率です。
そこで、n=5ならば6ステップという解をどこかに補完しておけば、

10 → 5

のように、1回の計算だけで「n=10ならば7ステップ」という解が出せます。

実装

（この場合は）実装は単純です。

memo = {}
max = 0
n = 0
upper = 1000000

def length(n):
    if n in memo:
        return memo[n]#メモにnの値が記録されていたらそのvalueを返す
    if n == 1:
        return 1
    elif n%2 == 0:
        return 1 + length(n >> 1)
    else:
        return 1 + length(3*n+1)

for i in range(1, upper):
    step = length(i)
    if step > max:
        max = step
        n = i
    memo[i] = step#メモにステップ数を記録

これだけ！

これを実行すると3秒切ります。

これだけで1/10も速くなるなんてすごい！

ー終ー