Algorithm - Python - パーティーに行くタイミング(重み、時間の粒度に依存しない方法、入れ子forループ)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple
• Emacs (Text Editor)
• Python 3.7 (プログラミング言語)

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

コード(Emacs)

Python 3

#!/usr/bin/env python3
''' パズル問題3 '''


def best_time_to_party_smart(schedule: list):
    '''
    >>> sched0 = []
    >>> sched1 = [(7, 8, 1)]
    >>> sched2 = [(7, 8, 1), (6, 10, 1), (6.5, 7.5, 1), (8.5, 9, 3)]
    >>> sched3 = [(6, 8, 2), (6.5, 12, 1), (6.5, 7, 2), (7, 8,  2),
    ...           (7.5, 10, 3), (8, 9, 2), (8, 10, 1), (9, 12, 2),
    ...           (9.5, 10, 4), (10, 11, 2), (10, 12, 3), (11, 12, 7)]
    >>> best_time_to_party_smart(sched0)
    >>> best_time_to_party_smart(sched1)
    (7, 1)
    >>> best_time_to_party_smart(sched2)
    (8.5, 4)
    >>> best_time_to_party_smart(sched3)
    (11, 13)
    '''
    if not schedule:
        return None
    time, _, max_weight = schedule[0]
    for i, (start, _, weight) in enumerate(schedule):
        for start1, end1, weight1 in schedule[:i] + schedule[i+1:]:
            if start1 <= start < end1:
                weight += weight1
        if weight > max_weight:
            max_weight = weight
            time = start

    return time, max_weight


if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, Jupyter(IPython))

$ ./sample3.py -v
Trying:
    sched0 = []
Expecting nothing
ok
Trying:
    sched1 = [(7, 8, 1)]
Expecting nothing
ok
Trying:
    sched2 = [(7, 8, 1), (6, 10, 1), (6.5, 7.5, 1), (8.5, 9, 3)]
Expecting nothing
ok
Trying:
    sched3 = [(6, 8, 2), (6.5, 12, 1), (6.5, 7, 2), (7, 8,  2),
              (7.5, 10, 3), (8, 9, 2), (8, 10, 1), (9, 12, 2),
              (9.5, 10, 4), (10, 11, 2), (10, 12, 3), (11, 12, 7)]
Expecting nothing
ok
Trying:
    best_time_to_party_smart(sched0)    
Expecting nothing
ok
Trying:
    best_time_to_party_smart(sched1)
Expecting:
    (7, 1)
ok
Trying:
    best_time_to_party_smart(sched2)
Expecting:
    (8.5, 4)
ok
Trying:
    best_time_to_party_smart(sched3)
Expecting:
    (11, 13)
ok
1 items had no tests:
    __main__
1 items passed all tests:
   8 tests in __main__.best_time_to_party_smart
8 tests in 2 items.
8 passed and 0 failed.
Test passed.
$ pylint  sample3.py
************* Module sample3
sample3.py:13:40: C0303: Trailing whitespace (trailing-whitespace)
sample3.py:21:7: C1801: Do not use `len(SEQUENCE)` to determine if a sequence is empty (len-as-condition)
sample3.py:5:0: R1710: Either all return statements in a function should return an expression, or none of them should. (inconsistent-return-statements)
sample3.py:24:19: W0612: Unused variable 'end' (unused-variable)

-----------------------------------
Your code has been rated at 7.33/10

$ pylint  sample3.py

-------------------------------------------------------------------
Your code has been rated at 10.00/10 (previous run: 7.33/10, +2.67)

$