# Advent of Code 2021 - Day 16, in Kotlin - Packet Decoder

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 16: 'Packet Decoder'

Posted on

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 `Char`s 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 {
return output
}
``````

At one point in our parsing logic, we’ll want to keep reading `String`s 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()) {
}
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!

1. Index of All Solutions - All posts and solutions for 2021, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 16
4. Advent of Code - Come join in and do these challenges yourself!