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章(偽造硬貨を探す)、練習問題(問題1)を取り組んでみる。

コード(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, bool):
    result1_2 = compare(group1, group2)
    if result1_2 == 'left':
        return group1, False
    if result1_2 == 'right':
        return group2, False
    return group3, True


def coin_comparison(coin_list: list) -> None:
    counter = 0
    current_list = coin_list
    while len(current_list) > 1:
        group1, group2, group3 = split_coins(current_list)
        current_list, equal = find_fake_group(group1, group2, group3)
        counter += 1
    if equal:
        counter += 1
        if compare(current_list, group1) == 'equal':
            print('no fake coin')
            print(f'Number of weighngs: {counter}')
            return
    fake = current_list[0]
    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__':
    coin_list1 = [10] * 6 + [11] + [10] * 20
    coin_list2 = [10] * 27
    coin_list3 = [0, 0, 0]
    coin_list4 = [0, 0, 1]
    coin_list5 = [0, 1, 0]
    coin_list6 = [1, 0, 0]
    for coin_list in [coin_list1, coin_list2, coin_list3, coin_list4,
                      coin_list5, coin_list6]:
        print(coin_list)
        coin_comparison(coin_list)
        print()

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

$ ./sample1.py
[10, 10, 10, 10, 10, 10, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
The fake coin is coin 7 in the original list
Number of weighngs: 3

[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
no fake coin
Number of weighngs: 4

[0, 0, 0]
no fake coin
Number of weighngs: 2

[0, 0, 1]
The fake coin is coin 3 in the original list
Number of weighngs: 2

[0, 1, 0]
The fake coin is coin 2 in the original list
Number of weighngs: 1

[1, 0, 0]
The fake coin is coin 1 in the original list
Number of weighngs: 1

$