「オフラインリアルタイムどう書くF06の問題」の解答

「オフラインリアルタイムどう書くF06の問題 - ツリーの中の数」の解答
http://nabetani.sakura.ne.jp/hena/ordf06numit/

会場では残り20分ぐらいのときに出来上がりましたが、
「メモ化」というテクニックを知らず非常に効率の悪いもので、実行終了まで十数分要するものでした。

以下は、会場で得た新しいスキル「メモ化」を適用後のコード。
一瞬で終わるようになりました。

その他に以下を実施しています。

• 再帰処理の見直し
• グローバル変数廃止
• '/'を'//'に置き換え

main.py

def right_func(input_num):
    return input_num // 2 - 10

def left_func(input_num):
    return input_num * 2 // 3

def calc(memo, input_num, target):
    if input_num in memo:
        return memo[input_num]

    if input_num < target:
        return 0

    if input_num == target:
        return 1

    ans = calc(memo, right_func(input_num), target) + calc(memo, left_func(input_num), target)
    memo[input_num] = ans
    return ans

def resolve(data):
    memo = {}
    split = data.split(",")

    input_num = int(split[0])
    target = int(split[1])

    return str(calc(memo, input_num, target))


## test logic
class Result:
    def __init__(self):
        self.success = 0
        self.fail = 0

RESULT = Result()
RESULT.success = RESULT.fail = 0

def test(data, expect):
    print("actual:" + resolve(data) + " expected:" + expect)
    if resolve(data) == expect:
        RESULT.success += 1
    else:
        RESULT.fail += 1


test( "123,4", "5" )
test( "1,1", "1" )
test( "2,1", "1" )
test( "3,3", "1" )
test( "19,5", "1" )
test( "69,5", "3" )
test( "88,9", "2" )
test( "1,100", "0" )
test( "100,4", "4" )
test( "101,9", "0" )
test( "456,7", "7" )
test( "567,8", "12" )
test( "756,10", "10" )
test( "789,10", "12" )
test( "896,29", "2" )
test( "7764,6", "664" )
test( "1234,56", "3" )
test( "8563,29", "35" )    
test( "12345,67", "10" )    
test( "72927,51", "263" )    
test( "71441,145", "22" )    
test( "123456,78", "397" )    
test( "123456,789", "1" )    
test( "592741,216", "55" )    
test( "913826,584", "81" )    
test( "1234567,89", "2293" )    
test( "10000000,1", "19383507" )    
test( "12345678,9", "3567354" )    
test( "6215879,358", "2907" )    
test( "12345678,90", "79419" )    
test( "5745432,1032", "1287" )

print("Success: {0.success}, Fail: {0.fail}".format(RESULT))