Advent of Code 2021 - Day 3

Devin McIntyre

Dec 3, 2021 • 5 min read

No time to waste, we're stuck in a submarine with a bunch of elves and need to get thing sorted stat!

Part 1: Why should any diagnostic report human readable?

Our submarine is well on its way, but we're hearing some disturbing creaking noises. Using our manual, we learn that the submarine can generate a diagnostics report for us, in the form of a list of binary numbers.

Our first goal is to use our new list of binary numbers to determine the oh so important (if completely unexplained¹) gamma and epsilon rates, from which we can determine the power consumption. We do this by finding the most common bit in each column of each number across the whole list. For example, in column one we have

which amounts to 5 zeros and 7 ones. From this we know that the gamma rate's first bit is one (the higher count) and the epsilon rate's first bit is 0 (the lower count). If we do this across all the columns, we find that the gamma rate is 10110 (22 in decimal) and the epsilon rate is 01001 (9 in decimal). Multiplying these together we get 198, and thus our power consumption.

There are two things to solve in this problem. The first is figuring out which of the two numbers a particular column prefers the second is to determine the gamma and epsilon rates based on this data. Here's my code for doing that:

data class ColumnData(var one: Int = 0, var zero: Int = 0)

fun day3(input: List<String>): Long {
    val positionTracker = mutableMapOf<Int, ColumnData>()
    input.forEach {
        for (i in it.indices) {
            val lastValue = positionTracker.getOrDefault(i, ColumnData())
            when (it[i]) {
                '1' -> lastValue.one += 1
                '0' -> lastValue.zero += 1
            }
            positionTracker[i] = lastValue
        }
    }

    // Now that we have a count of both ones and zeros for each column we can calculate gama and epsilon

    //Gamma is most common per column
    //Epsilon is the opposite
    var gamma = ""
    var epsilon = ""
    for (i in 0 until positionTracker.size) {
        val column = positionTracker[i]!!
        if (column.one > column.zero) {
            gamma += "1"
            epsilon += "0"
        } else {
            gamma += "0"
            epsilon += "1"
        }
    }

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

This is less complicated than it appears. The first iteration, the one that creates positionTracker just figures out the number of ones and zeros in each column position. This involves iterating over the list of strings, and then each index of each string, to find our count. We store this data in a map that pairs each index with a ColumnData object.

After that it's just a simple loop over each index. While I could have done positionTracker.values there is a chance that the order isn't guaranteed so I went with the safer loop approach. This lets us construct the binary number in string format for gamma and epsilon, followed by a stdlib conversion to a long, and a quick multiplication to get our power rate. First star in the bag!

Part 2: Breathing is important

Our next step is to check on our O2 and CO2 situation. As with all things on this submarine, our initial list of binary numbers can be used to find this information as well (What clever design!).

However, this time things are a bit more complicated. While the basic idea is similar (Start with a big list, accumulate knowledge about column data, generate output) we have a new twist. We start the same way, finding the most common bit for the first column, but rather than give us the first part of either the O2 or CO2 calculation, this instead gives us the "Bit Decider", which we use to then eliminate any data point in our list that doesn't have that particular bit in its column. For example, using the data above we know that the first column had 7 ones and 5 zeros. From there we can eliminate any of the values in the list without a one in the first position:

Now we repeat the process with the second bit, then the third bit, so on and so forth until we're left with only one value. That one value is either the O2 rating or the CO2 rating, depending on if you're taking the most found bit in a column (O2) or the least found (CO2).

Great! There are already some clear parallels between this part of the problem and the previous part. The important thing to remember though is that we need to recalculate the number of zeros and ones each iteration, as the number of inputs has likely changed.

So, to start we can start we can break out the positionTracker functionality we used in the first part into its own dedicated function, this will make reuse of it easier:

fun positionDataHelper(input: List<String>): Map<Int, ColumnData> {
    val positionTracker = mutableMapOf<Int, ColumnData>()
    input.forEach {
        for (i in it.indices) {
            val lastValue = positionTracker.getOrDefault(i, ColumnData())
            when (it[i]) {
                '1' -> lastValue.one += 1
                '0' -> lastValue.zero += 1
            }
            positionTracker[i] = lastValue
        }
    }
    return positionTracker
}

Now that we've extracted that for use, we can take a look at the other part of the problem. When determining the O2 and CO2 values we need to look through the input, making adjustments to the remaining list as we go, so we want to handle this in two different loops since the point that they finish is different. We could write some logic to handle it in one, but that's more brain drain than it's worth. A few minutes of coding gets us this:

fun day3Part2(input: List<String>): Long {
    // Figure out Oxygen
    var currentIndex = 0
    var oxygenValues = input
    val oxygenValue: String
    while (true) {
        val positionTracker = positionDataHelper(oxygenValues)
        val column = positionTracker[currentIndex]!!
        val bitCriteria = if (column.one >= column.zero) {
            '1'
        } else {
            '0'
        }
        oxygenValues = oxygenValues.filter { it[currentIndex] == bitCriteria }
        currentIndex++
        if (oxygenValues.size == 1) {
            oxygenValue = oxygenValues.first()
            break
        }
    }

    // Figure out CO2
    currentIndex = 0
    var co2Values = input
    val co2Value: String
    while (true) {
        val positionTracker = positionDataHelper(co2Values)
        val column = positionTracker[currentIndex]!!
        val bitCriteria = if (column.one >= column.zero) {
            '0'
        } else {
            '1'
        }
        co2Values = co2Values.filter { it[currentIndex] == bitCriteria }
        currentIndex++
        if (co2Values.size == 1) {
            co2Value = co2Values.first()
            break
        }
    }

    return co2Value.toLong(2) * oxygenValue.toLong(2)
}

And this works! We correctly get our value. And boom, second st- NO STOP. Come on now, we're not happy with this disaster of a function. We're duplicating code and logic all over the place! Before we get our second star let's do some clean-up. Right off the bat we can see that finding the O2 and CO2 ratings are using nearly identical methods. The only actual difference between them is how we decide what the bit decider is. Let's break that entire block out into a reusable function:

fun findRatingValue(input: List<String>, bitCriteriaDecider: (ColumnData) -> Char): String {
    var currentIndex = 0
    var values = input
    while (true) {
        val positionTracker = positionDataHelper(values)
        val column = positionTracker[currentIndex]!!
        val bitCriteria = bitCriteriaDecider(column)
        values = values.filter { it[currentIndex] == bitCriteria }
        currentIndex++
        if (values.size == 1) {
            return values.first()
        }
    }
}

There we go. By accepting in a function that knows how to determine the bit decider we've allowed ourselves the chance to reduce a ton of the code we had before. Our new part 2 function now looks like this:

fun day3Part22(input: List<String>): Long {
    // Figure out Oxygen
    val oxygenValue = findRatingValue(input) {
        if (it.one >= it.zero) '1' else '0'
    }
    val co2Value: String = findRatingValue(input) {
        if (it.one >= it.zero) '0' else '1'
    }
    return co2Value.toLong(2) * oxygenValue.toLong(2)
}

This is far more readable, creating clear self-documentation about what the code inside the findRatingValue function does. This is a much better solution, one we can feel good about, so let's go claim that star!

And that's it for Day 3! We've discovered more information about our submarine, but what else lurks down here in the depth with us!? The only way to know is the continue on and find out!

Notes

I'm sure gamma rate and epsilon rate have some clear and defined meanings, but I don't know them, and the site does nothing to explain it to us!

Part 1: Why should any diagnostic report human readable?

Part 2: Breathing is important

Notes

Sign up for more like this.