# Advent of Code 2021 - Day 3, in Kotlin - Binary Diagnostic

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 3: 'Binary Diagnostic'

Posted on

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!