2018年12月3日月曜日

開発環境

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

コード(Emacs)

Python 3

#!/usr/bin/env python3


def remove_talent(candidates: list,
                  candidate_talents: list,
                  all_talents: list,
                  talent: str) -> (list, list, str):
    '''
    >>> remove_talent(candidates, candidate_talents, talents, 'Sing')
    (['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code'], None)
    >>> remove_talent(candidates, candidate_talents, talents, 'Flex')
    (['Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act'], 'Aly')
    >>> remove_talent(candidates2, candidate_talents2, talents2, 2)
    (['A', 'B', 'C', 'D', 'E', 'F', 'G'], [[4, 5, 7], [1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 4, 5, 6, 7, 8, 9], None)
    >>> remove_talent(candidates2, candidate_talents2, talents2, 5)
    (['B', 'C', 'D', 'E', 'F', 'G'], [[1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 6, 8, 9], 'A')
    '''
    cover = False
    new_candidates = candidates[:]
    new_candidate_talents = candidate_talents[:]
    new_all_talents = all_talents[:]
    for i, talents in enumerate(new_candidate_talents):
        if talent in talents:
            if cover:
                return new_candidates, new_candidate_talents, new_all_talents, None
            cover = True
            talent_index = i
    if cover:
        candidate = new_candidates.pop(talent_index)
        talents = new_candidate_talents.pop(talent_index)
        for talent in talents:
            if talent in new_all_talents:
                new_all_talents.remove(talent)
    else:
        candidate = None
    return new_candidates, new_candidate_talents, new_all_talents, candidate


def remove_talents(candidates: list,
                   candidate_talents: list,
                   all_talents: list) -> (list, list, list, list):
    i = 0
    new_candidates = candidates[:]
    new_candidate_talents = candidate_talents[:]
    new_all_talents = all_talents[:]
    other_candidates = []
    while i < len(new_all_talents):
        talent = new_all_talents[i]
        new_candidates, new_candidate_talents, new_all_talents, candidate = \
            remove_talent(new_candidates, new_candidate_talents,
                          new_all_talents, talent)
        if not (candidate is None):
            other_candidates.append(candidate)
        else:
            i += 1
    return new_candidates, new_candidate_talents, new_all_talents, other_candidates


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)
    candidates, candidate_talents, talents, other_candidates = \
        remove_talents(candidates, candidate_talents, 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
    hire += other_candidates
    print(f'Optimum Solution: {sorted(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))

$ ./sample2.py
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
Trying:
    remove_talent(candidates, candidate_talents, talents, 'Sing')
Expecting:
    (['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Flex', 'Code'], ['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code'], None)
ok
Trying:
    remove_talent(candidates, candidate_talents, talents, 'Flex')
Expecting:
    (['Bob', 'Cal', 'Don', 'Eve', 'Fay'], [['Dance', 'Magic'], ['Sing', 'Magic'], ['Sing', 'Dance'], ['Dance', 'Act', 'Code'], ['Act', 'Code']], ['Sing', 'Dance', 'Magic', 'Act'], 'Aly')
ok
Trying:
    remove_talent(candidates2, candidate_talents2, talents2, 2)
Expecting:
    (['A', 'B', 'C', 'D', 'E', 'F', 'G'], [[4, 5, 7], [1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 4, 5, 6, 7, 8, 9], None)
ok
Trying:
    remove_talent(candidates2, candidate_talents2, talents2, 5)
Expecting:
    (['B', 'C', 'D', 'E', 'F', 'G'], [[1, 2, 8], [2, 4, 6, 9], [3, 6, 9], [2, 3, 9], [7, 8, 9], [1, 3, 7]], [1, 2, 3, 6, 8, 9], 'A')
ok
3 items had no tests:
    __main__
    __main__.is_cover
    __main__.remove_talents
4 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 __main__.remove_talent
8 tests in 7 items.
8 passed and 0 failed.
Test passed.
$

0 コメント:

コメントを投稿

関連コンテンツ