2018-12-20 - A Regular Map
(original .ipynb)
#--------------------------------------------------------------------
# TODO: make sure to use my latest `advent` lib instead of this inline BS
class GrowableGrid():
def __init__(self, start_node):
self.rows = 1
self.cols = 1
self.start_row = 0
self.start_col = 0
self.row = 0
self.col = 0
self.grid = [[start_node]]
self.stack = []
def create_row(self):
return [None] * self.cols
def create_col(self):
return [None] * self.cols
def assert_not_set(self, row, col, node):
existing_node = self.grid[row][col]
if existing_node != node and existing_node is not None:
raise Exception(
f"Trying to insert {node} into (row={row}, col={col})" +
f" but it already contains {self.grid[row][col]}")
def up(self, node):
if self.row == 0:
new_row = self.create_row()
self.grid.insert(0, new_row)
self.rows += 1
self.recalc_positions(1, 0)
self.assert_not_set(self.row-1, self.col, node)
self.grid[self.row-1][self.col] = node
self.row -= 1
def down(self, node):
if self.row == self.rows - 1:
new_row = self.create_row()
self.grid.append(new_row)
self.rows += 1
self.assert_not_set(self.row+1, self.col, node)
self.grid[self.row+1][self.col] = node
self.row += 1
def left(self, node):
if self.col == 0:
for row in self.grid:
row.insert(0, None)
self.recalc_positions(0, 1)
self.cols += 1
self.assert_not_set(self.row, self.col-1, node)
self.grid[self.row][self.col-1] = node
self.col -= 1
def right(self, node):
if self.col == self.cols - 1:
for row in self.grid:
row.append(None)
self.cols += 1
self.assert_not_set(self.row, self.col+1, node)
self.grid[self.row][self.col+1] = node
self.col += 1
def recalc_positions(self, d_row, d_col):
self.row += d_row
self.col += d_col
self.start_row += d_row
self.start_col += d_col
for i in range(len(self.stack)):
row, col = self.stack[i]
self.stack[i] = (row + d_row, col + d_col)
def push_position(self):
self.stack.append((self.row, self.col))
def pop_position(self):
row, col = self.stack.pop()
self.row = row
self.col = col
def peek_position(self):
row, col = self.stack[-1]
self.row = row
self.col = col
def __str__(self):
rs = []
for row in self.grid:
row_str = []
for col in row:
if col:
row_str.append(col)
else:
row_str.append(" ")
rs.append("".join(row_str))
return "\n".join(rs)
def neighbours4(grid, r, c):
"""
Returns the adjacent tiles NOT including diagonals
"""
max_r = len(grid)
max_c = len(grid[0])
candidates = (
(r-1, c), (r+1, c),
(r, c-1), (r, c+1)
)
for maybe_r, maybe_c in candidates:
if maybe_r == r and maybe_c == c:
continue
if maybe_r >= max_r or maybe_r < 0:
continue
if maybe_c >= max_c or maybe_c < 0:
continue
yield (maybe_r, maybe_c)
def expand_grid(i, regex_str, grid):
grid.push_position()
while i < len(regex_str):
c = regex_str[i]
if c == "(":
r, c = (grid.row, grid.col)
i = expand_grid(i+1, regex_str, grid)
grid.row, grid.col = r, c
elif c == ")":
grid.pop_position()
return i
elif c == "|":
grid.peek_position()
else:
if c == "N":
grid.up("-")
grid.up(".")
elif c == "S":
grid.down("-")
grid.down(".")
elif c == "E":
grid.right("|")
grid.right(".")
elif c == "W":
grid.left("|")
grid.left(".")
i += 1
return i
def solve(input_str):
g = GrowableGrid("X")
expand_grid(0, input_str, g)
# make move grid
move_grid = []
for row in g.grid:
move_grid.append([ None for _ in row ])
move_grid[g.start_row][g.start_col] = 0
queue = [(g.start_row, g.start_col)]
doors = 1
while any(queue):
next_queue = []
for r,c in queue:
neighbours = neighbours4(g.grid, r, c)
for nr, nc in neighbours:
if g.grid[nr][nc] in ("-", "|", ".") and move_grid[nr][nc] == None:
dr = nr - r
dc = nc - c
next_queue.append((r + dr, c + dc))
if move_grid[nr][nc] == None or move_grid[nr][nc] > doors:
if g.grid[nr][nc] == ".":
move_grid[nr][nc] = doors
else:
move_grid[nr][nc] = -1
doors += 1
queue = next_queue
print("part 1:", (doors // 2) - 1)
at_least_1k = 0
for r, row in enumerate(g.grid):
for c, col in enumerate(row):
if col == ".":
distance = move_grid[r][c]
if distance//2 >= 1000:
at_least_1k += 1
print("part 2:", at_least_1k)
puzzle_input_str = open("puzzle_input/day20.txt").read()
solve(puzzle_input_str)
part 1: 3755
part 2: 8627