109 lines
2.6 KiB
Python
109 lines
2.6 KiB
Python
from copy import copy
|
|
from typing import Optional, Tuple
|
|
|
|
|
|
CACHE = {}
|
|
EMPTY = '⬛'
|
|
FIELDS = ['🔴', '🟠', '🟡', '🟢', '🔵', '🟣', '⚪', '🟤', '⭐']
|
|
|
|
|
|
# We use [row, col] indexing.
|
|
BLOCKS = [
|
|
((0, 0), (0, 1), (0, 2)), # dark blue
|
|
((0, 0), (1, 0), (2, 0)), # black
|
|
((0, 0), (0, 1), (1, 0)), # red
|
|
((0, 0), (0, 1), (1, 1)), # green
|
|
((0, 0), (1, 0), (1, 1)), # blue
|
|
((0, 0), (1, 0), (1, -1)), # orange
|
|
]
|
|
|
|
|
|
class Field:
|
|
|
|
def __init__(self, N_COLS, N_ROWS):
|
|
self.N_COLS = N_COLS
|
|
self.N_ROWS = N_ROWS
|
|
self.state = 0
|
|
|
|
def __hash__(self):
|
|
return hash(self.state)
|
|
|
|
def get_first_empty(self) -> Optional[Tuple[int, int]]:
|
|
for row in range(self.N_ROWS):
|
|
for col in range(self.N_COLS):
|
|
if self.is_empty(row, col):
|
|
return (row, col)
|
|
return None
|
|
|
|
def is_empty(self, row: int, col: int) -> bool:
|
|
index = row * self.N_COLS + col
|
|
result = not bool(self.state & (1 << index))
|
|
return result
|
|
|
|
def set(self, row: int, col: int):
|
|
index = row * self.N_COLS + col
|
|
self.state |= (1 << index)
|
|
|
|
def __getitem__(self, row: int):
|
|
return [self.is_empty(row, col) for col in range(self.N_COLS)]
|
|
|
|
def print(self):
|
|
for row in range(self.N_ROWS):
|
|
row_str = ""
|
|
for col in range(self.N_COLS):
|
|
row_str += '⬛' if self.is_empty(row, col) else '⚪'
|
|
print(row_str)
|
|
|
|
|
|
def fits(field, block, coord):
|
|
N_ROWS = field.N_ROWS
|
|
N_COLS = field.N_COLS
|
|
|
|
for rel_coord in block:
|
|
abs_row = coord[0] + rel_coord[0]
|
|
abs_col = coord[1] + rel_coord[1]
|
|
|
|
if abs_row < 0 or abs_col < 0 or abs_row >= N_ROWS or abs_col >= N_COLS:
|
|
return None
|
|
|
|
if not field.is_empty(abs_row, abs_col):
|
|
return None
|
|
|
|
new_field = copy(field)
|
|
for rel_coord in block:
|
|
abs_row = coord[0] + rel_coord[0]
|
|
abs_col = coord[1] + rel_coord[1]
|
|
new_field.set(abs_row, abs_col)
|
|
|
|
return new_field
|
|
|
|
|
|
def count(field):
|
|
global CACHE
|
|
|
|
if hash(field) in CACHE:
|
|
return CACHE[hash(field)]
|
|
|
|
first_empty = field.get_first_empty()
|
|
if first_empty is None:
|
|
return 1
|
|
|
|
result = 0
|
|
for block in BLOCKS:
|
|
if (new_field := fits(field, block, first_empty)) is not None:
|
|
result += count(new_field)
|
|
|
|
CACHE[hash(field)] = result
|
|
return result
|
|
|
|
|
|
def euler_161():
|
|
return count(Field(9, 12))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_161()
|
|
print("e161.py: " + str(solution))
|
|
assert(solution == 20574308184277971)
|
|
|