2018年12月11日火曜日

開発環境

問題解決の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 コメント:

コメントを投稿

関連コンテンツ