Advent of Code 2022 - Day 13, in Kotlin - Distress Signal • Todd Ginsberg

Today’s puzzle reminded me a lot of the Snailfish Puzzle from 2021 which I had a lot of trouble with. Thankfully I didn’t run into any significant issues while solving this one. Maybe the fact that I read over my Snailfish solution before starting on this one helped.

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

Puzzle Input

As usual, before we get into parsing lets talk about the structure we want to end up with first. Just like the Snailfish problem, we will represent our packets with a sealed class structure. The root class, which will do all the parsing and nothing else will be called Packet. The two sealed subclasses will be called IntPacket (for packets that represent an integer) and ListPacket (for packets that represent lists of packets).

Because we will end up needing to do a lot of comparisons, we’ll have our Packet (and its subclasses) implement Comparable<Packet>. However, we’ll defer implementing them until Part One by “implementing” them with TODO(). The TODO() function in Kotlin is great - its type is Nothing, which subclasses every type in Kotlin. This means we can use it anywhere and satisfy the type requirements. I use this all the time when I’m writing code. If I know I want a function that has a specific signature, but don’t want to actually implement it or provide a dummy implementation I might forget to remove later, I “implement” it with TODO(). If I run this function, I’ll get an exception. The TODO() function is really nice for this kind of thing, so we’ll use it.

// In Day13

private sealed class Packet : Comparable<Packet> {

}

private class IntPacket(val amount: Int) : Packet() {
    override fun compareTo(other: Packet): Int = TODO()
}

private class ListPacket(val subPackets: List<Packet>) : Packet() {
    override fun compareTo(other: Packet): Int = TODO()
}

And now for the fun part - the parsing. Usually when I parse data into a class I like to provide an of function in the companion object for that class to do the work. That’s still true today but instead of one we’ll have two!

// In Day13.Packet:

companion object {
    fun of(input: String): Packet =
        of(
            input.split("""((?<=[\[\],])|(?=[\[\],]))""".toRegex())
                .filter { it.isNotBlank() }
                .filter { it != "," }
                .iterator()
        )

    private fun of(input: Iterator<String>): Packet {
        val packets = mutableListOf<Packet>()
        while (input.hasNext()) {
            when (val symbol = input.next()) {
                "]" -> return ListPacket(packets)
                "[" -> packets.add(of(input))
                else -> packets.add(IntPacket(symbol.toInt()))
            }
        }
        return ListPacket(packets)
    }
}

Why two? Because of how I’ve elected to perform the parsing by using an Iterator<String> to feed us each of the symbols we care about and nothing else. At the core level, we want to turn "[1, 20, [3]]" into a stream of symbols: ["1", "20", "[", "3", "]", "]"] and use that to construct our ListPacket (remember - all of these lines are ListPackets, ultimately). To do this, we’ll split each String by what I admit is a terrifying looking regular expression. I won’t go into detail on this (not sure if that’s a good thing or a bad thing) but basically what it does is split the string on any of “[” or “]” or “,” and keeps them in the output. Normally when we split a string, we don’t get the delimiters. In this case we want the brackets because they are the signal for “start a new list” and “we’re done creating a list”. The commas we can throw away, along with blank lines.

The other of function takes an Iterator<String> and uses the fact that we can pass it around and have our recursive calls draw from it as well. We start by create a MutableList<Packet> to store any Packet objects we end up creating. Then we start looping for as long as input has more symbols to give us via hasNext. As we get a symbol we examine it. If it is a close-list ("]"), we return a new ListPacket based on the packets we’ve already created (if any!). If it is an open-list ("[") we recursively call of with the rest of the input and add the result of that computation to the packets list. Otherwise, the only thing left are numbers, so we turn the symbol into an Int, use it to create a new IntPacket and add that to the list of packets. When we run out of input, we take whatever packets we have an return them in another new ListPacket.

Now that we can create a single Packet from a single String, we can map our input to Packet objects after filtering out blank lines.

class Day13(input: List<String>) {

    private val packets = input.filter { it.isNotBlank() }.map { Packet.of(it) }

}

⭐ Day 13, Part 1

The puzzle text can be found here.

Because the parsing code does all the work to set up each Packet, all that remains for us is to remove those TODO() calls and implement sorting. Sorting, as a reminder, is implemented in the compareTo function.

Let’s look at IntPacket first, as that one is more straight forward.

// In Day13

private class IntPacket(val amount: Int) : Packet() {
    fun asList(): Packet = ListPacket(listOf(this))

