Algorithm - Python - アメリカズ・ゴット・タレント(最小重み候補者選択問題、2次元の表をリストで表す)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の9章(アメリカズ・ゴット・タレント)、練習問題(パズル問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3


def is_good(combination: list, candidates: list, candidate_talents: list,
            all_talents: list) -> bool:
    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 get_weight(candidates: list) -> int:
    return sum([weight for _, weight in candidates])


def hire_for_show(
        candidates: list, candidate_talents: list, talents: list) -> None:
    '''
    >>> hire_for_show(candidates, candidate_talents, talents)
    Optimum Solution: [('A', 3), ('C', 1), ('D', 4), ('F', 2)]
    Weight is: 10
    '''
    n = len(candidates)
    hire = candidates[:]
    hire_weight = get_weight(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):
            combination_weight = get_weight(combination)
            if combination_weight < hire_weight:
                hire = combination
                hire_weight = combination_weight
    print(f'Optimum Solution: {hire}')
    print(f'Weight is: {hire_weight}')


if __name__ == '__main__':
    import doctest
    talents = list(range(1, 10))
    candidates = list(zip([chr(ord('A') + i) for i in range(7)],
                          [3, 2, 1, 4, 5, 2, 7]))
    candidate_talents = [[1, 5],
                         [1, 2, 8],
                         [2, 3, 6, 9],
                         [4, 6, 8],
                         [2, 3, 9],
                         [7, 8, 9],
                         [1, 3, ]]
    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})
    doctest.testmod(globs=globs)

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

$ ./sample3.py -v
Trying:
    hire_for_show(candidates, candidate_talents, talents)
Expecting:
    Optimum Solution: [('A', 3), ('C', 1), ('D', 4), ('F', 2)]
    Weight is: 10
ok
3 items had no tests:
    __main__
    __main__.get_weight
    __main__.is_good
1 items passed all tests:
   1 tests in __main__.hire_for_show
1 tests in 4 items.
1 passed and 0 failed.
Test passed.
$