Page Navigation
Problem Intro
This one was tough to get right.
We’ve reached a valley that we need to cross. The valley is full of horizontal and vertical blizzards. Our input data represents the valley, and it looks something like this:
#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
In this map:
- Locations marked
#are walls of the valley. - Locations marked
.are clear ground that we are allowed to occupy. - Locations marked with an arrow contain a blizzard. Each minute, every blizzard moves one unit in the direction it is pointing. All blizzards move simultaneously.
- If a blizzard reaches the boundary of the valley, it wraps around and reappears the other side, pointing in the same direction.
- We start in the clear ground
.in the top left. - We need to get to the clear ground
.in the bottom right.
Part 1
What is the fewest number of minutes required to avoid the blizzards and reach the goal?
My strategy is as follows:
- Create a MapState class that represents the current location of all the blizzards, and which knows how to return the blizzard state in the subsequent minute.
- Perform a BFS to calculate the shortest route through the ever-changing blizzard map.
First, I’ll use a Point dataclass, as I often do:
@dataclass(frozen=True)
class Point():
""" Point x,y which knows how to add another point, and how to return all adjacent (non-diag) points """
x: int
y: int
def __add__(self, other) -> Point:
""" Add other point to this point, returning new point vector """
return Point(self.x + other.x, self.y + other.y)
def adjacent_points(self) -> set[Point]:
return set(self+vector for vector in VECTORS.values())
def __repr__(self):
return f"P({self.x},{self.y})"
This Point class knows how to add a vector to return a new Point, and it uses this addition method to return all of it’s adjacent points (excluding diagonals), i.e. by adding each of four adjacent vectors to itself.
Now I define the VECTORS dictionary:
VECTORS = {
'>': Point(1, 0),
'v': Point(0, 1),
'<': Point(-1, 0),
'^': Point(0, -1)
}
Now I create a MapState() class:
class MapState():
""" Store location of blizzards, grid bounds, start, goal, and time. """
def __init__(self, blizzards: dict, grid_dims: tuple, start: Point, goal: Point, t: int) -> None:
self._blizzards: dict[Point, list] = blizzards
self._width = grid_dims[0]
self._height = grid_dims[1]
self._start = start
self._goal = goal
self._time = t
@classmethod
def init_from_grid(cls, grid_input: list[str]):
""" Create a new MapState using an input grid """
grid: list[str] = grid_input
blizzards = defaultdict(list)
for y, row in enumerate(grid[1:-1]): # ignore top and bottom
for x, col in enumerate(row[1:-1]): # ignore left and right
point = Point(x,y)
if col in VECTORS:
blizzards[point].append(col)
height = len(grid) - 2
width = len(grid[0]) - 2
start = Point(0, -1) # 1 above top grid row
goal = Point(width-1, height) # 1 below bottom grid row
return MapState(blizzards, (width, height), start=start, goal=goal, t=0)
@property
def start(self) -> Point:
return self._start
@start.setter
def start(self, point: Point):
self._start = point
@property
def time(self) -> int:
return self._time
@property
def goal(self) -> Point:
return self._goal
@goal.setter
def goal(self, point):
self._goal = point
def next_blizzard_state(self) -> MapState:
""" Move blizzards to achieve next blizzard state. There is only one possible next blizzard state """
next_blizzards = defaultdict(list)
for loc, blizzards_here in self._blizzards.items():
for current_bliz in blizzards_here:
next_bliz_x = (loc + VECTORS[current_bliz]).x % self._width
next_bliz_y = (loc + VECTORS[current_bliz]).y % self._height
next_blizzards[Point(next_bliz_x, next_bliz_y)].append(current_bliz)
return MapState(next_blizzards, (self._width, self._height), self._start, self._goal, self.time+1)
def is_valid(self, point: Point) -> bool:
""" Check if the specified point is an allowed position in the current blizzard state. """
if point in (self._start, self._goal): # out of bounds, but allowed
return True
# out of bounds
if not (0 <= point.x < self._width):
return False
if not (0 <= point.y < self._height):
return False
if point in (self._blizzards):
return False
return True
def __str__(self) -> str:
lines = []
for y in range(0, self._height):
line = ""
for x in range (0, self._width):
loc = Point(x,y)
if loc in self._blizzards:
blizzards_here = self._blizzards[loc]
how_many_blizzards = len(blizzards_here)
if how_many_blizzards == 1: # one blizzard here
line += next(bliz for bliz in blizzards_here)
elif how_many_blizzards > 1: # more than one blizzard here
line += str(how_many_blizzards)
else:
line += '.'
lines.append(line)
return ("\n".join(lines) +
f"\nTime={self.time}, Hash={hash(self)}")
def __repr__(self) -> str:
return f"Time={self.time}, Hash={hash(self)}"
- We create our first
MapStateobject using aninit_from_grid()classmethod, passing in grid data which we read from the input data.- This creates a defaultdict(list) where any blizzard locations are the keys, and the values are all the blizzards found at this location.
- Note that when we read in the grid data, we ignore the four edges, which are made up of walls,
#. - We store the current width and height of the grid, without its walls.
- We store our
startandgoallocations. - We set the
_timeto0in this first state.
- The class includes a
next_blizzard_state()method. It works by:- Creating a new
defaultdictto store the blizzards in the next state. - Iterates through all the current blizzard locations, and adds the appropriate vector (depending on the direction of each blizzard) to the current location, to populate the new
defaultdict. - Instantiates a new
MapState, using this new dict of blizzards, incrementing the time by1minute, but otherwise leaving the currentMapStateattributes untouched.
- Creating a new
- It includes an
is_valid()method, which allows us to check if any given location is an allowed location in thisMapState. To be valid, the location must be within the current bounds, and must not contain any blizzards. We also allow the_startand_goallocations.
We can now test our blizzard MapState is able to iterate, as follows:
def test_blizzard_states(init_state: MapState, iterations: int):
state = init_state
for _ in range(iterations):
print(state, end="\n\n")
state = state.next_blizzard_state()
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
state = MapState.init_from_grid(data)
test_blizzard_states(state, 10)
The output looks like this:
>>.<^<
.<..<<
>v.><>
<^v^^>
Time=0
.>3.<.
<..<<.
>2.22.
>v..^<
Time=1
.2>2..
.^22^<
.>2.^>
.>..<.
Time=2
<^<22.
.2<.2.
><2>..
..><..
Time=3
.<..22
<<.<..
<2.>>.
.^22^.
Time=4
2.v.<>
<.<..<
.^>^22
.2..2.
Time=5
>2.<.<
.2v^2<
>..>2>
<....>
Time=6
.22^2.
<v.<2.
>>v<>.
>....<
Time=7
.<>2^.
..<<.<
.22..>
.2v^2.
Time=8
<.2>>.
.<<.<.
>2>2^.
.v><^.
Time=9
Good, that looks correct!
Now we’re ready to implement the BFS.
def bfs(state: MapState) -> MapState:
""" BFS, but we're allowed to backtrack.
Our frontier should only contain the current set of allowed next locations. """
start = state.start
goal = state.goal
# Use a set because the many neighbours of the points in our frontier may be the same position
# We don't want to explore the same location twice IN THE SAME ITERATION
frontier = {start}
while goal not in frontier:
state = state.next_blizzard_state()
# reset frontier because we can revisit locations we've been to before
frontier = set(explore_frontier(state, frontier))
return state
def explore_frontier(current_state, frontier):
""" Generator that returns all valid next locations with current blizzard state
from all locations in the frontier. """
for loc in frontier:
for neighbour in loc.adjacent_points():
if current_state.is_valid(neighbour):
yield neighbour
if current_state.is_valid(loc): # staying still may be a valid move
yield loc
It works like this:
- First, we call the
bfs()function, passing in the initialMapState. - Extract the
startandgoallocations from thisMapState. - Create a
setto be ourfrontier, and addstartto it. - Now enter a
whileloop that only exits when we’ve found thegoal. In this loop:- Get the next
MapState, i.e. where the blizzards will be in the subsequent minute. - Explore all the locations in our
frontier. (For the first iteration, this will only bestart.) - For each location in the
frontier, determine which locations are valid next moves. This is a maximum of five locations: the current locations, plus its four neighbour points. For each of these candidate locations, check if the locationis_valid()for the currentMapState. - Create a new
frontierfrom these valid locations.
- Get the next
Note that unlike a typical BFS, we’re allowed to backtrack here. That’s why we’re not storing all previous visited points in an explored set, as we would typically do. Instead, we’re creating a new frontier set for each new MapState and the associated current position.
Finally, we can solve for Part 1, like this:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
# Part 1
state = MapState.init_from_grid(data)
state = bfs(state)
print(f"Part 1: {state.time}")
Part 2
Oh no! One of the elves left his snacks at the entrance to the valley. So we need to go back to the start, retrieve them, and then journey back to the goal. Thus:
What is the fewest number of minutes required to reach the goal, go back to the start, then reach the goal again?
Our total journey is now made up of three legs:
- From start to goal.
- From goal back to start.
- From start to goal again.
But throughout, the blizzards are changing.
This is pretty trivial for us to solve. We just need to continue where we left off, with leg 1 already complete. We just need to:
- Swap the locations of
startandgoal, and repeat the BFS. - Swap the locations back again, and repeat the BFS again.
In fact, we just need to amend our main() function to look like this:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
# Part 1
leg_times = []
state = MapState.init_from_grid(data)
state = bfs(state)
leg_times.append(state.time)
print(f"Part 1: Leg time={leg_times[0]}")
# Part 2
# First, swap goal and start, since we need to go back to the start
state.start, state.goal = state.goal, state.start
state = bfs(state)
leg_times.append(state.time - sum(leg_times))
print(f"Part 2: Return leg time={leg_times[-1]}")
state.start, state.goal = state.goal, state.start
state = bfs(state)
leg_times.append(state.time - sum(leg_times))
print(f"Part 2: Last leg time={leg_times[-1]}")
print(f"Part 2: Total time={sum(leg_times)}")
Results
Here’s the final code:
from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Point():
""" Point x,y which knows how to add another point, and how to return all adjacent (non-diag) points """
x: int
y: int
def __add__(self, other) -> Point:
""" Add other point to this point, returning new point vector """
return Point(self.x + other.x, self.y + other.y)
def adjacent_points(self) -> set[Point]:
return set(self+vector for vector in VECTORS.values())
def __repr__(self):
return f"P({self.x},{self.y})"
VECTORS = {
'>': Point(1, 0),
'v': Point(0, 1),
'<': Point(-1, 0),
'^': Point(0, -1)
}
class MapState():
""" Store location of blizzards, grid bounds, start, goal, and time. """
def __init__(self, blizzards: dict, grid_dims: tuple, start: Point, goal: Point, t: int) -> None:
self._blizzards: dict[Point, list] = blizzards
self._width = grid_dims[0]
self._height = grid_dims[1]
self._start = start
self._goal = goal
self._time = t
@classmethod
def init_from_grid(cls, grid_input: list[str]):
""" Create a new MapState using an input grid """
grid: list[str] = grid_input
blizzards = defaultdict(list)
for y, row in enumerate(grid[1:-1]): # ignore top and bottom
for x, col in enumerate(row[1:-1]): # ignore left and right
point = Point(x,y)
if col in VECTORS:
blizzards[point].append(col)
height = len(grid) - 2
width = len(grid[0]) - 2
start = Point(0, -1) # 1 above top grid row
goal = Point(width-1, height) # 1 below bottom grid row
return MapState(blizzards, (width, height), start=start, goal=goal, t=0)
@property
def start(self) -> Point:
return self._start
@start.setter
def start(self, point: Point):
self._start = point
@property
def time(self) -> int:
return self._time
@property
def goal(self) -> Point:
return self._goal
@goal.setter
def goal(self, point):
self._goal = point
def next_blizzard_state(self) -> MapState:
""" Move blizzards to achieve next blizzard state. There is only one possible next blizzard state """
next_blizzards = defaultdict(list)
for loc, blizzards_here in self._blizzards.items():
for current_bliz in blizzards_here:
next_bliz_x = (loc + VECTORS[current_bliz]).x % self._width
next_bliz_y = (loc + VECTORS[current_bliz]).y % self._height
next_blizzards[Point(next_bliz_x, next_bliz_y)].append(current_bliz)
return MapState(next_blizzards, (self._width, self._height), self._start, self._goal, self.time+1)
def is_valid(self, point: Point) -> bool:
""" Check if the specified point is an allowed position in the current blizzard state. """
if point in (self._start, self._goal): # out of bounds, but allowed
return True
# out of bounds
if not (0 <= point.x < self._width):
return False
if not (0 <= point.y < self._height):
return False
if point in (self._blizzards):
return False
return True
def __str__(self) -> str:
lines = []
for y in range(0, self._height):
line = ""
for x in range (0, self._width):
loc = Point(x,y)
if loc in self._blizzards:
blizzards_here = self._blizzards[loc]
how_many_blizzards = len(blizzards_here)
if how_many_blizzards == 1: # one blizzard here
line += next(bliz for bliz in blizzards_here)
elif how_many_blizzards > 1: # more than one blizzard here
line += str(how_many_blizzards)
else:
line += '.'
lines.append(line)
return ("\n".join(lines) + f"\nTime={self.time}")
def __repr__(self) -> str:
return f"Time={self.time}, Hash={hash(self)}"
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
# Part 1
leg_times = []
state = MapState.init_from_grid(data)
state = bfs(state)
leg_times.append(state.time)
print(f"Part 1: Leg time={leg_times[0]}")
# Part 2
# First, swap goal and start, since we need to go back to the start
state.start, state.goal = state.goal, state.start
state = bfs(state)
leg_times.append(state.time - sum(leg_times))
print(f"Part 2: Return leg time={leg_times[-1]}")
state.start, state.goal = state.goal, state.start
state = bfs(state)
leg_times.append(state.time - sum(leg_times))
print(f"Part 2: Last leg time={leg_times[-1]}")
print(f"Part 2: Total time={sum(leg_times)}")
def test_blizzard_states(init_state: MapState, iterations: int):
state = init_state
for _ in range(iterations):
print(state, end="\n\n")
state = state.next_blizzard_state()
def bfs(state: MapState) -> MapState:
""" BFS, but we're allowed to backtrack.
Our frontier should only contain the current set of allowed next locations. """
start = state.start
goal = state.goal
# Use a set because the many neighbours of the points in our frontier may be the same position
# We don't want to explore the same location twice IN THE SAME ITERATION
frontier = {start}
while goal not in frontier:
state = state.next_blizzard_state()
# reset frontier because we can revisit locations we've been to before
frontier = set(explore_frontier(state, frontier))
return state
def explore_frontier(current_state, frontier):
""" Generator that returns all valid next locations with current blizzard state
from all locations in the frontier. """
for loc in frontier:
for neighbour in loc.adjacent_points():
if current_state.is_valid(neighbour):
yield neighbour
if current_state.is_valid(loc): # staying still may be a valid move
yield loc
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
Here’s the output with my real input data:
Part 1: Leg time=286
Part 2: Return leg time=255
Part 2: Last leg time=279
Part 2: Total time=820
Execution time: 6.9212 seconds