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

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

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

コード(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)

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

$ ./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
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
   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.
$