## 2018年12月28日金曜日

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

コード(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)
```

```\$ ./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
__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.
\$
```