# Advent of Code 2021 - Day 18, in Kotlin - Snailfish

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 18: 'Snailfish'

Posted on

Sorry this one is late. I was traveling on December 18 and got a late start on this. I also ran into a bug (which I’ll point out below) that caused me to go down the wrong track for a while. Anyway, it’s here! I sure hope we don’t get any more Snailfish math problems this year, this one was quite challenging for me and if I’m being honest, not one of my favorite puzzles this year.

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

Problem Input

I tried a couple of different approaches to representing the Snailfish numbers and settled on a sealed class structure that eventually represents a tree. According to the instructions there are two kinds of Snailfish numbers: either a regular number (just a plain number) or a pair of numbers which has a left and right number.

These classes will expand in part one, but the basic structure looks like this:

``````class Day18(private val input: List<String>) {

sealed class SnailfishNumber {
var parent: SnailfishNumber? = null
abstract fun magnitude(): Int

private fun root(): SnailfishNumber =
if (parent == null) this else parent!!.root()
}

data class RegularNumber(var value: Int) : SnailfishNumber() {
override fun magnitude(): Int = value
}

data class PairNumber(var left: SnailfishNumber, var right: SnailfishNumber) : SnailfishNumber() {
init {
left.parent = this
right.parent = this
}

override fun magnitude(): Int = (left.magnitude() * 3) + (right.magnitude() * 2)
}
}
``````

We have two implementations of `SnailfishNumber` - a `RegularNumber` and a `PairNumber`. Because we’re going to be building a tree structure out of these have an optional (nullable and variable) `parent` to keep track of the node just above them in the tree. In the main `SnailfishNumber` class we will define a `root()` method to work through the parent references until we hit the top-most element. This is the root of the tree. As you can see in `PairNumber`, since the `left` and `right` values are also `SnailfishNumber`s, we need to set their `parent`, which we do in the `init` block.

It turns out that because we mutate this structure (which you’ll see below), `magnitude` must be either a function or powered by a `lazy delegate`. This burned a lot of time for me, so don’t make the same mistake. We’ll keep our raw String `input` as a String and create `SnailfishNumber` instances as needed. This is helpful in part two.

To reduce clutter in this post, I’ve broken out the parsing into it’s own block. In code, this belongs inside `SnailfishNumber` as a companion object. Our strategy, again, will be to define an `of` function that takes a `String` and returns us a `SnailfishNumber`. Parsing is done via a stack. If we run into a digit, we create a `RegularNumber` to represent that digit and push it on to a stack. If we run into a closing brace (`]`) that means we’ve hit the end of a pair, so we’ll pop the two `SnailfishNumber`s off the stack, put them into the `PairNumber` and then push that `PairNumber` back on the stack. Eventually, we’ll be left with a single item on the stack, a `PairNumber` representing the root of our tree of fully parsed `SnailfishNumber`s.

``````// In SnailfishNumber

companion object {
fun of(input: String): SnailfishNumber {
val stack = mutableListOf<SnailfishNumber>()
input.forEach { char ->
when {
char == ']' -> {
val right = stack.removeLast()
val left = stack.removeLast()
}
}
}
return stack.removeFirst()
}
}
``````

#### ⭐ Day 18, Part 1

The puzzle text can be found here.

There are a lot of small changes going on inside our sealed classes, so I’ll do my best to explain the big picture as we go. First up, let’s add some functions we’ll need in order to deal with exploding and splitting. We declare these abstract in our root classs…

``````// In SnailfishNumber

abstract fun split(): Boolean
abstract fun regularsInOrder(): List<RegularNumber>
abstract fun pairsInOrderWithDepth(depth: Int = 0): List<PairNumberDepth>
``````

And implement them in the child classes (we’ll find out why in a moment):

``````// In RegularNumber

override fun split(): Boolean = false
override fun regularsInOrder(): List<RegularNumber> = listOf(this)
override fun pairsInOrderWithDepth(depth: Int): List<PairNumberDepth> = emptyList()
``````

Because a `RegularNumber` cannot be split, we return `false` from the `split` function we’ve just defined. This tells the caller that a split did not happen. In the future, when we write the `explode` function, we’ll need to have all of the `RegularNumber` instances in the tree listed out in order, and all of the `PairNumber` instances listed out, along with the depth they were encountered at. Because `RegularNumbers` aren’t pairs, we can return an `emptyList` from `pairsInOrderWithDepth`, and a singleton list from `regularsInOrder`.

For completeness, `PairNumberDepth` is a class rather than a `Pair`:

``````// In Day18

data class PairNumberDepth(val depth: Int, val pair: PairNumber)
``````

We probably could have got away clarity-wise with a `Pair<Int,PairNumber>` but I think this is clearer. Those same functions in `PairNumber` are:

``````// In PairNumber

override fun regularsInOrder(): List<RegularNumber> =
this.left.regularsInOrder() + this.right.regularsInOrder()

override fun pairsInOrderWithDepth(depth: Int): List<PairNumberDepth> =
this.left.pairsInOrderWithDepth(depth + 1) +
listOf(PairNumberDepth(depth, this)) +
this.right.pairsInOrderWithDepth(depth + 1)
``````

These are both recursive functions (they call themselves). For `regularsInOrder`, we form a list of all the `regularsInOrder` our `left` child provides, combined with the list of `regularsInOrder` our `right` child provides. In `pairsInOrderWithDepth`, we do similar work - adding the list of `PairNumberDepth` objects our `left` child provides with the list our `right` child provides. However, there’s one big difference, we have to include the object this function was called on in the middle of all that. These functions are two examples of a depth-first traversal of a binary tree.

Now that we can get the regular and pair numbers from a tree in order we can explode!!! This doesn’t turn out to be nearly as fun as the name would otherwise indicate.

