# Advent of Code 2021 - Day 15, in Kotlin - Chiton

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 15: 'Chiton'

Posted on

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 `Traversal`s 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) {
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 `Traversal`s 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!