開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の9章(アメリカズ・ゴット・タレント)、練習問題(問題4)を取り組んでみる。
コード(Emacs)
Python 3
#!/usr/bin/env python3
def remove_talent(candidates: list,
candidate_talents: list,
all_talents: list,
talent: str) -> (list, list, str):
cover = False
new_candidates = candidates[:]
new_candidate_talents = candidate_talents[:]
new_all_talents = all_talents[:]
for i, talents in enumerate(new_candidate_talents):
if talent in talents:
if cover:
return (new_candidates,
new_candidate_talents,
new_all_talents,
None)
cover = True
talent_index = i
if cover:
candidate = new_candidates.pop(talent_index)
talents = new_candidate_talents.pop(talent_index)
for talent in talents:
if talent in new_all_talents:
new_all_talents.remove(talent)
else:
candidate = None
return new_candidates, new_candidate_talents, new_all_talents, candidate
def remove_talents(candidates: list,
candidate_talents: list,
all_talents: list) -> (list, list, list, list):
i = 0
new_candidates = candidates[:]
new_candidate_talents = candidate_talents[:]
new_all_talents = all_talents[:]
other_candidates = []
while i < len(new_all_talents):
talent = new_all_talents[i]
new_candidates, new_candidate_talents, new_all_talents, candidate = \
remove_talent(new_candidates, new_candidate_talents,
new_all_talents, talent)
if not (candidate is None):
other_candidates.append(candidate)
else:
i += 1
return (new_candidates,
new_candidate_talents,
new_all_talents,
other_candidates)
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
'''
candidates, candidate_talents, talents, other_candidates = \
remove_talents(candidates, candidate_talents, talents)
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
hire += other_candidates
hire_weight += get_weight(other_candidates)
print(f'Optimum Solution: {sorted(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)
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample4.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
5 items had no tests:
__main__
__main__.get_weight
__main__.is_good
__main__.remove_talent
__main__.remove_talents
1 items passed all tests:
1 tests in __main__.hire_for_show
1 tests in 6 items.
1 passed and 0 failed.
Test passed.
$
0 コメント:
コメントを投稿