## 2018年12月13日木曜日

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

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

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