## 2018年11月23日金曜日

### Algorithm - Python - 偽造硬貨を探す(偽造硬貨がない場合、リストスライス、ケース分析、分割統治法)

コード(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()
```

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

\$
```