Advent of Code 2022 - Day 24, in Kotlin - Blizzard Basin • Todd Ginsberg

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?
            if (nextMapState.isOpen(thisAttempt.location)) queue.add(thisAttempt.next())

            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 ->
                    queue.add(thisAttempt.next(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.

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading