## 2018年11月25日日曜日

### Algorithm - Python - 偽造硬貨を探す(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(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()
```

```\$ ./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
__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.
\$
```