# 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'

Posted on

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.