Skip to Content

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 vars 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

  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 12
  4. Advent of Code - Come join in and do these challenges yourself!