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

コード(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_type(group1: list,
                         group2: list,
                         group3: list) -> (list, str):
    result1_2 = compare(group1, group2)
    result1_3 = compare(group1, group3)
    if result1_2 == 'left':
        if result1_3 == 'left':
            return group1, 'heavier'
        return group2, 'lighter'
    if result1_2 == 'right':
        if result1_3 == 'equal':
            return group2, 'heavier'
        return group1, 'lighter'
    if result1_3 == 'left':
        return group3, 'lighter'
    if result1_3 == 'right':
        return group3, 'heaiver'
    return None, 'equal'


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


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


def coin_comparison(coin_list: list) -> (int, int):
    '''
    >>> coin_comparison([10] * 6 + [11] + [10] * 20)
    (7, 4)
    >>> coin_comparison([10] * 27)
    (-1, 2)
    >>> coin_comparison([0, 0, 0])
    (-1, 2)
    >>> coin_comparison([1, 0, 0])
    (1, 2)
    >>> coin_comparison([0, 1, 0])
    (2, 2)
    >>> coin_comparison([0, 0, 1])
    (3, 2)
    >>> coin_comparison([0, 1, 1])
    (1, 2)
    >>> coin_comparison([1, 0, 1])
    (2, 2)
    >>> coin_comparison([1, 1, 0])
    (3, 2)
    '''
    current_list, group_type = find_fake_group_type(*split_coins(coin_list))
    counter = 2
    if group_type == 'equal':
        # print('no fake coin')
        # print(f'Number of weighngs: {counter}')
        return -1, counter
    if group_type == 'heavier':
        find_fake_group = find_fake_group_heavier
    else:
        find_fake_group = find_fake_group_lighter
    while len(current_list) > 1:
        group1, group2, group3 = split_coins(current_list)
        current_list = find_fake_group(group1, group2, group3)
        counter += 1
    fake = current_list[0]
    return coin_list.index(fake) + 1, counter
    # print(f'The fake coin is coin {coin_list.index(fake) + 1} '
    #       'in the original list')
    # print(f'Number of weighngs: {counter}')


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    for index, counter in [coin_comparison([10] * 6 + [11] + [10] * 20),
                           coin_comparison([10] * 27)]:
        if index == -1:
            print('no fake coin')
            print(f'Number of weighngs: {counter}')
        else:
            print(f'The fake coin is coin {index} '
                  'in the original list')
            print(f'Number of weighngs: {counter}')

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

$ ./sample2.py -v
Trying:
    coin_comparison([10] * 6 + [11] + [10] * 20)
Expecting:
    (7, 4)
ok
Trying:
    coin_comparison([10] * 27)
Expecting:
    (-1, 2)
ok
Trying:
    coin_comparison([0, 0, 0])
Expecting:
    (-1, 2)
ok
Trying:
    coin_comparison([1, 0, 0])
Expecting:
    (1, 2)
ok
Trying:
    coin_comparison([0, 1, 0])
Expecting:
    (2, 2)
ok
Trying:
    coin_comparison([0, 0, 1])
Expecting:
    (3, 2)
ok
Trying:
    coin_comparison([0, 1, 1])
Expecting:
    (1, 2)
ok
Trying:
    coin_comparison([1, 0, 1])
Expecting:
    (2, 2)
ok
Trying:
    coin_comparison([1, 1, 0])
Expecting:
    (3, 2)
ok
6 items had no tests:
    __main__
    __main__.compare
    __main__.find_fake_group_heavier
    __main__.find_fake_group_lighter
    __main__.find_fake_group_type
    __main__.split_coins
1 items passed all tests:
   9 tests in __main__.coin_comparison
9 tests in 7 items.
9 passed and 0 failed.
Test passed.
The fake coin is coin 7 in the original list
Number of weighngs: 4
no fake coin
Number of weighngs: 2
$