Advent of Code 2021 - Day 15, in Kotlin - Chiton • Todd Ginsberg

I had the day off work today and am really glad that I had a problem like this to play with. I wrote it a few different ways and this is the one that I am the happiest with. Path finding problems are common in Advent of Code, so I was pleased to see this one.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

We’ll represent our cave as an Array<IntArray> and assign a typealias of ChitonCave to it to make it look a bit cleaner. You could also change the type to List<List<Int>>, but arrays felt more natural (even if we never really modify the cave). We could also use a Map<Point2d, Int> here if we really wanted to as well but it seemed a bit more confusing to me.

typealias ChitonCave = Array<IntArray>

class Day15(input: List<String>) {

    private val cave: ChitonCave = parseInput(input)

    private fun parseInput(input: List<String>): ChitonCave =
        input.map { row ->
            row.map { risk ->
                risk.digitToInt()
            }.toIntArray()
        }.toTypedArray()
}

Parsing the input shouldn’t look much different than previous days.

⭐ Day 15, Part 1

The puzzle text can be found here.

Before Advent of Code 2021 started, I said to myself that I would try not to use Pair so often because it might be confusing. I haven’t been doing a great job of that, so today we’ll define a class called Traversal which carries a Point2d representing a point in the cave, and the totalRisk it took to get to that point. This will be used in our path-finding algorithm, which we will go over in a moment. Because we’ll be comparing Traversal attempts by how much totalRisk they involve, we’ll implement Comparable<Traversal> so we can order Traversals by the total amount of risk (less risky come first).

// In Day15

private class Traversal(val point: Point2d, val totalRisk: Int) : Comparable<Traversal> {
    override fun compareTo(other: Traversal): Int =
        this.totalRisk - other.totalRisk
}

Just like days past, let’s implement the get operator on our ChitonCave type. This will give us a bit nicer syntax, and will help us out in part two (we’ll be redefining the logic here).

// In Day15

private operator fun ChitonCave.get(point: Point2d): Int =
    this[point.y][point.x]

The major piece of work today is to define a function to traverse the cave. To make things easier, we’ll assume we always want to start at Point2d(0,0). We’ll also define the destination as the bottom right-most point in the ChitonCave unless we are told otherwise (we change the destination in part two).

// In Day15

private fun ChitonCave.traverse(
    destination: Point2d = Point2d(first().lastIndex, lastIndex)
): Int {

    val toBeEvaluated = PriorityQueue<Traversal>().apply { add(Traversal(Point2d(0, 0), 0)) }
    val visited = mutableSetOf<Point2d>()

    while (toBeEvaluated.isNotEmpty()) {
        val thisPlace = toBeEvaluated.poll()
        if (thisPlace.point == destination) {
            return thisPlace.totalRisk
        }
        if (thisPlace.point !in visited) {
            visited.add(thisPlace.point)
            thisPlace.point
                .neighbors()
                .filter { it.x in (0..destination.x) && it.y in (0..destination.y) }
                .forEach { toBeEvaluated.offer(Traversal(it, thisPlace.totalRisk + this[it])) }
        }
    }
    error("No path to destination (which is really weird, right?)")
}

This might look confusing, so let’s go over how traverse works. First we set up a PriorityQueue which is effectively a List that keeps the elements in their natural order. Because we implemented Comparable on Traversal, we know that a Traversal with a lower totalRisk will always come before a Traversal with a higher totalRisk when removing items from the front of the queue, no matter what order we inserted them. This means when we remove the first element of the toBeEvaluated queue, we’ll always get the Traversal with the lowest totalRisk. When we set up the toBeVisited queue, we seed it with the origin point and assign it a totalRisk of 0 (per the instructions).

Because we’re going to be visiting points in the cave according to their totalRisk order, we can keep track of which ones we’ve already visited in a set which we’ll call visited. To expand on that a bit, suppose we get a Traversal from our queue. If we’ve ever seen the point in that traversal before, we know that it had a lower totalRisk because the queue orders Traversals in order of risk.

We’ll loop over our toBeEvaluated queue until it is empty. The first thing we do is poll the queue which simply means to remove the first element of the queue (the one with the lowest totalRisk) and return it to us. If we’ve just pulled the destination out of the queue, we can return the totalRisk, because we know there can’t be anything lower.

Otherwise, we want to check that we haven’t visited the place we just pulled out of the queue already. It’s possible that the same point ends up in the toBeVisited queue more than once. And again, if we’ve ever seen this point before, we know it was at a lower totalRisk level so we can ignore it. Now that we know we are looking at a point for the first time, we get all of its neighbors, taking care to filter only the ones that are actually in the cave. Anything that’s left (neighbors that are in the cave), we create a Traversal object to represent it and add it to the toBeVisited queue via offer. The PriorityQueue is responsible for putting our Traversal object in the right place depending on its totalRisk. Note that we could do a second filtering here to not add a point to the queue that we’ve already seen but I found that actually slowed the code down a bit so I removed it. This might make more sense if we have a much larger cave system.

And now that we can traverse the cave, we can solve part one:

// In Day15

fun solvePart1(): Int =
    cave.traverse()

Star earned! Onward!

⭐ Day 15, Part 2

The puzzle text can be found here.

Before we get into the code, let’s talk strategy. We could go through our ChitonCave and physically expand it by copying each block and recalculating the risk involved for each new spot. It would work, but it would take up a bunch of memory just to represent the cave. But because the cave has a predictable risk depending on the coordinates, we don’t have to do any of that. Instead lets redefine our get operator to perform the risk calculation as if the cave really were expanded.

// In Day15

// Replace existing with this! 
private operator fun ChitonCave.get(point: Point2d): Int {
    val dx = point.x / this.first().size
    val dy = point.y / this.size
    val originalRisk = this[point.y % this.size][point.x % this.first().size]
    val newRisk = (originalRisk + dx + dy)
    return newRisk.takeIf { it < 10 } ?: (newRisk - 9)
}

First, we calculate dx (delta x) and dy (delta y) to represent the number of tiles we need to move over. Conveniently, if we are on the “home” tile then dx and dy will equal 0. For example, if we have a 3x3 grid, and we want the risk for the spot at 7,4, we’ll have a dx of 2 and a dy of 1. In order to calculate the new level of risk, we need the risk value from the “home” tile, so we’ll pull that out and store it in originalRisk. We calculate the original risk by taking the point we want modulo the original size of the cave in that dimension. So again, if we have a 3x3 cave and we want the risk at 7,4, we’ll have to look at the original risk at 1,1.

Now we can calculate the newRisk by adding the originalRisk to dx (how many tiles we’ve moved over) and dy (how many tiles we’ve moved down). We can use takeIf to help ensure that our newRisk level never goes over 9. Note that if we ever have to expand the cave beyond a factor of 9, we’ll have to rethink this calculation.

And now we can traverse the cave for part two:

// In Day15

fun solvePart2(): Int =
    cave.traverse(
        Point2d((cave.first().size * 5)-1, (cave.size * 5)-1)
    )

The only thing we have to change is to tell traverse where the bottom right-most corner of the cave is. We calculate this by multiplying the size of each dimension by 5 and then subtracting 1 because we have a zero-indexed coordinate system. Other than that, the logic for traverse stays the same. On my machine this runs in about one second, and I felt that was fast enough.

Star earned!

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading