# Advent of Code 2022 - Day 24, in Kotlin - Blizzard Basin

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 24: 'Blizzard Basin'

Posted on

We’ll write another Breadth-First Search to solve today’s puzzle, something we’ve done a few times already. Hey, if it works, let’s use it. I liked the twist in this one that the map changed every step we took. That added an extra challenge to the puzzle. One more Advent of Code 2022 puzzle remains after this one, I hope you’re still having fun. You’ve made it a long way if you’ve come this far!

If you’d rather just view code, the GitHub Repository is here .

Puzzle Input

To store our data today, we’ll ultimately use two classes to do this. One to store the location and direction of each `Blizzard` and one to store the entire `MapState`.

The `Blizzard` data class stores its `location` as a `Point2D` and the `offset` for when it moves (how much to alter `x` and `y` by, which we’ve seen before).

``````// In Day24

private data class Blizzard(val location: Point2D, val offset: Point2D) {}
``````

The `MapState` stores the `boundary` as a `Point2D`, which basically means “where is the lower right corner”. I didn’t want to assume its value, nor did I want to store this at the class level in `Day24`. We also take in a `Set<Blizzard>` to show where all the blizzards currently are for this map. Because we’re going to be asking the `MapState` if a specific point is safe or not later, we’ll convert the `Set<Blizard>` to a `Set<Point2D>` to represent `unsafeSpots` - places there blizzards are. Remembering that blizzards move and more than one may occupy a given spot, we need to know both their specific location and direction, and can’t collapse that down just to a set of points.

``````// In Day24

private data class MapState(val boundary: Point2D, val blizzards: Set<Blizzard>) {
private val unsafeSpots = blizzards.map { it.location }.toSet()

companion object {
fun of(input: List<String>): MapState =
MapState(
Point2D(input.first().lastIndex - 1, input.lastIndex - 1),
input.flatMapIndexed { y, row ->
row.mapIndexedNotNull { x, char ->
when (char) {
'>' -> Blizzard(Point2D(x, y), Point2D(1, 0))
'<' -> Blizzard(Point2D(x, y), Point2D(-1, 0))
'v' -> Blizzard(Point2D(x, y), Point2D(0, 1))
'^' -> Blizzard(Point2D(x, y), Point2D(0, -1))
else -> null
}
}
}.toSet()
)
}
}
``````

As usual, we define an `of` function in the companion object to do the parsing. It’s another `flatMapIndexed` combined with `mapIndexedNotNull` that we’ve seen before.

From here, we can store the `initialMapState`, and parse the `input` for the `start` and `goal` spots.

``````class Day24(input: List<String>) {

private val initialMapState: MapState = MapState.of(input)
private val start: Point2D = Point2D(input.first().indexOfFirst { it == '.' }, 0)
private val goal: Point2D = Point2D(input.last().indexOfFirst { it == '.' }, input.lastIndex)

}
``````

#### ⭐ Day 24, Part 1

The puzzle text can be found here.

We’re going to do a Breadth-First Search to find our way through the maze, which changes every turn. To record our position and the length of the path we’ve taken, we’ll define a `PathAttempt` class which takes the number of `steps` taken, and the `location` we are currently in. It also defines a `next()` function, optionally taking in a `place` to move to. Otherwise, if the caller does not provide a `place`, we’ll use the current `location` to mean “stand still for one turn” (increasing the `steps` but not moving).

``````// In Day24

private data class PathAttempt(val steps: Int, val location: Point2D) {
fun next(place: Point2D = location): PathAttempt =
PathAttempt(steps + 1, place)
}
``````

We’ll need to add some functions to `MapState` as well:

``````// In Day24.MapState

fun isOpen(place: Point2D): Boolean =
place !in unsafeSpots

fun inBounds(place: Point2D): Boolean =
place.x > 0 && place.y > 0 && place.x <= boundary.x && place.y <= boundary.y

fun nextState(): MapState =
copy(blizzards = blizzards.map { it.next(boundary) }.toSet())
``````

The `isOpen` and `isInBounds` functions make sure we’re picking a place on the map that we’re allowed to move to by checking that a blizzard is not currently located there (`isOpen`) and that it is within the border area (`isInBounds`).

The `nextState` function helps us by generating the next `MapState`, moving all of the `Blizzard` objects. Which means we need to add a `next` function to `Blizzard` as well.

``````// In Day24.Blizzard

fun next(boundary: Point2D): Blizzard {
var nextLocation = location + offset
when {
nextLocation.x == 0 -> nextLocation = Point2D(boundary.x, location.y)
nextLocation.x > boundary.x -> nextLocation = Point2D(1, location.y)
nextLocation.y == 0 -> nextLocation = Point2D(location.x, boundary.y)
nextLocation.y > boundary.y -> nextLocation = Point2D(location.x, 1)
}
return copy(location = nextLocation)
}
``````

