Algorithm - Python - メモリは役に立つ(硬貨列問題、辞書の作成と検索、例外、再帰探索でのメモ化)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の18章(メモリは役に立つ)、練習問題(パズル問題2)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
def coins(row: list, table: dict) -> (int, dict):
    '''
    >>> coins([14, 3, 27, 4, 5, 15, 1], {})
    (61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
    '''
    if len(row) == 0:
        table[0] = (0, 1)
        return 0, table
    if len(row) == 1:
        table[1] = (row[0], 2)
        return row[0], table
    skip = coins(row[1:], table)[0]
    pick_skip = coins(row[2:], table)[0] + row[0]
    pick_pick = coins(row[4:], table)[0] + row[0] + row[1]
    if skip >= pick_skip and skip >= pick_pick:
        result = skip
        table[len(row)] = (result, 1)
    elif pick_skip >= skip and pick_skip >= pick_pick:
        result = pick_skip
        table[len(row)] = (result, 2)
    else:
        result = pick_pick
        table[len(row)] = (result, 3)
    return result, table


def coins_memo(row: list, memo: dict) -> (int, dict):
    '''
    >>> coins([14, 3, 27, 4, 5, 15, 1], {})
    (61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
    '''
    if len(row) == 0:
        memo[0] = (0, 1)
        return 0, memo
    if len(row) == 1:
        memo[1] = (row[0], 1)
        return row[0], memo
    if len(row) in memo:
        return memo[len(row)][0], memo
    skip = coins_memo(row[1:], memo)[0]
    pick_skip = coins_memo(row[2:], memo)[0] + row[0]
    pick_pick = coins_memo(row[4:], memo)[0] + row[0] + row[1]
    if skip >= pick_skip and skip >= pick_pick:
        result = skip
        memo[len(row)] = (result, 1)
    elif pick_skip >= skip and pick_skip >= pick_pick:
        result = pick_pick
        memo[len(row)] = (result, 2)
    else:
        result = pick_pick
        memo[len(row)] = (result, 3)
    return result, memo


if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample2.py -v
Trying:
    coins([14, 3, 27, 4, 5, 15, 1], {})
Expecting:
    (61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
ok
Trying:
    coins([14, 3, 27, 4, 5, 15, 1], {})
Expecting:
    (61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
ok
1 items had no tests:
    __main__
2 items passed all tests:
   1 tests in __main__.coins
   1 tests in __main__.coins_memo
2 tests in 3 items.
2 passed and 0 failed.
Test passed.
$