2018年11月29日木曜日

開発環境

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の8章(招かれざる客)、練習問題(問題1)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3

dislike_pairs = [['Alice', 'Bob'], ['Bob', 'Eve']]
guests = [('Alice', 2), ('Bob', 6), ('Cleo', 3), ('Don', 10), ('Eve', 3)]


def combinations(n: int, guests: list) -> list:
    all_combinations = []
    for i in range(2 ** n):
        num = i
        combinations = []
        for j in range(n):
            if num % 2 == 1:
                combinations = [guests[n - 1 - j]] + combinations
            num //= 2
        all_combinations.append(combinations)
    return all_combinations


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 remove_bad_combinations(
        all_combinations: list, dislike_pairs: list) -> list:
    all_good_combinations = []
    for combination in all_combinations:
        good = True
        for a, b in dislike_pairs:
            if not is_good(combination, a, b):
                good = False
                break
        if good:
            all_good_combinations.append(combination)
    return all_good_combinations


def get_weight(combination: list) -> int:
    return sum([weight for _, weight in combination])


def invite_dinner(guests: list, dislike_pairs: list) -> None:
    ''' メモリーの使用量を最適化していない版
    >>> invite_dinner(guests, dislike_pairs)
    Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
    '''
    all_combinations = combinations(len(guests), guests)
    all_good_combinations = remove_bad_combinations(
        all_combinations, dislike_pairs)
    invite = max(all_good_combinations, key=get_weight)
    print(f'Optimum Solution: {invite}')


def invite_dinner_optimized(guests: list, dislike_pairs: list) -> None:
    ''' メモリーの使用量を最適化した版
    >>> invite_dinner_optimized(guests, dislike_pairs)
    Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
    '''
    n = len(guests)
    invite = []
    invite_weight = 0
    for i in range(2 ** n):
        num = i
        combination = []
        for j in range(n):
            if num % 2 == 1:
                combination = [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
    print(f'Optimum Solution: {invite}')


if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample1.py -v
Trying:
    invite_dinner(guests, dislike_pairs)
Expecting:
    Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
ok
Trying:
    invite_dinner_optimized(guests, dislike_pairs)
Expecting:
    Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
ok
5 items had no tests:
    __main__
    __main__.combinations
    __main__.get_weight
    __main__.is_good
    __main__.remove_bad_combinations
2 items passed all tests:
   1 tests in __main__.invite_dinner
   1 tests in __main__.invite_dinner_optimized
2 tests in 7 items.
2 passed and 0 failed.
Test passed.
$

0 コメント:

コメントを投稿

関連コンテンツ