Advent of Code 2022 - Day 24

Day 24: Blizzard Basin

Useful Links

‹›

Concepts and Packages Demonstrated

defaultdict dataclass Factory method Breadth First Search (BFS)

Problem Intro
Part 1
Part 2
Results

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 MapState object using an init_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 start and goal locations.
- We set the _time to 0 in this first state.
The class includes a next_blizzard_state() method. It works by:
- Creating a new defaultdict to 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 by 1 minute, but otherwise leaving the current MapState attributes untouched.
It includes an is_valid() method, which allows us to check if any given location is an allowed location in this MapState. To be valid, the location must be within the current bounds, and must not contain any blizzards. We also allow the _start and _goal locations.

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 initial MapState.
Extract the start and goal locations from this MapState.
Create a set to be our frontier, and add start to it.
Now enter a while loop that only exits when we’ve found the goal. 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 be start.)
- 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 location is_valid() for the current MapState.
- Create a new frontier from these valid locations.

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 start and goal, 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

‹›

Learning Python with Advent of Code Walkthroughs