Algorithm - Python - おびただしい女王(アメリカズ・ゴット・タレント、forループを再帰関数に変換、再帰プロシージャーによるしらみつぶし探索)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の10章(おびただしい女王)、練習問題(パズル問題4)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3


def is_good(combination: list, candidates: list, candidates_talents: list,
            all_talents: list) -> bool:
    for talent in all_talents:
        cover = False
        for candidate in combination:
            candidate_talents = candidates_talents[candidates.index(candidate)]
            if talent in candidate_talents:
                cover = True
        if not cover:
            return False
    return True


def recursive_combination(
        j: int, n: int, num: int, candidates: list, combination: list) -> list:
    if j == n:
        return combination
    if num % 2 == 1:
        combination = [candidates[n - 1 - j]] + combination
    num //= 2
    return recursive_combination(j + 1, n, num, candidates, combination)


def small_solution(i: int, candidates: list, n: int, candidates_talents: list,
                   talents: list, hire: list) -> list:
    if i == 2 ** n:
        return hire
    combination = recursive_combination(0, n, i, candidates, [])
    if is_good(combination, candidates, candidates_talents, talents) and \
       len(combination) < len(hire):
        return small_solution(i + 1, candidates, n, candidates_talents, talents,
                              combination)
    return small_solution(i + 1, candidates, n, candidates_talents, talents,
                          hire)


def hire_for_show(candidates: list,
                  candidates_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']
    '''
    hire = small_solution(0, candidates, len(candidates), candidates_talents,
                          talents, candidates[:])
    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(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,
                  'talents2': talents2,
                  'candidates2': candidates2,
                  'candidate_talents2': candidate_talents2})
    doctest.testmod(globs=globs)

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

$ ./sample4.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
4 items had no tests:
    __main__
    __main__.is_good
    __main__.recursive_combination
    __main__.small_solution
1 items passed all tests:
   2 tests in __main__.hire_for_show
2 tests in 5 items.
2 passed and 0 failed.
Test passed.
$