Advent of Code 2021 - Day 3, in Kotlin - Binary Diagnostic • Todd Ginsberg

I had a lot of fun with today’s puzzle. My code started out very messy, but because I have the day off work today I could spend some time refining it down to what we have here. I’m pretty happy with how this turned out, and this is a good opportunity to learn about a couple of lesser-known Kotlin standard library functions.

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

Problem Input

Our input file is delivered as individual rows so we will map them to a List<String> using our helper functions and hand them into our daily solution class:

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

}

⭐ Day 3, Part 1

The puzzle text can be found here.

Note If you were here before and saw a completely different solution, I’ve rethought my approach and this is far simpler.

Before starting, if we look at the example, epsilon and gamma are opposites of one another. If we calculate one, we can flip our 1s and 0s to get the other. So let’s use that to our advantage when we solve part 1. Let’s go through each element of the input column by column, and make a new binary String. This should give us gamma. If we flip all of the bits, we can get a String representing epsilon. Then all we have to do is convert the binary String into a decimal Int.

fun solvePart1(): Int {
    val gamma = input.first().indices.map { column ->
        if (input.count { it[column] == '1' } > input.size / 2) '1' else '0'
    }.joinToString("")

    val epsilon = gamma.map { if(it == '1') '0' else '1' }.joinToString("")

    return gamma.toInt(2) * epsilon.toInt(2)
}

Because all of our input strings are the same length, we can pick any one of them, so we’ll grab the first() one. Then, instead of setting up our own range we can use the indices function on String to do that for us. It will give us a range of all the valid indices we can address in the String. Next, we map values. We’ll count all of the values in all of the inputs for a specific column. If there are more 1s than 0s, we want our output String to have a 1 character in this column, otherwise a 0 column. At this point we have a List<Char>, so we’ll use joinToString() to format it properly into a String. We now have the binary representation of gamma as a String.

To calculate epsilon, we can reverse each digit of gamma and turn the resulting List<Char> into a String. The binary strings don’t do us much good, so to calculate our answer, we’ll call toInt(2) on teach of them, telling Kotlin that we’d like this String that represents a number in base 2 (binary) converted to an Int.

Multiply these together and we have our answer!

⭐ Day 3, Part 2

The puzzle text can be found here.

I’ve done enough Advent of Code puzzles to get pretty good at spotting the part of the description that people will ignore and will come back to bite them. In this puzzle, it is this line:

If 0 and 1 are equally common, keep values with a 1 in the position being considered.

I’d like to think that spotting things like this in Advent of Code puzzles has made me a better programmer, but who really knows, right? Anyway, the important thing to keep in mind here is that this calculation is 1-biased.

Let’s talk about what we want to do before solving this part. We’re going to follow a similar approach as we did in part 1 in that we will work in column order. We’ll go through each column from right to left, and do a series of filters on our list. As we filter, we’ll eventually get the list down to one single element, which we will take for our value. If we define this function the right way, we can reuse it for both the “take largest” and “take smallest” parts of the requirements.

First, let’s go over a handy function from the Kotlin standard library - partition. The partition function works on an Iterable (which our List<String> implements) and allows us to break it into two parts (partition it) based on a criteria we set. In our case, we’ll partition our input based on whether a specific column is a 1 or a 0.

If we combine this with a fold (see yesterday’s post for a good overview of folding ), we can successively remove unwanted elements from the list of binary strings until we get down to one single value.

// In Day03

private fun List<String>.bitwiseFilter(keepMostCommon: Boolean): String =
    first().indices.fold(this) { inputs, column ->
        if (inputs.size == 1) inputs else {
            val split = inputs.partition { it[column] == '1' }
            if(keepMostCommon) split.longest() else split.shortest()
        }
    }.first()

The first thing to notice about this function is that it takes a value - keepMostCommon. This allows us to reuse the logic for both parts of the calculation we eventually need to perform. This function sets up a fold over all possible column values, again using a range provided by indices. The state we carry along in the fold is the List<String> of binary strings. Within the fold’s lambda, the first thing we need to check is if we’ve already reduced the list down to a single element. If so, we’ll simply return the inputs as-is. Sure, it might mean the fold isn’t doing any real work towards the end, but I think that’s OK.

On the other hand, if the list still has more than one binary string, we partition the inputs based on whether the column we are looking at is a 1 or not. The resulting Pair<List<String>, List<String> will have all of the elements with 1 in the desired column in the first value, and everything else (0 valued columns) in the second column. We decide which one to keep via some handy extension functions (see below) and eventually reduce this List<String> down to a single String value, which we will return.

To make the code simpler, we’ll define some private extension functions:

// In Day03

private fun <T> Pair<List<T>,List<T>>.longest(): List<T> =
    if(first.size >= second.size) first else second

private fun <T> Pair<List<T>,List<T>>.shortest(): List<T> =
    if(first.size < second.size) first else second

The longest function, you’ll see compares via greater-than-or-equal-to (>=) as opposed to greater-than. This is where the 1-biased part comes in that I warned you about earlier. This is very easy to overlook, so don’t feel bad if this tripped you up! The shortest function can be written as the opposite of longest but without having to account for the 1-bias.

And now we can solve part 2:

// In Day03

fun solvePart2(): Int =
    input.bitwiseFilter(true).toInt(2) * input.bitwiseFilter(false).toInt(2)

Note that we call bitwiseFilter twice - once to keep the most common values and again to keep the least common values. Then we use toInt(2) to convert the resulting binary strings to decimal.

Star earned!

⭐ Day 3, Part 1

⭐ Day 3, Part 2

Further Reading