Advent of Code 2022 - Day 12, in Kotlin - Hill Climbing Algorithm
Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 12: 'Hill Climbing Algorithm'
I’m pretty happy with the implementation of today’s puzzle solutions. It gives us a chance to learn about a fundamental computer science algorithm - breadth first search. We’ll implement BFS in a generic way that helps us solve both parts of the puzzle.
If you’d rather just view code, the GitHub Repository is here .
Puzzle Input
The time has come, as it does during every Advent of Code where I get tired of writing one-off Point2D
classes and write one to reuse throughout the year (I don’t reuse code from year to year except the functions to load input from files). Thankfully, there isn’t much that we need Point2D
to do at this time:
// In Point.kt
data class Point2D(val x: Int = 0, val y: Int = 0) {
fun cardinalNeighbors(): Set<Point2D> =
setOf(
copy(x = x - 1),
copy(x = x + 1),
copy(y = y - 1),
copy(y = y + 1)
)
}
Our Point2D
class will have an x
and a y
to represent its coordinates, and a cardinalNeighbors
function to return another Set<Point>
of its non-diagonal neighbors. We’ll take advantage of the copy
constructor that comes with our data class
to construct the neighbor instances.
For our input
, we’ll store it in a new class called HeightMap
, which will be an inner class of our Day12
class and will store the data we need to represent the map we’re given. The elevations
is a Map<Point2D, Int>
where the key is a point in the map and the value is the height at that point. The start
and end
points are the specially labeled places on the map.
// In Day12
private class HeightMap(val elevations: Map<Point2D, Int>, val start: Point2D, val end: Point2D)
And given that, we can write our usual parseInput
function which today will operate on a List<String>
and return a HeightMap
.
// In Day12
private fun parseInput(input: List<String>): HeightMap {
var start: Point2D? = null
var end: Point2D? = null
val elevations = input.flatMapIndexed { y, row ->
row.mapIndexed { x, char ->
val here = Point2D(x, y)
here to when (char) {
'S' -> 0.also { start = here }
'E' -> 25.also { end = here }
else -> char - 'a'
}
}
}.toMap()
return HeightMap(elevations, start!!, end!!)
}
We’ll define var
s for start
and end
as Point2D?
and set the initial value to null. As we loop through the input, we’ll find the proper values. To calculate the elevations
, we perform a flatMapIndexed
and mapIndexed
over the input
which gives us x
, y
, and the char
we are looking at. We’ll temporarily define here
to represent the point we’re looking at, and use a when
expression to calculate the height. Note that when we find the start
and end
, we also
need to store them. So we’ll take care of that. At the end of the flatMapIndexed
loop we’ll have a List<Pair<Point2D, Int>>
which we can turn into a Map<Point2D, Int>
via toMap()
.
We now have enough to crate the HeightMap
but we need to remember to call the hold-my-beer operator
on both start
and end
because they are nullable and we want non-null versions.
We’ll call this function on our input and set it aside in heightMap
.
class Day12(input: List<String>) {
private val heightMap: HeightMap = parseInput(input)
}
⭐ Day 12, Part 1
The puzzle text can be found here.
To solve Part One we’re going to implement what’s called a Breadth First Search (BFS). One of the key features of a BFS is priority queue. It’s a queue that keeps its contents in an order so that the first item is always the “best” item to look at next. For each spot on the map we will calculate how many steps it took us to get there, find all of its neighbors, and add them to the queue with a cost that is one higher than the cost it took us to get to where we are. Eventually, the goal will be found and the process can end.
In order to do this, we need something to store in our priority queue, so let’s define PathCost
, which defines Point2D
and the cost
it took to get there.
// In Day12 (OR in Day12.HeightMap)
private data class PathCost(val point: Point2D, val cost: Int) : Comparable<PathCost> {
override fun compareTo(other: PathCost): Int =
this.cost.compareTo(other.cost)
}
The reason PathCost
works for our priority queue is that it implements Comparable
. Meaning, we can compare two PathCost
instances together to figure out which one has a lower cost
(number of steps).
Time to write our BFS algorithm, which we’ll call shortestPath
. We’re going to write this in a way that makes things easier in Part Two, so we’ll take in a few arguments. The first thing we need to know is where to begin
our search. This is a Point2D
and in Part One this will be the start
. Next, we need a function to determine if a given Point2D
is the goal or not which we’ll call isGoal
. The isGoal
function takes in a Point2D
and returns a Boolean
indicating if we’ve found the goal or not. And finally we need another function called canMove
to determine if we’re allowed to move from one point to the next. This function takes in two Int
objects (the “from” point and the “to” point) also returning a Boolean
if we are allowed to move between them.
// In Day12.HeightMap
fun shortestPath(
begin: Point2D,
isGoal: (Point2D) -> Boolean,
canMove: (Int, Int) -> Boolean
): Int {
val seen = mutableSetOf<Point2D>()
val queue = PriorityQueue<PathCost>().apply { add(PathCost(begin, 0)) }
while (queue.isNotEmpty()) {
val nextPoint = queue.poll()
if (nextPoint.point !in seen) {
seen += nextPoint.point
val neighbors = nextPoint.point.cardinalNeighbors()
.filter { it in elevations }
.filter { canMove(elevations.getValue(nextPoint.point), elevations.getValue(it)) }
if (neighbors.any { isGoal(it) }) return nextPoint.cost + 1
queue.addAll(neighbors.map { PathCost(it, nextPoint.cost + 1) })
}
}
throw IllegalStateException("No valid path from $start to $end")
}
Let’s go through the implementation of the shortestPath
function. First we create a MutableSet<Point2D>
to represent the spots on the map we’ve seen
. Because the queue (which we will define in a moment) always returns points in the best order (shortest path), if a Point2D
is in seen
we know we’ve been able to get there a quicker way already. This is good to know because we won’t waste time evaluating the current spot ant longer since its' neighbors can’t ever be faster.
Next we define the queue
we’ll draw our work from. In this case it is a PrioirityQueue<PathCost>
which we will see with the starting point at zero cost.
Then the fun starts! We’ll loop through the queue
while it still has work for us to do, and we still haven’t found the goal. We’ll poll
the queue
, retrieving the best nextPoint
to look at. This is always going to be the lowest cost candiate spot to look at. If we haven’t seen
this point yet, we’ll begin to look at its neighbors. It is important to remember that we need to add the current point
to seen
or we’ll never be able to know where we’ve been.
We gather the neighbors
of the current point and filter out anything that is off the map (not in elevations
). In theory, we could add another filter
on here to make sure the neighbor isn’t in seen
as well, but I’m fine with checking them as the come off the queue (which we would have to do anyway). The last bit of filtering we need to do is to only keep spots we canMove
to. This uses the function we handed in as an argument to shortestPath
. We look up the elevation of both the spot we are coming from and spot we are going to and pass them to the function.
Now we have the list of neighbors that are on the map and can move to. This is the point where we can see if we’re about to reach the goal. If any
of the neihgbors
passes the isGoal
predicate we’ve defined, it is the spot we are looking for and we can return the total cost to get there. Remember the goal is one of our neighbors, so we need to add 1 step to the path.
If none of the neighbors
is the goal, we convert them to PathCost
objects (again, adding 1 to the cost) and add them all to the queue
.
Eventually, we’ll find a spot that we can move to that is the goal. All that’s left is to call this function.
// In Day12
fun solvePart1(): Int = heightMap.shortestPath(
begin = heightMap.start,
isGoal = { it == heightMap.end },
canMove = { from, to -> to - from <= 1 }
)
We want to begin
at the start
as defined in the puzzle input. We define a function to implement isGoal
that looks to see if the candidate spot is the end
, and we canMove
to a new spot if the spot we are moving to
is lower than or at most 1 elevation higher than the spot we are moving from
.
Running this gives us the answer to Part One!
Star Earned! Onward!
⭐ Day 12, Part 2
The puzzle text can be found here.
There are a couple of ways we could solve this part of the puzzle. First, we could go and find any low point on the map and run shortestPath
as-is for all of them, hanging out the begin
value each time, and taking the smallest number. The second possible solution is to start at the end (the highest point on the map) and perform shortestPath
until we find any low point. Because shortestPath
will run into the low point that is closest to the end first, this should give us our answer. I like this better, so let’s write it that way.
Thanks to the fact that we made shortestPath
so configurable in Part One, we have everything we need for Part Two ready to go. We just need to write some code for the various conditions.
// In Day12
fun solvePart2(): Int = heightMap.shortestPath(
begin = heightMap.end,
isGoal = { heightMap.elevations[it] == 0 },
canMove = { from, to -> from - to <= 1 }
)
Let’s go over the arguments to shortestPath
for Part Two. First, we need to set the begin
of the path to the highest point, so we’ll set that to heightMap.end
. Next, we need to redefine what the goal is. In Part One we wanted to find the end
, but in Part Two we are looking for any low point. So we’ll write a lambda function to examine the elevation
of the current point and see if it is a low point (“0”) or not. Finally, we need to reverse the canMove
logic. When going up the mountain, we can only climb one unit up and any number of units down. But in Part Two we’re running the find in reverse so this logic has to be reverse too - we can descend at most 1 but can climb as many as we like. Again, because we’re searching from the end to the beginning, this logic needs to be reversed.
Running this gives us the answer to Part Two!
Star earned! See you tomorrow.
Further Reading
- Index of All Solutions - All posts and solutions for 2022, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 12
- Advent of Code - Come join in and do these challenges yourself!