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章(アメリカズ・ゴット・タレント)、練習問題(問題1)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3


def is_cover(talents: list, other_talents: list) -> bool:
    for talent in talents:
        if talent not in other_talents:
            return False
    return True


def remove_candidates(candidates, candidate_talents) -> (list, list):
    '''
    >>> remove_candidates(candidates, candidate_talents)
    (['Aly', 'Bob', 'Cal', 'Don', 'Eve'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code']])
    '''
    new_candidates = []
    new_candidate_talents = []
    for i, talents in enumerate(candidate_talents):
        talents = candidate_talents[i]
        cover = False
        for j, other_talents in enumerate(candidate_talents):
            if i != j and is_cover(talents, other_talents):
                cover = True
                break
        if not cover:
            new_candidates.append(candidates[i])
            new_candidate_talents.append(talents)

    return new_candidates, new_candidate_talents


def is_good(combination: list, candidates: list, candidate_talents: list,
            all_talents: list) -> bool:
    '''
    >>> is_good(['Aly', 'Cal', 'Eve'], candidates, candidate_talents, talents)
    True
    '''
    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 hire_for_show(
        candidates: list, candidate_talents: list, talents: list) -> None:
    '''
    >>> hire_for_show(candidates, candidate_talents, talents)
    Optimum Solution: ['Aly', 'Cal', 'Eve']
    >>> hire_for_show(candidates2, candidate_talents2, talents2)
    Optimum Solution: ['A', 'B', 'D']
    '''
    candidates, candidate_talents = remove_candidates(candidates,
                                                      candidate_talents)
    n = len(candidates)
    hire = 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) and \
           len(hire) > len(combination):
            hire = combination
    print(f'Optimum Solution: {hire}')


if __name__ == '__main__':
    import doctest
    talents = ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code']
    candidates = ['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay']
    candidate_talents = [['Flex', 'Code'],
                         ['Dance', 'Magic'],
                         ['Sing', 'Magic'],
                         ['Sing', 'Dance'],
                         ['Dance', 'Act', 'Code'],
                         ['Act', 'Code']]
    talents2 = list(range(1, 10))
    candidates2 = [chr(ord('A') + i) for i in range(10)]
    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,
                  'talents2': talents2,
                  'candidates2': candidates2,
                  'candidate_talents2': candidate_talents2})
    doctest.testmod(globs=globs)

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

$ ./sample1.py -v
Trying:
    hire_for_show(candidates, candidate_talents, talents)
Expecting:
    Optimum Solution: ['Aly', 'Cal', 'Eve']
ok
Trying:
    hire_for_show(candidates2, candidate_talents2, talents2)
Expecting:
    Optimum Solution: ['A', 'B', 'D']
ok
Trying:
    is_good(['Aly', 'Cal', 'Eve'], candidates, candidate_talents, talents)
Expecting:
    True
ok
Trying:
    remove_candidates(candidates, candidate_talents)
Expecting:
    (['Aly', 'Bob', 'Cal', 'Don', 'Eve'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code']])
ok
2 items had no tests:
    __main__
    __main__.is_cover
3 items passed all tests:
   2 tests in __main__.hire_for_show
   1 tests in __main__.is_good
   1 tests in __main__.remove_candidates
4 tests in 5 items.
4 passed and 0 failed.
Test passed.
$