This function does the boundary checking for a blizzard. If it runs into a wall, it resets the blizzard to the other end of the map. I am assuming here that blizzards cannot go into either the `start` or `goal` spots.

Now we have enough to write our search. It’s basic function should look familiar if you’ve been reading these posts - its a Breadth-First Search, which we’ve used a few times this year for Advent of Code already.

``````// In Day24

private fun solve(
startPlace: Point2D = start,
stopPlace: Point2D = goal,
startState: MapState = initialMapState,
stepsSoFar: Int = 0
): Pair<Int, MapState> {
val mapStates = mutableMapOf(stepsSoFar to startState)
val queue = mutableListOf(PathAttempt(stepsSoFar, startPlace))
val seen = mutableSetOf<PathAttempt>()

while (queue.isNotEmpty()) {
val thisAttempt = queue.removeFirst()
if (thisAttempt !in seen) {
seen += thisAttempt
val nextMapState = mapStates.computeIfAbsent(thisAttempt.steps + 1) { key ->
mapStates.getValue(key - 1).nextState()
}

// Can we just stand still here?

val neighbors = thisAttempt.location.cardinalNeighbors()

// Is one of our neighbors the goal?
if (stopPlace in neighbors) return Pair(thisAttempt.steps + 1, nextMapState)

// Add neighbors that will be open to move to on the next turn.
neighbors
.filter { it == start || (nextMapState.inBounds(it) && nextMapState.isOpen(it)) }
.forEach { neighbor ->
}
}
}
throw IllegalStateException("No path to goal")
}
``````

One thing to notice is that the `solve` function takes in a few arguments, all of them with defaults. This is because Part Two needs to change these things later on, and I didn’t want to explain the refactoring. We take in the `startPlace` and the `stopPlace` indicating where we start and when we stop searching. We’ll take in the `startState` in case we don’t want to start searching the map purely from the puzzle input. We can also initialize the step counter by specify `stepsSoFar`.

Once inside the function, we set up a cache called `mapStates`. Since our work queue will be looking up the `MapState` for a given number of steps over and over, it makes sense to cache these. The `queue` should look familiar - it is a `MutableList` seeded with the initial `PathAttempt` so we have some work to do. And to reduce our workload, we’ll cache states we’ve already considered in `seen`, or we will never run out of work to do and finding our answer will take a very long time.

While our queue `isNotEmpty` it means we still have work to do, so we pick the first item off the `queue` and call it `thisAttempt`. If we’ve seen this state before (same location and step count), we ignore it because we’d be doing duplicate work. Otherwise, we have work to do with this state after adding it to the `seen` cache.

First, we either look up or calculate the `MapState` for the given number of `steps` for the attempt. All states of the same step number are identical. We use this to determine if we can schedule some work of standing still, rather than moving, and do so if we can. Next, we consider our `neighbors`. If one of them is the `goal` we can stop looking and return a `Pair<Int,MapState>`. Why not just return the steps? We need both of these for Part Two.

The last bit of work is to schedule our `neighbors` for evaluation. We do this by including any `neighbor` that is either the `start` position, or is `inBounds` and `isOpen` for us to move to. Anything else we can ignore. We then add the `next` version of `thisAttempt` to the work `queue` so we can evaluate the same thing all over for each of our neighbors.

Eventually, this will return us the optimal path as it evaluates possibilities in ever-increasing lengths.

Now we can `solve` Part One:

``````// In Day24

fun solvePart1(): Int =
solve().first
``````

Star earned! Onward!

#### ⭐ Day 24, Part 2

The puzzle text can be found here.

Forgot your snacks?! Seriously? I’m risking my life around multiple blizzards because you forgot your snacks?! Come on.

Well, now you know why we wrote `sovle` with so many arguments. The way I’ve elected to solve this is to repeat Part One - moving from the `start` to the `goal`. And then moving back from the `goal` to the `start`, ensuring that we start off with the right `MapState` so the blizzards will be in the right places. And finally, once we have the snacks, we can go from the `start` to the `goal` (again - risking our lives) making sure to use the right `MapState`.

``````// In Day24

fun solvePart2(): Int {
val toGoal = solve()
val backToStart = solve(goal, start, toGoal.second, toGoal.first)
val backToGoal = solve(start, goal, backToStart.second, backToStart.first)
return backToGoal.first
}
``````

Star earned! See you tomorrow.

1. Index of All Solutions - All posts and solutions for 2022, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 24
4. Advent of Code - Come join in and do these challenges yourself!