Advent of Code 2021 in Kotlin - Day 3

Day 3’s problem has us work out what the most common bit is per column concatenating them to find the gamma value. The epsilon value is the inverse.

Given the following input,

we’d have a gamma of 10110 and epsilon of 01001. The result is the product of the gamma and epsilon.

buildString provides a string builder as an expression, letting us yield characters and strings. I then use it again to flip the bits to get the epsilon value. To parse the strings as base 2 numbers we just need to specify the radix.

fun powerConsumption(data: List<String>): Int {
    val rowLength = data.first().length

    val gamma = buildString(rowLength) {
        for (c in 0 until rowLength) {
            val setBits = data.count { n -> n[c] == '1' }
            append (if (setBits >= data.size / 2) '1' else '0')
        }
    }

    val epsilon = buildString(rowLength) {
        gamma.forEach { append (if (it == '1') '0' else '1') }
    }

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

A criticism of this approach (and certainly not the only one) is that if epsilon ever needs to be something than gamma with flipped bits, this whole thing needs rewriting. We could use a string builder for each, like this:

fun powerConsumption(data: List<String>): Int {
    val rowLength = data.first().length

    val gamma = StringBuilder()
    val epsilon = StringBuilder()

    for (c in 0 until rowLength) {
        val setBits = data.count { n -> n[c] == '1' }
        if (setBits >= data.size / 2) {
            gamma.append('1')
            epsilon.append('0')
        } else {
            gamma.append('0')
            epsilon.append('1')
        }
    }
    
    return gamma.toString().toInt(2) * epsilon.toString().toInt(2)
}

I wouldn’t say we’ve improved on anything here. It may be better to write a function to calculate based on either most or least common bit and call it twice. Time complexity stays the same, although there’d be a tiny runtime hit.

enum class BitCommonality { Most, Least }

fun intFromCommonBit(data: List<String>, commonality: BitCommonality): Int {
    val rowLength = data.first().length

    return buildString(rowLength) {
        for (c in 0 until rowLength) {
            val setBits = data.count { n -> n[c] == '1' }
            append (when (Pair(commonality, setBits >= data.size/2)) {
                Pair(BitCommonality.Most, true) -> '1'
                Pair(BitCommonality.Most, false) -> '0'
                Pair(BitCommonality.Least, true) -> '0'
                Pair(BitCommonality.Least, false) -> '1'
                else -> throw Exception("I don't understand Kotlin match exhaustion")
            })
        }
    }.toInt(2)
}

val gamma = intFromCommonBit(data, BitCommonality.Most)
val epsilon = intFromCommonBit(data, BitCommonality.Least)

Interestingly, I was required to add an else branch to the when. I thought type inference would take care of that because there’s a clear finite list of possible values, but using Pair probably mucks that up. I’ll need to fiddle around with this some more later to see if there’s a better way to represent it.

On to part 2, where the problem changes a little bit. Instead, when we finding the most, or least, common bit in each column, we discard all rows that don’t have that bit. So if we’re looking for the most common bit in the first column of the example data above, we find that 1 is the most common and we discard all rows that have a 0 in that column. Conversely, if we’re looking for the least common bit, we would choose 0 and discard all rows with a 1 in that column. We then move on to the next column and do the same thing, but with a reduced amount of rows. If there are equal numbers of each bit, choose 1 for most common and 0 for least common.

In the problem, we find the “oxygen generator rating” by looking for the most common bit, and find the “CO2 scrubber rating” by looking for the least common bit. The answer, which gives us the “life support rating”, is the product of these two.

enum class BitCommonality { Most, Least }

fun getRating(data: List<String>, commonality: BitCommonality): Int {
    tailrec fun loop(pos: Int, remaining: List<String>): String {
        if (remaining.size == 1) return remaining.first()
        if (pos == remaining.first().length) throw Exception("not found")

        val setBits = remaining.count { it[pos] == '1' }

        val setIsMostCommonBit = setBits >= remaining.size - setBits
        val next = remaining.filter { it[pos] ==
            when (commonality) {
                BitCommonality.Most -> if (setIsMostCommonBit) '1' else '0'
                BitCommonality.Least -> if (setIsMostCommonBit) '0' else '1'
            }
        }

        return loop (pos + 1, next)
    }

    return loop(0, data).toInt(2)
}

val o2 = getRating(data, BitCommonality.Most)
val co2 = getRating(data, BitCommonality.Least)
val lifeSupport = o2 * co2

A recursive approach made sense here, and I tried something different with matching commonality and the most common bit - nested condition statements instead of a single when with a tuple. I like this less as the nested if needs to be replicated for each condition and could be the source of bugs, but the other way doesn’t work the way I had hoped. I’ll reach out to some Kotlin aware friends for help and update it with their advice.

Thanks for reading! Please feel free to send me an email to talk more about this (or anything else for that matter).