開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の8章(招かれざる客)、練習問題(問題3)を取り組んでみる。
コード(Emacs)
Python 3
#!/usr/bin/env python3
def get_two_guests(guests: list, dislike_pairs: list) -> list:
'''
>>> get_two_guests(large_guests, large_dislikes)
(['B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], ['A'])
'''
new_guests = []
other_guests = []
for guest in guests:
is_good = True
for dislike_pair in dislike_pairs:
if guest in dislike_pair:
is_good = False
if is_good:
other_guests.append(guest)
else:
new_guests.append(guest)
return new_guests, other_guests
def invite_dinner_flexible_optimized(guests: list, dislike_pairs: list) -> None:
'''
>>> invite_dinner_flexible_optimized(['A', 'B', 'C'], [('B', 'C')])
Optimum Solution: ['A', 'B', 'C']
>>> invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'B'), ('A', 'C')])
Optimum Solution: ['B', 'C']
>>> invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'B'), ('B', 'C')])
Optimum Solution: ['B', 'C']
>>> invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'C'), ('B', 'C')])
Optimum Solution: ['B', 'C']
'''
new_guests, other_guests = get_two_guests(guests, dislike_pairs)
n = len(new_guests)
invite = []
for i in range(2 ** n):
combination = []
num = i
for j in range(n):
if num % 2 == 1:
combination = [new_guests[n - 1 - j]] + combination
num //= 2
good = True
dislike_count = 0
for a, b in dislike_pairs:
if a in combination and b in combination:
dislike_count += 1
if dislike_count == 2:
good = False
break
if good and len(combination) > len(invite):
invite = combination
invite = other_guests + invite
print(f'Optimum Solution: {invite}')
def is_good(combination: list, name1: str, name2: str) -> bool:
names = [name for name, _ in combination]
return not (name1 in names and name2 in names)
def get_weight(combination: list) -> int:
return sum([weight for _, weight in combination])
def get_two_guests_weight(guests: list, dislike_pairs: list) -> list:
'''
>>> get_two_guests_weight(large_guests_weight, large_dislikes)
([('B', 1), ('C', 3), ('D', 2), ('E', 1), ('F', 4), ('G', 2), ('H', 1), ('I', 3)], [('A', 2)])
'''
new_guests = []
other_guests = []
for guest in guests:
is_good = True
for dislike_pair in dislike_pairs:
if guest[0] in dislike_pair:
is_good = False
break
if is_good:
other_guests.append(guest)
else:
new_guests.append(guest)
return new_guests, other_guests
def invite_dinner_flexible_weight_optimized(
guests: list, dislike_pairs: list) -> None:
'''重み付き最適化した版
>>> invite_dinner_flexible_weight_optimized(large_guests_weight, large_dislikes)
Optimum Solution: [('A', 2), ('C', 3), ('E', 1), ('F', 4), ('I', 3)]
Weight is: 13
'''
new_guests, other_guests = get_two_guests_weight(guests, dislike_pairs)
n = len(new_guests)
invite = []
invite_weight = 0
for i in range(2 ** n):
num = i
combination = []
for j in range(n):
if num % 2 == 1:
combination = [new_guests[n - 1 - j]] + combination
num //= 2
good = True
dislike_count = 0
for a, b in dislike_pairs:
if not is_good(combination, a, b):
dislike_count += 1
if dislike_count == 2:
good = False
break
if good:
weight = get_weight(combination)
if weight > invite_weight:
invite = combination
invite_weight = weight
invite = other_guests + invite
invite_weight += get_weight(other_guests)
print(f'Optimum Solution: {invite}')
print(f'Weight is: {invite_weight}')
if __name__ == '__main__':
import doctest
globs = locals()
large_dislikes = [['B', 'C'], ['C', 'D'], ['D', 'E'],
['F', 'G'], ['F', 'H'], ['F', 'I'], ['G', 'H']]
large_guests = [chr(ord('A') + i) for i in range(9)]
large_guests_weight = list(zip(large_guests, [2, 1, 3, 2, 1, 4, 2, 1, 3]))
globs.update({'large_dislikes': large_dislikes,
'large_guests': large_guests,
'large_guests_weight': large_guests_weight})
doctest.testmod(globs=globs)
invite_dinner_flexible_optimized(large_guests, large_dislikes)
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample3.py -v
Trying:
get_two_guests(large_guests, large_dislikes)
Expecting:
(['B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], ['A'])
ok
Trying:
get_two_guests_weight(large_guests_weight, large_dislikes)
Expecting:
([('B', 1), ('C', 3), ('D', 2), ('E', 1), ('F', 4), ('G', 2), ('H', 1), ('I', 3)], [('A', 2)])
ok
Trying:
invite_dinner_flexible_optimized(['A', 'B', 'C'], [('B', 'C')])
Expecting:
Optimum Solution: ['A', 'B', 'C']
ok
Trying:
invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'B'), ('A', 'C')])
Expecting:
Optimum Solution: ['B', 'C']
ok
Trying:
invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'B'), ('B', 'C')])
Expecting:
Optimum Solution: ['B', 'C']
ok
Trying:
invite_dinner_flexible_optimized(['A', 'B', 'C'], [('A', 'C'), ('B', 'C')])
Expecting:
Optimum Solution: ['B', 'C']
ok
Trying:
invite_dinner_flexible_weight_optimized(large_guests_weight, large_dislikes)
Expecting:
Optimum Solution: [('A', 2), ('C', 3), ('E', 1), ('F', 4), ('I', 3)]
Weight is: 13
ok
3 items had no tests:
__main__
__main__.get_weight
__main__.is_good
4 items passed all tests:
1 tests in __main__.get_two_guests
1 tests in __main__.get_two_guests_weight
4 tests in __main__.invite_dinner_flexible_optimized
1 tests in __main__.invite_dinner_flexible_weight_optimized
7 tests in 7 items.
7 passed and 0 failed.
Test passed.
Optimum Solution: ['A', 'C', 'E', 'G', 'H', 'I']
$
0 コメント:
コメントを投稿