開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の11章(中庭にタイルを敷く)、練習問題(問題1)を取り組んでみる。
コード(Emacs)
Python 3
#!/usr/bin/env python3
import random
def is_different_quad(missing_tiles: list) -> bool:
quads = [(row // 4, col // 4) for row, col in missing_tiles]
for i, quad1 in enumerate(quads):
for j, quad2 in enumerate(quads):
if i != j and quad1 == quad2:
return False
return True
def is_tromino(missing_tiles: list):
for i, tile1 in enumerate(missing_tiles):
tile1_row, tile1_col = tile1
for j, tile2 in enumerate(missing_tiles):
if i == j:
continue
tile2_row, tile2_col = tile2
for k, tile3 in enumerate(missing_tiles):
if i == k or j == k:
continue
tile3_row, tile3_col = tile3
if (
tile2_row - tile1_row == 1 and tile1_col == tile2_col and
tile2_row == tile3_row and tile3_col - tile2_col == 1
) or (
tile1_row == tile2_row and tile1_col - tile2_col == 1 and
tile3_row - tile2_row == 1 and tile2_col == tile3_col
) or (
tile1_row - tile2_row == 1 and tile1_col == tile2_col and
tile2_row == tile3_row and tile2_col - tile3_col == 1
) or (
tile1_row == tile2_row and tile2_col - tile1_col == 1 and
tile2_row - tile3_row == 1 and tile2_col == tile3_col
):
return True
return False
def four_tiles_missing_yard(n: int, tiles_missing: list) -> bool:
if n <= 1:
return True
# 4つの欠損正方形が4つの異なる象限にあるか
if is_different_quad(tiles_missing):
print('quads')
return True
# 4つのうち3つにトロミノが当てはまるか
for i, _ in enumerate(tiles_missing):
if is_tromino(tiles_missing[:i] + tiles_missing[i + 1:]):
print('tromino')
return True
return False
def print_yard(n, missing_tiles) -> None:
for row in range(2 ** n):
for col in range(2 ** n):
if (row, col) in missing_tiles:
print(' ', end='')
else:
print('X', end='')
print()
if __name__ == '__main__':
print(four_tiles_missing_yard(3, [(0, 0), (0, 7), (7, 0), (7, 7)]))
print(four_tiles_missing_yard(3, [(0, 0), (0, 1), (1, 0), (7, 7)]))
for _ in range(10):
n = random.randrange(2, 5)
tiles = [(row, col)
for row in range(2 ** n)
for col in range(2 ** n)]
missing_tiles = random.sample(tiles, k=4)
print(n, missing_tiles)
print_yard(n, missing_tiles)
print(four_tiles_missing_yard(n, missing_tiles))
print()
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample1.py quads True tromino True 4 [(5, 3), (10, 2), (3, 7), (12, 3)] XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXX XXXXXXXX XXXXXXXXXXXXXXXX XXX XXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XX XXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXX XXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX quads True 3 [(5, 6), (1, 7), (3, 4), (3, 2)] XXXXXXXX XXXXXXX XXXXXXXX XX X XXX XXXXXXXX XXXXXX X XXXXXXXX XXXXXXXX False 2 [(0, 3), (2, 2), (2, 0), (3, 3)] XXX XXXX X X XXX False 2 [(0, 0), (3, 2), (2, 0), (2, 1)] XXX XXXX XX XX X False 2 [(3, 2), (0, 0), (1, 1), (1, 0)] XXX XX XXXX XX X tromino True 3 [(3, 2), (2, 1), (0, 1), (4, 1)] X XXXXXX XXXXXXXX X XXXXXX XX XXXXX X XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX False 2 [(1, 1), (3, 2), (3, 0), (2, 1)] XXXX X XX X XX X X False 4 [(12, 2), (8, 3), (11, 11), (12, 15)] XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXX XXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXX XXXX XX XXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX quads True 4 [(9, 0), (2, 8), (0, 1), (9, 15)] X XXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXX XXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX quads True 3 [(1, 6), (4, 2), (1, 0), (7, 3)] XXXXXXXX XXXXX X XXXXXXXX XXXXXXXX XX XXXXX XXXXXXXX XXXXXXXX XXX XXXX False $
0 コメント:
コメントを投稿