``````// In SnailfishNumbr

private fun explode(): Boolean {
val pairs = root().pairsInOrderWithDepth()
val explodingPair = pairs.firstOrNull { it.depth == 4 }?.pair
if (explodingPair != null) {
val regulars = root().regularsInOrder()
regulars.elementAtOrNull(regulars.indexOfFirst { it === explodingPair.left } - 1)
regulars.elementAtOrNull(regulars.indexOfFirst { it === explodingPair.right } + 1)
(explodingPair.parent as PairNumber).childHasExploded(explodingPair)
return true
}
return false
}
``````

The `explode` function returns `true` when it handles an explosion and `false` otherwise. To determine if we need to explode, we’ll find the `root` of the tree and call `pairsInOrdeWithDepth` on it. If we find an `explodingPair` whose depth is 4, we need to explode. To figure out where our `left` and `right` child values go, we need to figure out where they are in the tree. This is where `regularsInOrder` comes in. We get the list of `RegularNumber` objects and find where in that order our `left `and `right` child numbers are. We need to take care to use `===` because we want referential equality here. If we used `==` we would be telling Kotlin that any 2 (for example) is good, where we need a specific 2 (assuming 2 is the value we’re looking for). Once we’ve got that index value, we get either the previous node (for left) or the next node (for right) and add our left and right values to them respectively. Because we might be at the end of the list, there might not be a next-left or a next-right node. Kotlin’s `elementAtOrNull` saves us here, we can give it whatever number we like (-1 for example) and it won’t throw an exception if that’s invalid, it just returns null. Neat, huh?

You might have noticed `addValue`. I defined that to simplify things a bit:

``````// In RegularNumber

this.value += amount.value
}
``````

We also need to record the fact that for this pair, a replacement `RegularNumber(0)` needs to be inserted. We’ll do this by adding a `childHasExploded` function to `PairNumber` that we can call to sort out the references when we insert this new number:

``````// In PairNumber

fun childHasExploded(child: PairNumber) {
val replacement = RegularNumber(0).apply { parent = this@PairNumber.parent }
when {
left === child -> left = replacement
else -> right = replacement
}
}
``````

We’re done with explosions! On to splitting…

``````// In PairNumber

override fun split(): Boolean {
if (left is RegularNumber) {
val actualLeft = left as RegularNumber
if (actualLeft.value >= 10) {
left = actualLeft.splitToPair(this)
return true
}
}
val didSplit = left.split()
if (didSplit) return true
if (right is RegularNumber) {
val actualRight = right as RegularNumber
if (actualRight.value >= 10) {
right = actualRight.splitToPair(this)
return true
}
}
return right.split()
}
``````

Splitting works like some of the other functions we’ve seen here today - it depends on a depth-first traversal. Since `PairNumber` is the `parent` of anything that can be split, we’ll concentrate the logic there. First, we look to see if our `left` hand side is a `RegularNumber` and needs splitting. If so, we split it and return `true` to indicate that we’re done with the single split we can do this pass. If not, we recurse down to our `left` child and ask it to split. Assuming that did not result in a split, we do the same for the `right` - check our immediate child, and if not, recurse down.

The `RegularNumber` is responsible for splitting itself:

``````// In RegularNumber

fun splitToPair(splitParent: SnailfishNumber): PairNumber =
PairNumber(
RegularNumber(floor(value.toDouble() / 2.0).toInt()),
RegularNumber(ceil(value.toDouble() / 2.0).toInt())
).apply { this.parent = splitParent }
``````

This function takes care of the math using `floor` and `ceil` from the Kotlin standard library to round down and up respectively. It is also responsible for setting the `parent` of the newly created node.

Finally! We have enough to write the reduce function!

``````// In SnailfishNumber

fun reduce() {
do {
val didSomething = explode() || split()
} while(didSomething)
}
``````

Because explosions take priority over splitting, each time through the do/while loop we’ll either explode or split if we didn’t explode. Or neither, and that’s when the loop ends.

One more piece of housekeeping - an `operator` to make adding `SnailfishNumber` instances easier:

``````// In SnailfishNumber

operator fun plus(other: SnailfishNumber): SnailfishNumber =
PairNumber(this, other).apply { reduce() }
``````

Whenever we add two `SnailfishNumber` instances, we’ll want to `reduce` them as well. Because that’s here in the `plus` operator, we don’t have to worry about it.

We can finally solve part one:

``````// In Day18

fun solvePart1(): Int =
input.map { SnailfishNumber.of(it) }.reduce { a, b -> a + b }.magnitude()
``````

First we map each `input` into a `SnailfishNumber` and then `reduce` them one by one (this is a functional reduction, not the `SnailfishNumber.reduce` we just wrote). This functional reduction ends with a single `SnailfishNumber`, which we can call `magnitude()` on to get our answer.

Star earned! I’m glad that’s over. Onward!

#### ⭐ Day 18, Part 2

The puzzle text can be found here.

Part two has us finding the pair of Snailfish numbers that add up to the largest magnitude. To do this, we’ll have to run through our input and pair each one up with each other one, keeping in mind that A,B and B,A are separate pairs! Because our `SnailfishNumber` class is not immutable, we’ll create a new instance every time we need one. Looping through the `String` input to create the pairs helps us here.

``````// In Day18

fun solvePart2(): Int =
input.mapIndexed { index, left ->
input.drop(index + 1).map { right ->
listOf(
SnailfishNumber.of(left) to SnailfishNumber.of(right),
SnailfishNumber.of(right) to SnailfishNumber.of(left)
)
}.flatten()
}.flatten()
.maxOf { (it.first + it.second).magnitude() }
``````

At the end, we can call `maxOf` and give it the calculation to find the magnitude of the two numbers in each pair. Kotlin does the rest!

Star earned!