2018年12月5日水曜日

開発環境

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

コード(Emacs)

Python 3

#!/usr/bin/env python3


def remove_talent(candidates: list,
                  candidate_talents: list,
                  all_talents: list,
                  talent: str) -> (list, list, str):
    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_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
    '''
    candidates, candidate_talents, talents, other_candidates = \
        remove_talents(candidates, candidate_talents, talents)
    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
    hire += other_candidates
    hire_weight += get_weight(other_candidates)
    print(f'Optimum Solution: {sorted(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))

$ ./sample4.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
5 items had no tests:
    __main__
    __main__.get_weight
    __main__.is_good
    __main__.remove_talent
    __main__.remove_talents
1 items passed all tests:
   1 tests in __main__.hire_for_show
1 tests in 6 items.
1 passed and 0 failed.
Test passed.
$

0 コメント:

コメントを投稿

関連コンテンツ