2017-12-21 - Fractal Art
(original .ipynb)
%%time
# printing the time because apparently many other people's solutions to part 2 were slow
# but mine is relatively speedy
puzzle_input_str = open("puzzle_input/day21.txt").read()
test_input_str = """../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#"""
start_pattern = [
list(".#."),
list("..#"),
list("###")
]
def rotations_2x2(grid, rotations=4):
a, b = grid[0]
d, c = grid[1]
new_grid = [
[d, a],
[c, b]
]
yield new_grid
if rotations > 0:
yield from rotations_2x2(new_grid, rotations-1)
def rotations_3x3(grid, rotations=3):
yield grid
a, b, c = grid[0]
h, x, d = grid[1]
g, f, e = grid[2]
new_grid = [
[g, h, a],
[f, x, b],
[e, d, c],
]
if rotations > 0:
yield from rotations_3x3(new_grid, rotations-1)
def flips_2x2(grid):
r1, r2 = grid
yield grid
yield [r2, r1]
yield [r1[::-1], r2[::-1]]
def flips_3x3(grid):
r1, r2, r3 = grid
yield grid
yield [r3, r2, r1]
yield [r1[::-1], r2[::-1], r3[::-1]]
def combinations_2x2(base_grid):
yield base_grid
for grid in flips_2x2(base_grid):
yield from rotations_2x2(grid)
def combinations_3x3(base_grid):
yield base_grid
for grid in flips_3x3(base_grid):
yield from rotations_3x3(grid)
def combinations(base_grid):
if len(base_grid[0]) == 2:
return combinations_2x2(base_grid)
elif len(base_grid[0]) == 3:
return combinations_3x3(base_grid)
def stringify(grid):
return "".join(
"".join(row) for row in grid
)
def parse_rules(rules_str):
rule_lines = rules_str.strip().split("\n")
rules = {}
for rule_line in rule_lines:
raw_pattern, raw_replacement = rule_line.split(" => ")
base_pattern = raw_pattern.split("/")
replacement = raw_replacement.split("/")
for pattern in combinations(base_pattern):
rules[stringify(pattern)] = replacement
return rules
def subgrid_2x2(grid, r, c):
base_r = 2 * r
base_c = 2 * c
return [
grid[base_r + 0][base_c:base_c+2],
grid[base_r + 1][base_c:base_c+2]
]
def subgrid_3x3(grid, r, c):
base_r = 3 * r
base_c = 3 * c
return [
grid[base_r + 0][base_c:base_c+3],
grid[base_r + 1][base_c:base_c+3],
grid[base_r + 2][base_c:base_c+3]
]
def enhance_grid_base(grid, rules, subgrid_func, n):
size = len(grid) // n
new_grid = []
for r in range(size):
new_row = []
for c in range(size):
subgrid = subgrid_func(grid, r, c)
pattern = stringify(subgrid)
if pattern in rules:
new_row.append(rules[pattern])
else:
raise Exception(f"{pattern} does not exist in rules")
new_grid.append(new_row)
return flatten(new_grid)
def enhance_grid(grid, rules):
if len(grid) % 2 == 0:
return enhance_grid_base(grid, rules, subgrid_2x2, 2)
if len(grid) % 3 == 0:
return enhance_grid_base(grid, rules, subgrid_3x3, 3)
raise Exception("The grid is a weird size")
def flatten(grid):
assert len(grid) == len(grid[0])
new_grid = []
for row in grid:
new_rows = [""] * len(row[0])
for subgrid in row:
for i, subgrid_row in enumerate(subgrid):
new_rows[i] += subgrid_row
new_grid += new_rows
return new_grid
def count_on(pattern):
on = 0
for row in pattern:
on += sum(1 for c in row if c != ".")
return on
def solve(input_str, iterations):
rules = parse_rules(input_str)
pattern = start_pattern
while iterations > 0:
pattern = enhance_grid(pattern, rules)
iterations -= 1
return count_on(pattern)
assert 12 == solve(test_input_str, 2)
print("part one:", solve(puzzle_input_str, 5))
print("part two:", solve(puzzle_input_str, 18))
part one: 197
part two: 3081737
CPU times: user 3.36 s, sys: 23.8 ms, total: 3.39 s
Wall time: 3.45 s