Algorithm - Python - 中庭にタイルを敷く(最良のアルゴリズム、各ステップで行か列の削除、全行と全列がソート済みの2次元リスト、リスト内包表記、再帰分割統治探索)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の11章(中庭にタイルを敷く)、練習問題(パズル問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3


def find_recursive_remove_row_or_col(
        n: int, t: list, origin_i: int = 0) -> (int, int):
    '''
    >>> find_recursive_remove_row_or_col(21, t)
    (4, 1)
    >>> find_recursive_remove_row_or_col(0, t)
    (-1, -1)
    >>> find_recursive_remove_row_or_col(100, t)
    (-1, -1)
    >>> find_recursive_remove_row_or_col(9, t)
    (2, 2)
    >>> find_recursive_remove_row_or_col(1, t)
    (0, 0)
    >>> find_recursive_remove_row_or_col(15, t)
    (0, 4)
    >>> find_recursive_remove_row_or_col(18, t)
    (4, 0)
    >>> find_recursive_remove_row_or_col(30, t)
    (4, 4)
    '''
    if len(t) == 0:
        return -1, -1
    row0 = t[0]
    row0_len = len(row0)
    if row0_len == 0:
        return -1, -1
    row0_last = row0[-1]
    if n == row0_last:
        return origin_i, row0_len - 1
    if row0_last < n:
        return find_recursive_remove_row_or_col(n, t[1:], origin_i + 1)
    t = [row[:row0_len - 1] for row in t]
    return find_recursive_remove_row_or_col(n, t, origin_i)


if __name__ == '__main__':
    import doctest
    t = [[1, 4, 7, 11, 15],
         [2, 5, 8, 12, 19],
         [3, 6, 9, 16, 22],
         [10, 13, 14, 17, 24],
         [18, 21, 23, 26, 30]]
    globs = locals()
    globs.update({'t': t})
    doctest.testmod(globs=globs)

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

$ ./sample3.py -v
Trying:
    find_recursive_remove_row_or_col(21, t)
Expecting:
    (4, 1)
ok
Trying:
    find_recursive_remove_row_or_col(0, t)
Expecting:
    (-1, -1)
ok
Trying:
    find_recursive_remove_row_or_col(100, t)
Expecting:
    (-1, -1)
ok
Trying:
    find_recursive_remove_row_or_col(9, t)
Expecting:
    (2, 2)
ok
Trying:
    find_recursive_remove_row_or_col(1, t)
Expecting:
    (0, 0)
ok
Trying:
    find_recursive_remove_row_or_col(15, t)
Expecting:
    (0, 4)
ok
Trying:
    find_recursive_remove_row_or_col(18, t)
Expecting:
    (4, 0)
ok
Trying:
    find_recursive_remove_row_or_col(30, t)
Expecting:
    (4, 4)
ok
1 items had no tests:
    __main__
1 items passed all tests:
   8 tests in __main__.find_recursive_remove_row_or_col
8 tests in 2 items.
8 passed and 0 failed.
Test passed.
$