    override fun compareTo(other: Packet): Int =
        when (other) {
            is IntPacket -> amount.compareTo(other.amount)
            is ListPacket -> asList().compareTo(other)
        }
}

For comparing an IntPacket with another Packet we have two possible outcomes. First, the other packet could be another IntPacket. In that case the instructions tell us to compare their values, so we’ll call compareTo again on their amount (thankfully, Int implements Comparable<Int>). The other possible outcome is that the other packet is a ListPacket. In that case we need to turn ourselves (an IntPacket) into a ListPacket. We’ll write a function called asList to do this. When called, asList bundles up the current instance into a List<Packet> and hands it to the ListPacket constructor. We then call compareTo on the ListPacket instances, which we’ll go over next.

// In Day13

private class ListPacket(val subPackets: List<Packet>) : Packet() {
    override fun compareTo(other: Packet): Int =
        when (other) {
            is IntPacket -> compareTo(other.asList())
            is ListPacket -> subPackets.zip(other.subPackets)
                .map { it.first.compareTo(it.second) }
                .firstOrNull { it != 0 } ?: subPackets.size.compareTo(other.subPackets.size)
        }
}

A bit more complicated than before, but still only two possible outcomes. In the first outcome, the other packet is an IntPacket, so we do the same as before - convert it to a ListPacket and call compareTo on them. The second outcome is where the real work of the solution is - both sides of the compareTo are ListPacket instances.

In that case, we’re going to need to pair up each Packet from both lists and compare them together. We do that by calling zip. I love the zip function and can’t believe we got to Day 13 and are only just now seeing it for the first time in one of my solutions. When we call zip on a list and give it another list, the elements from each list are paired together. So [A, B, C].zip([1, 2, 3]) gives us [[A, 1], [B, 2], [C, 3]]. Neat, huh?

Once we have our zip, we want to compare these two packets. We’ll map the output of compareTo and then find the first element that isn’t a 0 (reminder: 0 means the packets are equal). If we don’t find any packets that aren’t equal, we’ll have to see which side of the comparison has a longer list (if any). We do this by calling compareTo on the size of each of the list of subPackets in each ListPacket.

To summarize: compare each element in the lists pair-wise. If one of them is greater or less than the other, that’s our answer. If all elements are equal, compare the size of the lists.

Now that we can compare Packet instances, we have everything we need to solve Part One.

// In Day13

fun solvePart1(): Int =
    packets.chunked(2).mapIndexed { index, pair ->
        if (pair.first() < pair.last()) index + 1 else 0
    }.sum()

Because we want to compare pairs of inputs, we will get a chunked(2) view of our packets. Calling chunked(2) gives us a List<Packet> of length 2. Since we ultimately need the index of the pair of packets that are in the right order, we’ll mapIndexed the output from chunked. The mapping function is a comparison - if the first element of the pair is less than the second element of the pair, they are in the right order so we’ll map to index+1 (because the puzzle answer wants 1-indexed values). Otherwise they are equal or in the wrong order so we’ll return 0. The result of mapIndexed is a List<Int> containing either a 0 or the 1-based index value of correct packets. We’ll sum those to get our answer.

Star earned! Onward!

A Brief Intermission

If you’ve made it this far, you’ve now collected half of the stars available in 2022!

⭐ Day 13, Part 2

The puzzle text can be found here.

Because we implemented Comparable<Packet> in our Packet sealed class structure, we have everything we need to solve Part Two.

// In Day13

fun solvePart2(): Int {
    val dividerPacket1 = Packet.of("[[2]]")
    val dividerPacket2 = Packet.of("[[6]]")
    val ordered = (packets + dividerPacket1 + dividerPacket2).sorted()
    return (ordered.indexOf(dividerPacket1) + 1) * (ordered.indexOf(dividerPacket2) + 1)
}

We’ll have to create the two divider packets the instructions call for. We’ll store them in dividerPacket1 and dividerPacket2 and create them with Packet.of(String). Once we have those we’ll append them to the packets list in order to get a new List<Packet> with the two dividers added on. Calling sorted() on the new list will return another new list with all of our packets in the right order. All that remains is to find the index of both of the divider packets (remembering to add 1 because we are 0-indexed and the puzzle answer assumes 1-indexed) and multiply them together!

Star earned! See you tomorrow. There are not fewer days of Advent of Code 2022 ahead of us than behind us.

⭐ Day 13, Part 1

A Brief Intermission

⭐ Day 13, Part 2

Further Reading