2018年12月4日火曜日

Algorithm - Python - アメリカズ・ゴット・タレント(最小重み候補者選択問題、2次元の表をリストで表す)

コード(Emacs)

Python 3

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

def is_good(combination: list, candidates: list, candidate_talents: list,
all_talents: list) -> bool:
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 get_weight(candidates: list) -> int:
return sum([weight for _, weight in candidates])

def hire_for_show(
candidates: list, candidate_talents: list, talents: list) -> None:
'''
>>> hire_for_show(candidates, candidate_talents, talents)
Optimum Solution: [('A', 3), ('C', 1), ('D', 4), ('F', 2)]
Weight is: 10
'''
n = len(candidates)
hire = candidates[:]
hire_weight = get_weight(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):
combination_weight = get_weight(combination)
if combination_weight < hire_weight:
hire = combination
hire_weight = combination_weight
print(f'Optimum Solution: {hire}')
print(f'Weight is: {hire_weight}')

if __name__ == '__main__':
import doctest
talents = list(range(1, 10))
candidates = list(zip([chr(ord('A') + i) for i in range(7)],
[3, 2, 1, 4, 5, 2, 7]))
candidate_talents = [[1, 5],
[1, 2, 8],
[2, 3, 6, 9],
[4, 6, 8],
[2, 3, 9],
[7, 8, 9],
[1, 3, ]]
talents2 = list(range(1, 10))
candidates2 = [chr(ord('A') + i) for i in range(7)]
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})
doctest.testmod(globs=globs)
```

```\$ ./sample3.py -v
Trying:
hire_for_show(candidates, candidate_talents, talents)
Expecting:
Optimum Solution: [('A', 3), ('C', 1), ('D', 4), ('F', 2)]
Weight is: 10
ok
__main__
__main__.get_weight
__main__.is_good
1 items passed all tests:
1 tests in __main__.hire_for_show
1 tests in 4 items.
1 passed and 0 failed.
Test passed.
\$
```