開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の9章(アメリカズ・ゴット・タレント)、練習問題(問題2)を取り組んでみる。
コード(Emacs)
Python 3
#!/usr/bin/env python3
def remove_talent(candidates: list,
candidate_talents: list,
all_talents: list,
talent: str) -> (list, list, str):
'''
>>> remove_talent(candidates, candidate_talents, talents, 'Sing')
(['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code'], None)
>>> remove_talent(candidates, candidate_talents, talents, 'Flex')
(['Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act'], 'Aly')
>>> remove_talent(candidates2, candidate_talents2, talents2, 2)
(['A', 'B', 'C', 'D', 'E', 'F', 'G'], [[4, 5, 7], [1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 4, 5, 6, 7, 8, 9], None)
>>> remove_talent(candidates2, candidate_talents2, talents2, 5)
(['B', 'C', 'D', 'E', 'F', 'G'], [[1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 6, 8, 9], 'A')
'''
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_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)
candidates, candidate_talents, talents, other_candidates = \
remove_talents(candidates, candidate_talents, 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
hire += other_candidates
print(f'Optimum Solution: {sorted(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(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,
'talents2': talents2,
'candidates2': candidates2,
'candidate_talents2': candidate_talents2})
doctest.testmod(globs=globs)
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample2.py
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
Trying:
remove_talent(candidates, candidate_talents, talents, 'Sing')
Expecting:
(['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code'], None)
ok
Trying:
remove_talent(candidates, candidate_talents, talents, 'Flex')
Expecting:
(['Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act'], 'Aly')
ok
Trying:
remove_talent(candidates2, candidate_talents2, talents2, 2)
Expecting:
(['A', 'B', 'C', 'D', 'E', 'F', 'G'], [[4, 5, 7], [1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 4, 5, 6, 7, 8, 9], None)
ok
Trying:
remove_talent(candidates2, candidate_talents2, talents2, 5)
Expecting:
(['B', 'C', 'D', 'E', 'F', 'G'], [[1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 6, 8, 9], 'A')
ok
3 items had no tests:
__main__
__main__.is_cover
__main__.remove_talents
4 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 __main__.remove_talent
8 tests in 7 items.
8 passed and 0 failed.
Test passed.
$
0 コメント:
コメントを投稿