Skip to content

Instantly share code, notes, and snippets.

@huzecong
Created February 18, 2022 05:17
Show Gist options
  • Save huzecong/adf12353adc58c9b59eb314c8cf6437c to your computer and use it in GitHub Desktop.
Save huzecong/adf12353adc58c9b59eb314c8cf6437c to your computer and use it in GitHub Desktop.
A solver for A-Puzzle-A-Day from https://www.thingiverse.com/thing:4876979
# A solver for A-Puzzle-A-Day from https://www.thingiverse.com/thing:4876979
# Solutions are printed with terminal color escape sequences.
from typing import Dict, List, Tuple
import attrs
import numpy as np
import termcolor
def get_raw_board() -> List[List[str]]:
raw_board = [
["Jan", "Feb", "Mar", "Apr", "May", "Jun", ""],
["Jul", "Aug", "Sep", "Oct", "Nov", "Dec", ""],
list(map(str, range(1, 7 + 1))),
list(map(str, range(8, 14 + 1))),
list(map(str, range(15, 21 + 1))),
list(map(str, range(22, 28 + 1))),
["29", "30", "31", "", "", "", ""],
]
assert all(len(row) == 7 for row in raw_board)
return raw_board
def get_board(*empty_cells: str) -> np.ndarray:
assert len(empty_cells) == 2
raw_board = get_raw_board()
board = np.array(
[[cell in {"", *empty_cells} for cell in row] for row in raw_board]
)
return board
def first_empty(arr: np.ndarray) -> Tuple[int, int]:
assert arr.ndim == 2
for i in range(arr.shape[0]):
for j in range(arr.shape[1]):
if not arr[i, j]:
return (i, j)
assert False
@attrs.frozen()
class Block:
tiles: np.ndarray
offset: Tuple[int, int] = (0, 0)
@property
def width(self) -> int:
return self.tiles.shape[1]
@property
def height(self) -> int:
return self.tiles.shape[0]
def get_blocks() -> List[List[Block]]:
_blocks = {
2: """
X.X XXX XX. X... .X.. XX..
XXX XXX XXX XXXX XXXX .XXX
""",
3: """
X.. XX.
X.. .X.
XXX .XX
""",
}
blocks = []
for string in _blocks.values():
parts = [line.split() for line in string.strip().splitlines()]
for lines in zip(*parts):
block = np.array([[ch == "X" for ch in line] for line in lines])
variants = []
for _ in range(2):
for _ in range(4):
block = np.rot90(block)
if all(not np.array_equal(x, block) for x in variants):
variants.append(block)
block = np.fliplr(block)
blocks.append(
[Block(tiles=block, offset=first_empty(~block)) for block in variants]
)
return blocks
@attrs.frozen()
class BlockPosition:
x: int
y: int
variant: int
def repr_solution(
blocks: List[List[Block]],
block_positions: Dict[int, BlockPosition],
) -> str:
assert set(block_positions.keys()) == set(range(len(blocks)))
raw_board = get_raw_board()
raw_board = [[cell[:2] if cell else " " for cell in row] for row in raw_board]
final_board = np.array(raw_board, dtype=np.object)
for idx, pos in block_positions.items():
block = blocks[idx][pos.variant]
index = np.index_exp[
pos.x : (pos.x + block.height), pos.y : (pos.y + block.width)
]
label = termcolor.colored(" ", on_color=list(termcolor.HIGHLIGHTS)[idx])
final_board[index] = np.where(block.tiles, label, final_board[index])
lines = ["|" + "".join(row) + "|" for row in final_board]
separator = "--" * (final_board.shape[1] + 1)
return "\n".join([separator, *lines, separator])
def solve(cell1: str, cell2: str):
board = get_board(cell1, cell2) # false -> cell that can be placed
height, width = board.shape
blocks = get_blocks()
solutions: List[Dict[int, BlockPosition]] = []
block_positions: Dict[int, BlockPosition] = {}
count = 0
def dfs(depth: int) -> None:
if depth >= len(blocks):
assert set(block_positions.keys()) == set(range(len(blocks)))
solutions.append(block_positions.copy())
nonlocal count
count += 1
print(f"Solution {count}:")
print(repr_solution(blocks, block_positions))
return
# Find first empty spot.
first_x, first_y = first_empty(board)
for block_id, block_variants in enumerate(blocks):
if block_id in block_positions:
continue
for variant_id, block in enumerate(block_variants):
x = first_x - block.offset[0]
y = first_y - block.offset[1]
if not (
0 <= x <= height - block.height and 0 <= y <= width - block.width
):
continue
index = np.index_exp[x : (x + block.height), y : (y + block.width)]
if np.any(board[index] & block.tiles):
continue
board[index] |= block.tiles
block_positions[block_id] = BlockPosition(x, y, variant_id)
dfs(depth + 1)
del block_positions[block_id]
board[index] &= ~block.tiles
dfs(0)
print(f"{count} solutions")
if __name__ == "__main__":
solve("Feb", "18")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment