Advent of Code 2021 - Day 16, in Kotlin - Packet Decoder • Todd Ginsberg

I’ll admit the instructions for this one confused the heck out of me for a while before I re-read it enough times to realize that sub-packets were completely specified packets. Once I understood that the implementation clicked. Today, we’ll be making use of Iterator and adding some handy extension functions to it to make our parsing code a bit more appealing.

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

Problem Input

Before we start manipulating our input into a format we can work with, let’s talk about our approach to today’s puzzle. We’re asked to take in a hexadecimal string and turn it into a binary string. From that, we’re asked to parse the binary string into packets. Since the input reads left to right and doesn’t require us to read backwards at any point, we’ll represent our binary input as an Iterator<Char>. We could use a Sequence<Char> but I found Iterator to be more natural (to me).

The first step is to convert our hexadecimal input into binaryInput, which we’ll store as an Iterator<Char>

class Day16(input: String) {

    private val binaryInput: Iterator<Char> = hexToBinary(input).iterator()

    private fun hexToBinary(input: String): List<Char> =
        input.map { it.digitToInt(16).toString(2).padStart(4, '0') }.flatMap { it.toList() }

}

Instead of writing hexToBinary the way we have, we could create a lookup table like the one that appears in the puzzle description. But I think this works better and shows off the power of the Kotlin standard library. First, we map each character of input to an Int by calling digitToInt on each Char. We pass 16 to digitToInt to tell it the Char we want to convert is in base 16 (hexadecimal). Since we want that base 10 Int as a base 2 String, we’ll call toString on it and pass in 2 to represent base 2 (binary). Because not all binary numbers will be width 4, we padStart them so they’ll all be the same width. At this point we have a List<String> and we want a List<Char>, so we’ll flatMap all of the strings into one List<Char>.

⭐ Day 16, Part 1

The puzzle text can be found here.

Since we’ll be dealing with Iterator<Char> a lot, let’s add some extension functions to make our life better. We’ll define them all here and we’ll see them used later on. We’ll define them in our Extensions.kt file.

// In Extensions.kt

fun Iterator<Char>.next(size: Int): String =
    (1..size).map { next() }.joinToString("")

First up - given an Iterator<Char> we need a way to get a few Chars into a String. For example, if we had ['0', '1', '0', '1'] and wanted to get the first three characters as a String ("010"), we’d call next(3). The code for that maps over a range, calling next() which gives us a single Char. We joinToString at the end to turn the List<Char> into a String. This is a fundamental function used in our parsing.

// In Extensions.kt

fun Iterator<Char>.nextInt(size: Int): Int =
    next(size).toInt(2)

Next up, we need a way to get the next few binary digits from an Iterator<Char> and turn them into an Int (in decimal). We’ll use next(Int) which we just wrote and convert the String to an Int by calling toInt and specifying that we’re converting from base 2 (binary).

// In Extensions.kt

fun Iterator<Char>.nextUntilFirst(size: Int, stopCondition: (String) -> Boolean): List<String> {
    val output = mutableListOf<String>()
    do {
        val readValue = next(size)
        output.add(readValue)
    } while (!stopCondition(readValue))
    return output
}

At one point in our parsing logic, we’ll want to keep reading Strings until we hit some stopping point. The wrinkle here is that we also want the value that causes us to stop parsing. Basically “Keep giving me Strings until you find a single one that matches some criteria, give me that String as well, and then stop parsing”. To do that we’ll define nextUntilFirst passing in the size of the String we want, and a function that determines our stopCondition. Note we could have passed functions for both of those things if the parsing had been more complicated.

// In Extensions.kt

fun <T> Iterator<Char>.executeUntilEmpty(function: (Iterator<Char>) -> T): List<T> {
    val output = mutableListOf<T>()
    while (this.hasNext()) {
        output.add(function(this))
    }
    return output
}

Finally, we’ll need a way to keep consuming the Iterator<Char> until it is empty. At some point in our parsing, we’re given a sub-sequence of characters and we want to consume them all, calling a function to do so. We’ll define executeUntilEmpty which is given a function that takes an Iterator<Char> and returns some type T. So long as the iterator has more characters to give, we’ll execute the function and return all of the results from that function as a List.

Again, we’ve defined all of these in Extensions.kt as they seem generic enough.

Now we have to parse our input, but thanks to the work we’ve done, we have all of the tools. To do this, we’ll create a sealed class hierarchy. Our base class will be called BITSPacket and it will have two subclasses - BITSLiteral and BITSOperator. Note that we’re defining these as private in Day16. If we end up needing them for a future day, we’ll pull it out and put it in its own class. Each BITSPacket instance will have a few things: a version, a value and a function to return all of the versions (called allVersions) just to make life a bit easier.

// In Day16

private sealed class BITSPacket(val version: Int) {
    abstract val value: Long

    companion object {
        fun of(input: Iterator<Char>): BITSPacket {
            val version = input.nextInt(3)
            return when (val packetType = input.nextInt(3)) {
                4 -> BITSLiteral.of(version, input)
                else -> BITSOperator.of(version, packetType, input)
            }
        }
    }

    abstract fun allVersions(): List<Int>
}

We’ll follow the convention for parsing that we’ve followed all month - a function called of inside a companion object. The of function in BITSPacket is responsible for parsing and setting aside the version and figuring out which packetType we have. Once it knows that, it passes this information and (most critically) the input iterator to the appropriate subclass.

Let’s work with BITSLiteral next, since it is simpler than the BITSOperator:

// In Day16

private class BITSLiteral(version: Int, override val value: Long) : BITSPacket(version) {
    override fun allVersions(): List<Int> = listOf(version)

    companion object {
        fun of(version: Int, input: Iterator<Char>): BITSLiteral =
            BITSLiteral(version, parseLiteralValue(input))

        private fun parseLiteralValue(input: Iterator<Char>): Long =
            input.nextUntilFirst(5) { it.startsWith('0') }.map { it.drop(1) }.joinToString("").toLong(2)
    }
}

As we can see the BITSLiteral constructor takes in a version and a value. We can define allVersions as a simple list containing a single element (our version) since BITSLiteral only has one version and no subpacktes to contend with. Parsing is, again, a function called of inside the companion object. The main work here is done inside parseLiteralValue and uses our Iterator<Char>.nextUntilFirst function. We tell nextUntilFirst to keep giving us strings of length 5 until one of them starts with 0. We now have a List<String> where each string is 5 digits long. Because the first bit in each string is a control bit, we drop them. (Note: We could pass the drop call to joinToString and eliminate the map but it reads funny so I didn’t do that). We take all of these strings and join them into a single string via joinToString and then convert our big binary String into a Long, specifying that we are converting from base 2 (binary).

As you can see, BITSOperator is a bit more complicated because it has sub-packets:

// In Day16

private class BITSOperator(version: Int, type: Int, val subPackets: List<BITSPacket>) : BITSPacket(version) {
    override fun allVersions(): List<Int> =
        listOf(version) + subPackets.flatMap { it.allVersions() }

    override val value: Long = 0

    companion object {
        fun of(version: Int, type: Int, input: Iterator<Char>): BITSOperator {
            return when (input.nextInt(1)) { // Length Type
                0 -> {
                    val subPacketLength = input.nextInt(15)
                    val subPacketIterator = input.next(subPacketLength).iterator()
                    val subPackets = subPacketIterator.executeUntilEmpty { of(it) }
                    BITSOperator(version, type, subPackets)
                }
                1 -> {
                    val numberOfPackets = input.nextInt(11)
                    val subPackets = (1..numberOfPackets).map { of(input) }
                    BITSOperator(version, type, subPackets)
                }
                else -> error("Invalid Operator length type")
            }
        }
    }
}

The allVersions function in BITSOperator needs to take into account the fact that we have sub-packets. We do this by making a single list of our version and adding it to all the flatmapped versions of our subpacket versions. We don’t know what to do with value yet (this comes in part two!) so for now we’ll set it to 0. It shouldn’t be a surprise that parsing is done via a function called of in the companion. :)

We need to handle two ways to parse out the BITSOperator instances. Type 0 means need to extract a single Int representing our subPacketLength. Once we know that, we can take that many characters off our main iterator and set them aside. This subPacketIterator we’ve just created is separate from our main input iterator and will use it to parse out the sub-packets. This works well because we know the length of the encoded sub-packets and can treat that section of the input like a wholly separate parsing request. We parse each sub-packet by calling BITSPacket.of (I’ve left off the “BITSPacket” qualifier because we don’t need it)

The other way to handle sub-packet parsing is if we’re told the numberOfPackets to expect. This is a bit easier to handle in that we can map the results of calling BITSPacket.of until we’ve hit the right number of subPackets.

And with that, we can solve part one!

// In Day16

fun solvePart1(): Int =
    BITSPacket.of(binaryInput).allVersions().sum()

Star earned! Onward!

⭐ Day 16, Part 2

The puzzle text can be found here.

Remember how in part one we didn’t know what the value of a BITSOperator was? We do now! So we’ll erase our current implementation of value in BITSOperator and replace it with this:

// In BITSOperator

// REPLACE the existing implementation with this:

override val value: Long = when (type) {
    0 -> subPackets.sumOf { it.value }
    1 -> subPackets.fold(1) { acc, next -> acc * next.value }
    2 -> subPackets.minOf { it.value }
    3 -> subPackets.maxOf { it.value }
    5 -> if (subPackets.first().value > subPackets.last().value) 1 else 0
    6 -> if (subPackets.first().value < subPackets.last().value) 1 else 0
    7 -> if (subPackets.first().value == subPackets.last().value) 1 else 0
    else -> error("Invalid Operator type")
}

To me, this really shows off the power of the Kotlin standard library. Want to sum some numbers? Call sumOf. Want to get the product of some numbers? fold over them. minOf and maxOf return the min and max. This is so nice to look at. I did try to find one expression to handle the 5, 6, and 7 cases but it was klunky so I made them all the way you see them here. Not terrible.

And now we have enough to solve part two!

// In Day16

fun solvePart2(): Long =
    BITSPacket.of(binaryInput).value

Star earned! Onward!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading