@xavdid does Advent of Code

Blizzard Basin

Published: 2023-07-28 Original Prompt

Part 1

Whenever you see “fastest way to do X”, it’s a good bet we’re going to use Dijkstra’s algorithm like we did in day 12. I’ve covered this a number of times before, so I’ll focus on what makes this problem unique.

First up, input! I started with a little Blizzard class. It needs to do 2 things:

That’s easy enough using the same add-position-to-offset approach we’ve done before:

from dataclasses import dataclass, field
from typing import Literal
GridPoint = tuple[int, int]
DIRECTIONS = Literal["<", ">", "v", "^"]
OFFSETS: dict[DIRECTIONS, GridPoint] = {
"<": (0, -1),
">": (0, 1),
"v": (1, 0),
"^": (-1, 0),
class Blizzard:
direction: DIRECTIONS
position: GridPoint
max_row: int = field(repr=False) # hidden from print statements
max_col: int = field(repr=False) # hidden from print statements
def move(self):
offset_row, offset_col = OFFSETS[self.direction]
self.position = (
(self.position[0] + offset_row) % self.max_row,
(self.position[1] + offset_col) % self.max_col,

A blizzard only ever moves in one direction, so its moves are predictable. We can also supply the grid size and each blizzard will handling wrapping around the map at the right time.

Next, the actual grid. Rather than take the walls into account for the size of the grid, we’ll ignore them and tread the start and end points as special cases. The grid parsing is therefore pretty straightforward:

class Grid:
blizzards: list[Blizzard] = []
def __init__(self, raw_grid: str) -> None:
rows = raw_grid.split("\n")
self.max_rows = len(rows) - 2
self.max_cols = len(rows[0]) - 2
for row, line in enumerate(rows[1:-1]):
for col, c in enumerate(line[1:-1]):
if c not in OFFSETS:
Blizzard(c, (row, col), self.max_rows, self.max_cols)

We have our list of blizzards and they’re each able to move independently. They’re on the (row, col) system that should be familiar (where (0, 0) is in the top left).

Next, let’s consider our actual algorithm. Normally in Dijkstra’s you have a set of visited nodes and a queue of sortable (cost, node) tuples. You traditionally only ever visit a node once, so you don’t need any other info in the visited set. But to dodge blizzards, you may be retracing your steps (as shown in the example, where you’re on (0, 0) in minutes 1 and 4). So we must track both the timestamp and the location because (1, (0, 0)) and (4, (0, 0)) are distinct. This begets a new issue: time travel.

On an unchanging graph, you always know who your neighbors are. When you visit a node, it’s easy to add the valid next steps: they are each neighbor at time + 1. But our graph is far from static, so the distinct points (1, (0, 0)) and (4, (0, 0)) have different sets of valid neighbors. This means that instead of maintaining a single state that shows all neighbors right now, we have to be able to look up neighbors for a point at a given timestamp. This means we’ll need to track all states, not just the “current” one.

Before we can write that code, let’s think about what data to store. We need to store the blizzard objects, since they know which direction to move when asked. But, there’s nothing in the prompt about handling spaces where there are 2+ blizzards differently. At at given timestamp, we need to know the set of points which are occupied.

Will all that understanding in hand, we’re ready to write some code:

from heapq import heappop, heappush
Step = tuple[int, GridPoint]
class Grid:
# the occupied points at a moment in time
states: dict[int, set[GridPoint]] = {}
steps_taken = 0
def __init__(self, raw_grid: str) -> None:
# after grid setup, get initial set of points
self.states[0] = {b.position for b in self.blizzards}
def state_at(self, time: int) -> set[GridPoint]:
while time not in self.states:
self.steps_taken += 1
for b in self.blizzards:
self.states[self.steps_taken] = {b.position for b in self.blizzards}
return self.states[time]
def run(self) -> int:
start_point: GridPoint = (-1, -1)
# time and expedition location
queue: list[Step] = [(0, start_point)]
visited: set[Step] = set()
while queue:
now = heappop(queue)
if now in visited:
t, pos = now
# gut check
assert (
pos not in self.states[t]
), f"Invalid! Occupied tile {pos} at time {t} at the same time a storm did"
# TODO: add items to queue
# something will hopefully return a time (our answer)
raise ValueError("no solution found!")

That’s a lot of code, but nothing to crazy! We:

Now, neighbor selection. In each case, we’re going to look at state_at[time + 1] and add points to the queue if they’re not in that set. We’ll re-use the neighbors function to find current in-bound neighbors for each grid square. We also need special cases for the beginning and end (since those are outside the grid and won’t be seen by neighbors). And of course, the ability to wait in place.

Here’s what that all looks like:

class Grid:
def __init__(self, raw_grid: str) -> None:
# the grid point _next_ to the exit, aka the bottom-right corner
self.target: GridPoint = self.max_rows - 1, self.max_cols - 1
def run(self) -> int:
while queue:
next_t = t + 1
# if we're next to the exit, we can always move there (and are done)
if pos == self.target:
return next_t
next_state = self.state_at(next_t)
# from the starting position, there are only 2 options (neither of which could be visited yet)
if pos == start_point:
# we can _always_ wait on the starting point
heappush(queue, (next_t, start_point))
# maybe step out into the grid
if (zeroes := (0, 0)) not in next_state:
heappush(queue, (next_t, zeroes))
# nothing else to check, these are our options
# otherwise, we must be in the grid somewhere, so we can only move to neighbors or wait
# (or the ending, as covered above)
# try waiting
if pos not in next_state:
heappush(queue, (next_t, pos))
# try each orthogonal neighbor
for next_move in neighbors(
max_x_size=self.max_rows - 1,
max_y_size=self.max_cols - 1,
# don't move where there'll be a blizzard
if next_move in next_state:
# don't re-add points we've tried
if (potential_state := (next_t, next_move)) in visited:
# otherwise, give it a shot!
heappush(queue, potential_state)

Nothing too unusual here now that setup is covered. We make a bunch of checks against the points in the next state. We also use a lot of args for the neighbors function to constrain our checks to 0 <= X <= max_X (no looping or negatives). We have special cases for the start and end, but everything else is pretty standard. That’s a wrap on part 1!

Part 2

Before, we were always moving from (0, 0) (adjacent to our start placeholder, (-1, -1)) to the bottom-right corner (the max grid size). Now we’ll have to make that dynamic (along with the starting time). Our Grid will still keep track of all the states between runs, so we’re in pretty good shape. The biggest change is handling what point is considered adjacent to the starting point. We can keep using our starter placeholder, but we’ll have to be a little more clever with that specific neighbor calculation.

Here’s the updates we need to make:

class Grid:
top_left_point: GridPoint = 0, 0
def __init__(self, raw_grid: str) -> None:
self.bottom_right_point: GridPoint = self.max_rows - 1, self.max_cols - 1 # renamed
# updated args
def run(self, start_time: int, end_point: GridPoint) -> int:
assert end_point in {self.top_left_point, self.bottom_right_point}
queue: list[Step] = [(start_time, start_point)]
while queue:
# if we're next to the exit, we can always move there
if pos == end_point:
return next_t
if pos == start_point:
# the point you can move to from the start varies based on where you're headed
if (
start_neighbor := self.top_left_point
if end_point == self.bottom_right_point
else self.bottom_right_point
) not in next_state:
heappush(queue, (next_t, start_neighbor))

The assert is important to ensure the staring point neighbor check below works. If there were more cases, the assert would fail and we could ensure we used something besides a ternary check.

Running the solution is pretty straightforward too:

class Solution(TextSolution):
def solve(self) -> tuple[int, int]:
g = Grid(self.input)
end_of_first_crossing = g.run(0, g.bottom_right_point)
end_of_return_trip = g.run(end_of_first_crossing, g.top_left_point)
end_of_second_crossing = g.run(end_of_return_trip, g.bottom_right_point)
return end_of_first_crossing, end_of_second_crossing

By being able to start at any point in time and with a dynamic destination, we can run our original algorithm forwards and backwards. Do that 3 times and we have our answer(s)!