Advent of Code 2021 - Day 18, in Kotlin - Snailfish • Todd Ginsberg

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 SnailfishNumbers, 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 SnailfishNumbers 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 SnailfishNumbers.

// In SnailfishNumber

companion object {
    fun of(input: String): SnailfishNumber {
        val stack = mutableListOf<SnailfishNumber>()
        input.forEach { char ->
            when {
                char.isDigit() -> stack.add(RegularNumber(char.digitToInt()))
                char == ']' -> {
                    val right = stack.removeLast()
                    val left = stack.removeLast()
                    stack.add(PairNumber(left, right))
                }
            }
        }
        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)
            ?.addValue(explodingPair.left as RegularNumber)
        regulars.elementAtOrNull(regulars.indexOfFirst { it === explodingPair.right } + 1)
            ?.addValue(explodingPair.right as RegularNumber)
        (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

fun addValue(amount: 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!

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading