## 2018年12月2日日曜日

### Algorithm - Python - アメリカズ・ゴット・タレント(組み合わせ生成の効率化、2次元の表をリストで表す)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

def is_cover(talents: list, other_talents: list) -> bool:
for talent in talents:
if talent not in other_talents:
return False
return True

def remove_candidates(candidates, candidate_talents) -> (list, list):
'''
>>> remove_candidates(candidates, candidate_talents)
(['Aly', 'Bob', 'Cal', 'Don', 'Eve'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code']])
'''
new_candidates = []
new_candidate_talents = []
for i, talents in enumerate(candidate_talents):
talents = candidate_talents[i]
cover = False
for j, other_talents in enumerate(candidate_talents):
if i != j and is_cover(talents, other_talents):
cover = True
break
if not cover:
new_candidates.append(candidates[i])
new_candidate_talents.append(talents)

return new_candidates, new_candidate_talents

def is_good(combination: list, candidates: list, candidate_talents: list,
all_talents: list) -> bool:
'''
>>> is_good(['Aly', 'Cal', 'Eve'], candidates, candidate_talents, talents)
True
'''
for talent in all_talents:
cover = False
for candidate in combination:
candidate_talent = candidate_talents[candidates.index(candidate)]
if talent in candidate_talent:
cover = True
break
if not cover:
return False
return True

def hire_for_show(
candidates: list, candidate_talents: list, talents: list) -> None:
'''
>>> hire_for_show(candidates, candidate_talents, talents)
Optimum Solution: ['Aly', 'Cal', 'Eve']
>>> hire_for_show(candidates2, candidate_talents2, talents2)
Optimum Solution: ['A', 'B', 'D']
'''
candidates, candidate_talents = remove_candidates(candidates,
candidate_talents)
n = len(candidates)
hire = candidates[:]
for i in range(2 ** n):
combination = []
num = i
for j in range(n):
if num % 2 == 1:
combination = [candidates[n - 1 - j]] + combination
num //= 2
if is_good(combination, candidates, candidate_talents, talents) and \
len(hire) > len(combination):
hire = combination
print(f'Optimum Solution: {hire}')

if __name__ == '__main__':
import doctest
talents = ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code']
candidates = ['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay']
candidate_talents = [['Flex', 'Code'],
['Dance', 'Magic'],
['Sing', 'Magic'],
['Sing', 'Dance'],
['Dance', 'Act', 'Code'],
['Act', 'Code']]
talents2 = list(range(1, 10))
candidates2 = [chr(ord('A') + i) for i in range(10)]
candidate_talents2 = [[4, 5, 7],
[1, 2, 8],
[2, 4, 6, 9],
[3, 6, 9],
[2, 3, 9],
[7, 8, 9],
[1, 3, 7]]
globs = locals()
globs.update({'talents': talents,
'candidates': candidates,
'candidate_talents': candidate_talents,
'talents2': talents2,
'candidates2': candidates2,
'candidate_talents2': candidate_talents2})
doctest.testmod(globs=globs)
```

```\$ ./sample1.py -v
Trying:
hire_for_show(candidates, candidate_talents, talents)
Expecting:
Optimum Solution: ['Aly', 'Cal', 'Eve']
ok
Trying:
hire_for_show(candidates2, candidate_talents2, talents2)
Expecting:
Optimum Solution: ['A', 'B', 'D']
ok
Trying:
is_good(['Aly', 'Cal', 'Eve'], candidates, candidate_talents, talents)
Expecting:
True
ok
Trying:
remove_candidates(candidates, candidate_talents)
Expecting:
(['Aly', 'Bob', 'Cal', 'Don', 'Eve'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code']])
ok
__main__
__main__.is_cover
3 items passed all tests:
2 tests in __main__.hire_for_show
1 tests in __main__.is_good
1 tests in __main__.remove_candidates
4 tests in 5 items.
4 passed and 0 failed.
Test passed.
\$
```