## 2018年11月24日土曜日

### 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_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}')
```

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