Algorithm - Python - 偽造硬貨を探す(2枚の偽造硬貨、リストスライス、ケース分析、分割統治法)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の6章(偽造硬貨を探す)、練習問題(パズル問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def compare(group_a: list, group_b: list) -> str:
    if sum(group_a) > sum(group_b):
        return 'left'
    if sum(group_a) < sum(group_b):
        return 'right'
    return 'equal'


def split_coins(coin_list: list) -> list:
    index = len(coin_list) // 3
    return [coin_list[index * i:index * (i + 1)] for i in range(3)]


def find_fake_group(group1: list, group2: list, group3: list) -> list:
    result1_2 = compare(group1, group2)
    if result1_2 == 'left':
        return group1
    if result1_2 == 'right':
        return group2
    result1_3 = compare(group1, group3)
    if result1_3 == 'left':
        return group1
    return group3


def coin_comparison(coin_list: list) -> None:
    '''
    >>> coin_comparison([1, 1, 0])
    The fake coin is coin 1 in the original list
    >>> coin_comparison([1, 0, 1])
    The fake coin is coin 1 in the original list
    >>> coin_comparison([0, 1, 1])
    The fake coin is coin 2 in the original list
    >>> coin_comparison([1] + [0] * 8 + [1] + [0] * 8 + [0] * 9)
    The fake coin is coin 1 in the original list
    >>> coin_comparison([1] + [0] * 8 + [0] * 9 + [1] + [0] * 8)
    The fake coin is coin 1 in the original list
    >>> coin_comparison([0] * 9 + [1] + [0] * 8 + [1] + [0] * 8)
    The fake coin is coin 10 in the original list
    >>> coin_comparison([0] * 8 + [1] + [0] * 8 + [1] + [0] * 9)
    The fake coin is coin 9 in the original list
    >>> coin_comparison([0] * 8 + [1] + [0] * 9 + [0] * 8 + [1])
    The fake coin is coin 9 in the original list
    >>> coin_comparison([0] * 9 + [0] * 8 + [1] + [0] * 8 + [1])
    The fake coin is coin 18 in the original list
    >>> coin_comparison([1] + [0] * 8 + [0] * 9 + [0] * 8 + [1])
    The fake coin is coin 1 in the original list
    '''
    current_list = coin_list
    while len(current_list) > 1:
        group1, group2, group3 = split_coins(current_list)
        current_list = find_fake_group(group1, group2, group3)
    fake = current_list[0]
    print(f'The fake coin is coin {coin_list.index(fake) + 1} '
          'in the original list')


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

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

$ ./sample3.py -v
Trying:
    coin_comparison([1, 1, 0])
Expecting:
    The fake coin is coin 1 in the original list
ok
Trying:
    coin_comparison([1, 0, 1])
Expecting:
    The fake coin is coin 1 in the original list
ok
Trying:
    coin_comparison([0, 1, 1])
Expecting:
    The fake coin is coin 2 in the original list
ok
Trying:
    coin_comparison([1] + [0] * 8 + [1] + [0] * 8 + [0] * 9)
Expecting:
    The fake coin is coin 1 in the original list
ok
Trying:
    coin_comparison([1] + [0] * 8 + [0] * 9 + [1] + [0] * 8)
Expecting:
    The fake coin is coin 1 in the original list
ok
Trying:
    coin_comparison([0] * 9 + [1] + [0] * 8 + [1] + [0] * 8)
Expecting:
    The fake coin is coin 10 in the original list
ok
Trying:
    coin_comparison([0] * 8 + [1] + [0] * 8 + [1] + [0] * 9)
Expecting:
    The fake coin is coin 9 in the original list
ok
Trying:
    coin_comparison([0] * 8 + [1] + [0] * 9 + [0] * 8 + [1])
Expecting:
    The fake coin is coin 9 in the original list
ok
Trying:
    coin_comparison([0] * 9 + [0] * 8 + [1] + [0] * 8 + [1])
Expecting:
    The fake coin is coin 18 in the original list
ok
Trying:
    coin_comparison([1] + [0] * 8 + [0] * 9 + [0] * 8 + [1])
Expecting:
    The fake coin is coin 1 in the original list
ok
4 items had no tests:
    __main__
    __main__.compare
    __main__.find_fake_group
    __main__.split_coins
1 items passed all tests:
  10 tests in __main__.coin_comparison
10 tests in 5 items.
10 passed and 0 failed.
Test passed.
$