Advent of Code 2021 - Day 24, in Kotlin - Arithmetic Logic Unit • Todd Ginsberg

If we do what the problem tells us to do, we’ll never finish it. Writing an interpreter might sound like fun (it actually is!) but in this case, actually executing the instructions will be too slow to get us an answer in a reasonable time. An alternative solution is to analyze what the instructions are actually doing and implement the logic in another language (like Kotlin) and not run it 22,876,792,454,960 times (twice!).

All credit for this analysis goes to /u/i_have_no_biscuits and /u/etotheipi1 for figuring out what is actually going on here and saving me a few hours of refactoring (and my sanity). I have to say, I’m not a huge fan of this class of problem.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

The input is 14 sections consisting of 18 lines each. These sections are mostly the same except for three constants spread throughout, which we’ll call simply a, b, and c. We’ll parse the input to get a, b, and c and put them in a new Parameters class. To parse the actual constants out we’ll chunk our inputs into 18-line sections and fish out the constants which are at the ends of lines 4, 5, and 15 (indexing at zero).

class Day24(input: List<String>) {

    private val magicParameters: List<Parameters> = parseMagicParameters(input)

    private class Parameters(val a: Int, val b: Int, val c: Int)

    private fun parseMagicParameters(input: List<String>): List<Parameters> =
        input.chunked(18).map {
            Parameters(
                it[4].substringAfterLast(" ").toInt(),
                it[5].substringAfterLast(" ").toInt(),
                it[15].substringAfterLast(" ").toInt()
            )
        }
}

⭐ Day 24, Part 1

The puzzle text can be found here.

I mentioned before I’m not a huge fan of this kind of puzzle (recognizing, of course, that a tremendous amount of effort goes into Advent of Code, and that not every puzzle is what every developer likes). Basically, each of the 14 sections of the input we receive executes this function:

// In Day24

private fun magicFunction(parameters: Parameters, z: Long, w: Long): Long =
    if (z % 26 + parameters.b != w) ((z / parameters.a) * 26) + w + parameters.c
    else z / parameters.a

There is talk in the instructions about how dividing needs to round down, but Kotlin/Java do that for us automatically so we don’t have to do anything special to account for that.

Part one only asks for the largest number that works, but since part two asks for the smallest number that works, we’ll write one function called solve that calculates both.

// In Day24

private fun solve(): Pair<Long, Long> {
    var zValues = mutableMapOf(0L to (0L to 0L))
    magicParameters.forEach { parameters ->
        val zValuesThisRound = mutableMapOf<Long, Pair<Long, Long>>()
        zValues.forEach { (z, minMax) ->
            (1..9).forEach { digit ->
                val newValueForZ = magicFunction(parameters, z, digit.toLong())
                if (parameters.a == 1 || (parameters.a == 26 && newValueForZ < z)) {
                    zValuesThisRound[newValueForZ] =
                        minOf(zValuesThisRound[newValueForZ]?.first ?: Long.MAX_VALUE, minMax.first * 10 + digit) to
                            maxOf(zValuesThisRound[newValueForZ]?.second ?: Long.MIN_VALUE, minMax.second * 10 + digit)
                }
            }
        }
        zValues = zValuesThisRound
    }
    return zValues.getValue(0)
}

To calculate both the smallest and largest number, we’ll end up returning a Pair<Long,Long> that has the smallest number in first and the largest number in second. Since we’ll need to keep track of the values of z that we end up calculating, we’ll create MutableMap<Long,Pair<Long,Long>> called zValues where the key is z and the value is the min/max values found, taking care to seed it with 0 and 0,0. We’ll loop over our magicParmeters, much like the program we’re given does. Because we don’t want to overwrite our existing zValues until later, we create another MutableMap here to work with. We set up a loop over all the known z-values so far, using destructuring to extract the key (z) and the min/max values (minMax). Next we set up yet another loop over the digits 1 through 9 (I had this as 0 through 9 by mistake and it messed me up for a good while). Inside this inner loop, we call the magicFunction ands get a new z value back from it. If it is one of the ones we care about (there are many that we don’t!) we perform a subsequent calculation on it (the existing value times 10 plus the digit we’re looping over). Here again, we store both the minimum and maximum values so we don’t have to write this function twice or call it with a lambda. At the end of all this work, the z value 0 has our answer.

And to solve, we call this function and take the second part of the Pair returned (the largest z value).

// In Day24

fun solvePart2(): Long = 
    solve().first

Star “earned”! Onward.

⭐ Day 24, Part 2

The puzzle text can be found here.

Take the first part of the Pair<Long,Long> we returned from solve as part of part one:

// In Day24

fun solvePart2(): Long = 
    solve().first

Star “earned”.

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading