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章(中庭にタイルを敷く)、練習問題(パズル問題2)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3


def bin_search(
        n: int, t: list, origin_i: int = 0, origin_j: int = 0) -> (int, int):
    '''
    >>> bin_search(21, t)
    (4, 1)
    >>> bin_search(0, t)
    (-1, -1)
    >>> bin_search(100, t)
    (-1, -1)
    >>> bin_search(9, t)
    (2, 2)
    >>> bin_search(1, t)
    (0, 0)
    >>> bin_search(15, t)
    (0, 4)
    >>> bin_search(18, t)
    (4, 0)
    >>> bin_search(30, t)
    (4, 4)
    '''
    rows = len(t)
    if rows == 0:
        return -1, -1
    cols = len(t[0])
    if cols == 0:
        return -1, -1
    i = (rows - 1) // 2
    j = (cols - 1) // 2
    if n == t[i][j]:
        return origin_i + i, origin_j + j
    if n < t[i][j]:
        new_i, new_j = bin_search(n, [t[i][:j]], origin_i, origin_j)
        if new_i != -1:
            return new_i, new_j
        new_i, new_j = bin_search(n, [[row[j]] for row in t[:i]],
                                  origin_i, origin_j)
        if new_i != -1:
            return new_i, new_j
        return bin_search(n, [row[:j] for row in t[:i]],
                          origin_i, origin_j)
    new_i, new_j = bin_search(n, [row[j + 1:] for row in t[:i + 1]],
                              origin_i, origin_j + j + 1)
    if new_i != -1:
        return new_i, new_j
    new_i, new_j = bin_search(n, [row[:j + 1] for row in t[i + 1:]],
                              origin_i + i + 1, origin_j)
    if new_i != -1:
        return new_i, new_j
    return bin_search(n, [row[j + 1:] for row in t[i + 1:]],
                      origin_i + i + 1, origin_j + j + 1)


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, 3, 26, 30]]
    globs = locals()
    globs.update({'t': t})
    doctest.testmod(globs=globs)

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

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