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

Sebastian Aigner

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.

fun main() {
    fun part1(input: List<String>): Int {
        TODO()
    }

    val testInput = readInput("Day03_test")
    val input = readInput("Day03")
    println("P1 Test: " + part1(testInput))
    check(part1(testInput) == 198)
    println("P1 Result: " + part1(input))
}

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:

val columns = input[0].indices
for(column in columns) {
    input.countBitsInColumn(column)
}

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:

private fun List<String>.countBitsInColumn(column: Int): Pair<Int, Int> {
    var zeroes = 0
    var ones = 0
    for(line in this) {
        if(line[column] == '0') zeroes++ else ones++
    }
    return zeroes to ones
}

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:

private data class BitCount(val zeroes: Int, val ones: Int)

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:

val bitCount = input.countBitsInColumn(column)
val zeroes = bitCount.zeroes
val ones = bitCount.ones

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:

val (zeroes, ones) = input.countBitsInColumn(column)

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:

val gammaRate = buildString {
    for (column in columns) {
        val (zeroes, ones) = input.countBitsInColumn(column)
        val commonBit = if (zeroes > ones) "0" else "1"
        append(commonBit)
    }
}

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:

return gammaRate.toInt(2)

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:

val epsilonRate = gammaRate.invertBinaryString()

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”:

private fun String.invertBinaryString() = this
    .asIterable()
    .joinToString("") { if (it == '0') "1" else "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!

return gammaRate.toInt(2) * epsilonRate.toInt(2)

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:

val gammaRate2 = columns
    .map { input.countBitsInColumn(it) }
    .joinToString("") { (zeroes, ones) ->
        if (zeroes > ones) "0" else "1"
    }

check(gammaRate == gammaRate2)

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:

fun part1(input: List<String>): Int {
    val columns = input[0].indices
    val gammaRate = buildString {
        for (column in columns) {
            val (zeroes, ones) = input.countBitsInColumn(column)
            val commonBit = if (zeroes > ones) "0" else "1"
            append(commonBit)
        }
    }
    val gammaRate2 = columns
        .map { input.countBitsInColumn(it) }
        .joinToString("") { (zeroes, ones) ->
            if (zeroes > ones) "0" else "1"
        }
    check(gammaRate == gammaRate2)
    val epsilonRate = gammaRate.invertBinaryString()
    return gammaRate.toInt(2) * epsilonRate.toInt(2)
}

private fun String.invertBinaryString() = this
   .asIterable()
   .joinToString("") { if (it == '0') "1" else "0" }

private fun List<String>.countBitsInColumn(column: Int): BitCount {
   var zeroes = 0
   var ones = 0
   for (line in this) {
       if (line[column] == '0') zeroes++ else ones++
   }
   return BitCount(zeroes, ones)
}

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:

fun oxyRating(): String {
    val columns = input[0].indices
    var candidates = input
    for(column in columns) {
        val (zeroes, ones) = candidates.countBitsInColumn(column)
        val mostCommon = if (zeroes > ones) '0' else '1'
        candidates = candidates.filter { it[column] == mostCommon }
        if(candidates.size == 1) break
    }
    return candidates.single()
}

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:

return oxyRating().toInt(2)

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:

fun co2Rating(): String {
    val columns = input[0].indices
    var candidates = input
    for (column in columns) {
        val (zeroes, ones) = candidates.countBitsInColumn(column)
        val mostCommon = if (zeroes > ones) '0' else '1'
        candidates = candidates.filter { it[column] != mostCommon }
        if(candidates.size == 1) break
    }
    return candidates.single()
}

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:

return oxyRating().toInt(2) * co2Rating().toInt(2)

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:

private enum class RatingType {
    OXYGEN,
    CO2
}

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:

fun part2(input: List<String>): Int {
    fun rating(type: RatingType): String {
        val columns = input[0].indices
        var candidates = input
        for (column in columns) {
            val (zeroes, ones) = candidates.countBitsInColumn(column)
            val mostCommon = if (zeroes > ones) '0' else '1'
            candidates = candidates.filter {
                when (type) {
                    RatingType.OXYGEN -> it[column] == mostCommon
                    RatingType.CO2 -> it[column] != mostCommon
                }
            }
            if (candidates.size == 1) break
        }
        return candidates.single()
    }
    return rating(RatingType.OXYGEN).toInt(2) * rating(RatingType.CO2).toInt(2)
}

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!

Subscribe to Kotlin Blog updates

Subscribe form

By submitting this form, I agree to the JetBrains Privacy Policy Notification icon

By submitting this form, I agree that JetBrains s.r.o. ("JetBrains") may use my name, email address, and location data to send me newsletters, including commercial communications, and to process my personal data for this purpose. I agree that JetBrains may process said data using third-party services for this purpose in accordance with the JetBrains Privacy Policy. I understand that I can revoke this consent at any time in my profile. In addition, an unsubscribe link is included in each email.

Submit

Thanks, we've got you!