News

Advent of Code 2021 in Kotlin, Day 3: Binary Diagnostic

The nautical advent-ure continues with the third day of AOC 2021, which we will, of course, once more solve in Kotlin! This time, it will involve wrangling binary numbers in all sorts of ways. Check out the solution and a detailed explanation on YouTube, or follow along as we explain our solution in this blog post!

Solving part 1

We’re on maintenance duty today: That means we’re working with a report of binary numbers. Our goal is to calculate two values in order to get our gold star. They are referred to as the gamma and epsilon rate in the original problem description, which you can find on adventofcode.com.

We calculate the gamma rate by determining the most common bit for each position of the binary numbers in our input. When there’s more “1” bits than “0” bits in a column, the resulting number will be a “1”. Or when it is the other way around, and we see more “0” bits than “1” bits, our result will have a “0” in that position. We repeat that process for each column in our inputs until we get the final gamma rate in binary representation.

The epsilon rate is calculated analogously to the gamma rate, only this time, it always looks at the least common bit in each position.

Once both numbers are calculated, we arrive at the answer – the power consumption of our submarine – by converting the two numbers to decimal, and multiplying them.

Let’s turn our intuitive understanding into a Kotlin program! These examples use the scaffolding provided by the Advent of Code Kotlin Template, but a standalone solution would look very similar.

Gamma rate: Most popular bits

From the problem description, we know that we are going to need to iterate our list of inputs (a list of binary strings) column by column. We can assume that all numbers in the input have the same length, so we can use the zero’th element, and save its indices into a variable via the indices function.

We can then loop over all the column indices, and count the number of ones and zeroes in that column to help us decide what we should do next. Ideally, we would like to use a function such as the following:

Since this is a pretty problem-specific function, the standard library does not come with an implementation for it. But with the power of extension functions, we can build this exact function ourselves! A simple implementation looks like this:

The function keeps track of the ones and zeroes, and returns them as a Pair (constructed via the infix function to).

We can still make this code a bit more expressive, by replacing the Pair return type with our own custom data class:

By having the function return an instance of BitCount, the zeroes and ones can be accessed explicitly, and our code has become a little bit more expressive:

Since BitCount is a data class, we can use a destructuring declaration to elegantly access the zeroes and ones directly instead of having to write the three lines above. This single line has the same effect:

Creating the string of binary numbers that makes up the gamma rate is now a matter of figuring out which bit is more popular, and concatenating all of these bits into a single string. To do so, we can use Kotlin’s buildString function, which gives us access to a StringBuilder. We can combine that with a short if-expression, and append the most common bit to the gammaRate string:

This makes up the first half of the solution for part 1. To see the calculated value, we can turn this string of binary digits back into a real integer using the toInt function, and telling it we’re looking at a base-2 number:

This outputs “22”! We can confirm that this is indeed the correct gamma rate for the given sample input by going back to adventofcode.com and carefully re-reading the instructions. Great!

Epsilon rate: The binary inverse

Moving on to the epsilon rate, we make use of the property we observed in our initial discussion: the epsilon rate is just the binary inverse of the gamma rate. Where you see a “1” in the gamma rate, there’s a “0” in the epsilon rate, and vice versa. Once again, using an extension function, the call site for the epsilon rate looks like this:

We can use a few primitives from the standard library to assemble the implementation for invertBinaryString: we use the asIterable function to get access to the individual characters, and use the joinToString function to turn each “0” into a “1” and each “1” into a “0”:

To get the final result, we multiply these two numbers together, and obtain the power consumption of the submarine, which we can submit and get our first gold star for the day!

Intermission: An alternative approach for the gamma rate

Before moving on to part 2 of the challenge, let’s reuse our knowledge that joinToString takes a transform function, and attempt to write a more functional version of the algorithm that calculates the gamma rate in this problem. We can combine the map function, a destructuring declaration, and joinToString to get the same result as the solution that uses a for-loop, buildString, and append:

Having seen both solutions, which one do you prefer? Feel free to let us know in the comments below, or on our YouTube video!

Here’s the complete implementation of part 1 again, for reference:

Solving part 2

For part 2, we once again multiply numbers together: this time, the oxygen generator rating, and the CO2 scrubber rating! You can find detailed instructions on how to calculate these numbers on adventofcode.com. We’ll also discuss the computation of the oxygen generator rating here as an example.

The algorithm once again iterates the numbers column by column again, determining the most frequent bit (or, in the case of the CO2 scrubber rating, the least frequent bit). Then, the process of elimination is applied: all numbers that don’t have the most frequent bit are removed, and only the numbers which have the most popular bit in the given position remain. Tiebreakers go to the numbers with “1” in a given position for the oxygen generator rating, and the inverse for the CO2 scrubber.

This process is repeated until only one number remains, which is our result.

Computing the oxygen generator rating

Let’s start by defining a small local function for it, and let’s fill in some logic. We can structure the function similarly to our solution for part 1. To implement the process of elimination, we need to keep track of all the candidate numbers (starting with all of the input). We then need to repeatedly filter the list to make sure only the numbers with the most common bit at any given position remain.

We can reuse our countBitsInColumn implementation to arrive at a solution that looks like this:

When coming up with this snippet, it’s important we take great care to ensure the if-condition handles tiebreakers correctly: If “0” and “1” are equally common, it keeps values with a “1” in the position being considered.

Because I made the choice to use an immutable list here, removing elements is done via the filter function, which creates a new list. This list can then be assigned to the candidates variable again. If you’d like, you can also try to use a mutable list, and use the removeIf function for this algorithm, instead.

The only candidate that should remain can be extracted from the collection via the single function, and then returned. This allows us to already check our first partial result:

Copy-pasting the CO2 implementation

We can get our quick-and-dirty implementation of the CO2 scrubber rating by copy-pasting the code we wrote a moment ago, and adjusting the filter condition to keep only those candidates that don’t have the most common bit:

Together with our previous partial solution, this is actually enough to get our second gold star for the day – multiply the numbers, run the program, and get your reward:

Removing duplication

Hopefully, you’ll agree at this point that our code could still be improved before we check it into our repository. Both co2Rating and oxyRating are essentially the same function, just with a different parameter. We only changed a single line of code in them – why would we want to have all that other code lying around as well? We can do better. We can define an enum class RatingType to distinguish between the types of ratings we want to calculate:

We can then turn one of the two rating functions into a multi-purpose implementation by using a when-statement based on the requested RatingType:

This code works the same, but is much more concise, and doesn’t contain duplications anymore. That’s much better!

We’re done!

That’s it! This code can go into our repository, and we can celebrate another problem solved, and hopefully some more Kotlin lessons learned.

If you’re coming up with your own solutions for Advent of Code, or if you’ve coded along to our videos, make sure to share your code on GitHub, and add the topic aoc-21-in-kotlin to your repo! This way you have a chance to win some Kotlin swag this holiday season! Check out the “Advent of Code 2021 in Kotlin” blog post for more details.

Enjoy yourself, keep warm, and take care!

image description