Algorithm - Python - 貪欲は良いことだ(履修時間数の最大化、重ならない科目、関数引数、貪欲アルゴリズム)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の16章(貪欲は良いことだ)、練習問題(パズル問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def get_courses_after(course: list, courses: list):
    '''
    >>> get_courses_after([9, 12], courses)
    [[12, 13], [15, 16], [16, 17], [18, 20], [17, 19], [13, 20]]
    >>> get_courses_after([17, 19], courses)
    []
    '''
    _, finish = course
    return [c for c in courses if c[0] >= finish]


def get_duration(courses: list) -> int:
    '''
    >>> get_duration(courses)
    20
    '''
    return sum([finish - start for start, finish in courses])


def recursive_select(courses: list) -> list:
    '''
    >>> recursive_select([[1, 20], [2, 3], [4, 5]])
    [[1, 20]]
    >>> recursive_select([[2, 3], [1, 20], [4, 5]])
    [[1, 20]]
    >>> recursive_select([[2, 3], [4, 5], [1, 20]])
    [[1, 20]]
    >>> recursive_select([[1, 20], [1, 3], [4, 5]])
    [[1, 20]]
    >>> recursive_select([[1, 3], [1, 20], [4, 5]])
    [[1, 20]]
    >>> recursive_select([[1, 20], [2, 3], [20, 21], [4, 5], [5, 6], [7, 10]])
    [[1, 20], [20, 21]]
    '''
    if len(courses) == 0:
        return []
    duration = 0
    for course in courses:
        courses_after = get_courses_after(course, courses)
        courses_tmp = [course] + recursive_select(courses_after)
        duration_tmp = get_duration(courses_tmp)
        if duration_tmp > duration:
            duration = duration_tmp
            selected_courses = courses_tmp
    return selected_courses


if __name__ == '__main__':
    import doctest
    courses = [[8, 10], [9, 12], [11, 12], [12, 13], [15, 16], [16, 17],
               [18, 20], [17, 19], [13, 20]]
    globs = globals()
    globs.update({'courses': courses})
    doctest.testmod(globs=globs)

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

$ ./sample3.py -v
Trying:
    get_courses_after([9, 12], courses)
Expecting:
    [[12, 13], [15, 16], [16, 17], [18, 20], [17, 19], [13, 20]]
ok
Trying:
    get_courses_after([17, 19], courses)
Expecting:
    []
ok
Trying:
    get_duration(courses)
Expecting:
    20
ok
Trying:
    recursive_select([[1, 20], [2, 3], [4, 5]])
Expecting:
    [[1, 20]]
ok
Trying:
    recursive_select([[2, 3], [1, 20], [4, 5]])
Expecting:
    [[1, 20]]
ok
Trying:
    recursive_select([[2, 3], [4, 5], [1, 20]])
Expecting:
    [[1, 20]]
ok
Trying:
    recursive_select([[1, 20], [1, 3], [4, 5]])
Expecting:
    [[1, 20]]
ok
Trying:
    recursive_select([[1, 3], [1, 20], [4, 5]])
Expecting:
    [[1, 20]]
ok
Trying:
    recursive_select([[1, 20], [2, 3], [20, 21], [4, 5], [5, 6], [7, 10]])
Expecting:
    [[1, 20], [20, 21]]
ok
1 items had no tests:
    __main__
3 items passed all tests:
   2 tests in __main__.get_courses_after
   1 tests in __main__.get_duration
   6 tests in __main__.recursive_select
9 tests in 4 items.
9 passed and 0 failed.
Test passed.
$