## 2018年11月30日金曜日

### Algorithm - Python - 招かれざる客(効率、最大選択肢、重み、メモリ使用の最適化、リストの連結、しらみつぶしの数え上げと符号化の組合わせ)

コード(Emacs)

Python 3

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

def get_two_guests(guests: list, dislike_pairs: list) -> list:
'''
>>> get_two_guests(guests, dislike_pairs)
(['Alice', 'Bob', 'Eve'], ['Cleo', 'Don'])
'''
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_optimized(guests: list, dislike_pairs: list) -> None:
'''
>>> invite_dinner_optimized(guests, dislike_pairs)
Optimum Solution: ['Alice', 'Eve', 'Cleo', 'Don']
'''
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
for a, b in dislike_pairs:
if a in combination and b in combination:
good = False
break
if good and len(combination) > len(invite):
invite = combination
invite += other_guests
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(guests_weight, dislike_pairs)
([('Alice', 2), ('Bob', 6), ('Eve', 3)], [('Cleo', 3), ('Don', 10)])
'''
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_weight_optimized(guests: list, dislike_pairs: list) -> None:
'''重み付き最適化した版
>>> invite_dinner_weight_optimized(guests_weight, dislike_pairs)
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
'''
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
for a, b in dislike_pairs:
if not is_good(combination, a, b):
good = False
break
if good:
weight = get_weight(combination)
if weight > invite_weight:
invite = combination
invite_weight = weight
invite += other_guests
print(f'Optimum Solution: {invite}')

if __name__ == '__main__':
import doctest
globs = locals()
dislike_pairs = [['Alice', 'Bob'], ['Bob', 'Eve']]
guests = ['Alice', 'Bob', 'Cleo', 'Don', 'Eve']
guests_weight = list(zip(guests, [2, 6, 3, 10, 3]))
globs.update({'dislike_pairs': dislike_pairs,
'guests': guests,
'guests_weight': guests_weight})
doctest.testmod(globs=globs)
```

```\$ ./sample2.py -v
Trying:
get_two_guests(guests, dislike_pairs)
Expecting:
(['Alice', 'Bob', 'Eve'], ['Cleo', 'Don'])
ok
Trying:
get_two_guests_weight(guests_weight, dislike_pairs)
Expecting:
([('Alice', 2), ('Bob', 6), ('Eve', 3)], [('Cleo', 3), ('Don', 10)])
ok
Trying:
invite_dinner_optimized(guests, dislike_pairs)
Expecting:
Optimum Solution: ['Alice', 'Eve', 'Cleo', 'Don']
ok
Trying:
invite_dinner_weight_optimized(guests_weight, dislike_pairs)
Expecting:
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
ok
__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
1 tests in __main__.invite_dinner_optimized
1 tests in __main__.invite_dinner_weight_optimized
4 tests in 7 items.
4 passed and 0 failed.
Test passed.
\$
```