Advent of Code 2024 - Day 16, in Kotlin - Reindeer Maze
Kotlin solutions to parts 1 and 2 of Advent of Code 2024, Day 16: 'Reindeer Maze'
Have I ever mentioned how much I like these kind of maze puzzles? For some reason, I always look forward to them during Advent of Code season. While I didn’t write a single solution to both parts of today’s puzzle, I think the solutions are good at highlighting the various concerns with finding a single best cost and all best costs, two types of work you’d use a solution like this for.
If you’d rather just view the code, my GitHub Repository is here.
Puzzle Input
We will take the input (called maze today, not input as usual) as a List<String>. We won’t need to modify the maze in any way, so we won’t do any parsing. We will, however, pick out the start and end points from the maze.
class Day16(private val maze: List<String>) {
private val start: Point2D = maze.find('S')
private val end: Point2D = maze.find('E')
}
The find function takes a target and goes through all of the rows and columns, returning the first instance of the target. Yesterday we wrote a similar function that returned all instances. Perhaps we should put this in Extensions.kt?
// In Day16
private fun List<String>.find(target: Char) =
flatMapIndexed { y, row ->
row.mapIndexed { x, c ->
if (c == target) Point2D(x, y) else null
}
}.filterNotNull().first()
⭐ Day 16, Part 1
The puzzle text can be found here.
Another day, another extension function to make getting a value from a 2D structure given a Point2D.
// In Day16
private operator fun List<String>.get(at: Point2D): Char =
this[at.y][at.x]
Next, we’ll define a Location data class to store the positions of the entire history of our path traversal, as well as the current direction we are facing. Why store the history and not just the current point? Because we need it for Part 2 and its easier to explain it now than refactor it all later.
// In Day16
private data class Location(
val positions: List<Point2D>,
val direction: Point2D
) {
fun position(): Point2D =
positions.last()
fun key(): Pair<Point2D, Point2D> =
position() to direction
fun step(): Location =
copy(
positions = positions + (position() + direction)
)
fun clockwise(): Location =
copy(
direction = when (direction) {
Point2D.NORTH -> Point2D.EAST
Point2D.EAST -> Point2D.SOUTH
Point2D.SOUTH -> Point2D.WEST
Point2D.WEST -> Point2D.NORTH
else -> throw IllegalStateException("Invalid turning point: $this")
}
)
fun antiClockwise(): Location =
copy(
direction = when (direction) {
Point2D.NORTH -> Point2D.WEST
Point2D.WEST -> Point2D.SOUTH
Point2D.SOUTH -> Point2D.EAST
Point2D.EAST -> Point2D.NORTH
else -> throw IllegalStateException("Invalid turning point: $this")
}
)
}
Let’s go through the various functions in Location. First, we have a helper function to get the current position from the list of positions. We’re only doing this so we don’t have to type location.positions.last() in a bunch of places. Next, we have the key which is the current position and direction in a pair. We need this when we implement our main algorithm, I’ll explain it later.
We also have functions related to movement. We have step to create a new Location that is one step in the direction of travel, and we have clockwise and antiClockwise to create a new Location in the same position but turned.
Now we can implement our main algorithm which will be another Breadth-First search! As usual, we set up our work queue, this time using PriorityQueue. The queue holds a Pair<Location,Int> for the work. The Int in this case is the cost to get to that Location. We’ll sort the queue by the cost, descending. We also have to track the locations we’ve seen. We’ll do this in a Map<Pair<Point2D,Point2D>,Int>. The key is a pair of points, the position and direction (this is why we have Location.key()), and the value is the cost to get there. We need to keep track of the cost because there could be a case where we can get to the same place in the same orientation in the same number of steps, and we want to evaluate both of them.
// In Day16
private fun traverseMaze(): Int {
val queue = PriorityQueue<Pair<Location, Int>>(compareBy { it.second })
.apply { add(Location(listOf(start), Point2D.EAST) to 0) }
val seen = mutableMapOf<Pair<Point2D, Point2D>, Int>()
while (queue.isNotEmpty()) {
val (location, cost) = queue.poll()
if (location.position() == end) {
return cost
} else if (seen.getOrDefault(location.key(), Int.MAX_VALUE) > cost) {
seen[location.key()] = cost
location.step().apply {
if (maze[position()] != '#') {
queue.add(this to cost + 1)
}
}
queue.add(location.clockwise() to cost + 1000)
queue.add(location.antiClockwise() to cost + 1000)
}
}
throw IllegalStateException("No path to goal")
}
We’ll keep working so long as the queue is not empty, failing if we reach the end of the queue and have not yet produced an answer. The first thing we do is destructure our pair into a location and cost to make life easier.
If we’ve detected that the position we’re standing on is the end, we’re done. This is at least one of the shortest paths to get to the goal, so return the cost. Otherwise, we need to check that we can schedule more work for our queue. First, we mark the location as having been seen at the current cost. Next, we step in the direction of travel and if that place is not a wall (#), we add that Location to the queue and increment its cost by 1. Because turning is also a valid move at this point, we schedule a clockwise and counterclockwise turn in the queue, adding 1000 to their cost.
All that’s left is to traverse the maze, which solves part 1.
// In Day16
fun solvePart1(): Int = traverseMaze()
Star earned! Onward!
⭐ Day 16, Part 2
The puzzle text can be found here.
Because we stored the history in our Location class, the implementation for Part 2 is mostly finished. We’ll write a traverseMazeWithPath function to execute the new logic, which is mostly the same.
// In Day16
private fun traverseMazeWithPath(): Int {
val queue = PriorityQueue<Pair<Location, Int>>(compareBy { it.second })
.apply { add(Location(listOf(start), Point2D.EAST) to 0) }
val seen = mutableMapOf<Pair<Point2D, Point2D>, Int>()
var costAtGoal: Int? = null
val allSpotsInAllPaths: MutableSet<Point2D> = mutableSetOf()
while (queue.isNotEmpty()) {
val (location, cost) = queue.poll()
if(costAtGoal != null && cost > costAtGoal) {
return allSpotsInAllPaths.size
} else if (location.position() == end) {
costAtGoal = cost
allSpotsInAllPaths.addAll(location.positions)
} else if (seen.getOrDefault(location.key(), Int.MAX_VALUE) >= cost) {
seen[location.key()] = cost
location.step().apply {
if (maze[position()] != '#') {
queue.add(this to cost + 1)
}
}
queue.add(location.clockwise() to cost + 1000)
queue.add(location.antiClockwise() to cost + 1000)
}
}
return allSpotsInAllPaths.size
}
The only major difference is the fact that we want all paths to the goal that are the same length. So if there are two paths from start to end that are both cost 42, we want to see them both. Work scheduling works the same as part 1 so I won’t cover it, but the end condition is different. Basically, we’re looking to make sure we get to the end, and if so, we record the cost it took to get there (costAtGoal). So long as the queue is giving us locations that are at the end for the same cost, we’ll add their entire history to the allSpotsInAllPaths set. The first time we see a cost that is above the smallest costAtGoal, we know we’ll never see a path to the goal that costs less.
Calling traverseMazeWithPath solves part 2.
// In Day16
fun solvePart2(): Int = traverseMazeWithPath()
Star earned! See you tomorrow!
Further Reading
- Index of All Solutions - All posts and solutions for 2024, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 16
- Advent of Code - Come join in and do these challenges yourself!