Advent of Code 2024 - Day 22, in Kotlin - Monkey Market • Todd Ginsberg

We’re coming to the end of Advent of Code 2024 and so far I’ve really enjoyed it. I had fun turning today’s puzzle solution into a single expression. I suspect I could get the 1s runtime for part 2 down a bit if I did things differently, but I’m happy with how this solution looks. We’ll write some higher-order functions, do some bit shifting, and break out zipWithNext - one of my favorites from the Kotlin Standard Library.

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

Puzzle Input

Today, we’ll take our input in from the test case as a List<String> and not declare it as a property as we’ll parse it right away. We’ll convert each of the String elements into a Long and store them in buyerNumbers.

class Day22(input: List<String>) {

    private val buyerNumbers: List<Long> = input.map { it.toLong() }

}

⭐ Day 22, Part 1

The puzzle text can be found here.

We need to mix and prune three times during our secret number generation process, so let’s define an extension function on Long to make that look a bit better. We’ll take in a function to describe what we are mixing and pruning, and return a new Long that has been mixed, pruned, and had the function applied.

// In Day22

private fun Long.mixAndPrune(function: (Long) -> Long): Long =
    (this xor function(this)) % 16777216L

Next, we need to generate the sequence of secret numbers. We’ll also define this as an extension function on Long but we’ll define it as a sequence using generateSequence. This will let us pull from this as long as we need to.

// In Day22

private fun Long.secretNumbers(): Sequence<Long> =
    generateSequence(this) { secret ->
        secret
            .mixAndPrune { it shl 6 }
            .mixAndPrune { it shr 5 }
            .mixAndPrune { it shl 11 }
    }

We call mixAndPrune three times, each time passing in a function representing the math we need to perform for that step in the process. It is worth noting that we can perform each of the operations by doing some bit shifting. Multiplying by 64 is the equivalent of shifting left 6 times, dividing by 32 is the equivalent of shifting right 5 times, and multiplying by 2048 is the equivalent of shifting left 11 times. How convenient!

We have enough to solve part 1. We get the sumOf the 2001st secret numbers from each buyerNumbers. We accomplish this by dropping the first 2000 and taking the first result.

// In Day22

fun solvePart1(): Long =
    buyerNumbers.sumOf {
        it.secretNumbers().drop(2000).first()
    }

Star earned! Onward!

⭐ Day 22, Part 2

The puzzle text can be found here.

Our strategy for Part 2 is going to be to go through the first 2001 secrets for each buyer, calculate a sequence of four deltas and the score they represent, take only unique instances per buyer, and adding those all to a map. If another buyer has added a sequence to score mapping, we add our score to that entry. The entry with the highest value is the answer to part 2.

fun solvePart2(): Int = buildMap {
    buyerNumbers
        .map { it.secretNumbers().take(2001).map { i -> (i % 10).toInt() }.toList() }
        .forEach { sequence ->
            sequence
                .windowed(5, 1)
                .map { it.zipWithNext { first, second -> second - first } to it.last() }
                .distinctBy { it.first }
                .forEach { (key, value) ->
                    this[key] = (this[key] ?: 0) + value
                }
        }
}.maxOf { it.value }

The entire solvePart2 function is within a buildMap which we build up as we go. Inside the buildMap, we go through each of the buyerNumbers, generate the sequence of 2001 secrets, and map them to perform a mod 10, which will reduce them down to the last digits. We store each of these in a List<Int>.

Next, we take this List<Int> and window it by 5, stepping over 1 entry each time (n.b. 1 is the default but I left it because I like the clarity). Now we have a Sequence<List<Int>> where the inner lists are 5 elements each. Each one of these needs to be turned into a delta list that is 4 elements long, where each value is the change between successive elements (this is why we need a list of 5 to create a list of 4 deltas). We can accomplish this with Kotlin’s handy zipWithNext function. Usually we see the form of this function without a lambda, but in this case we want it to do a mapping for us (subtracting first from second to create the delta. This is joined together into a Pair<List<Int>, Int> where the last element of the unzipped sequence is the value of the last element in the List<Int> of 5. This is how much this set of deltas is worth.

Because we only want to take the first instance of any sequence of 4 deltas from any one buyer, we filter this using distinctBy, specifying we want the first part of the pair.

Finally, we maintain the Map we’re building. We add the value (the score) to the map’s existing value, taking care to assume that value is 0 if not already in the Map. At this point we have a Map<List<Int>, Int>, where the key is the list of 4 deltas and the value is the cumulative score of that delta across all buyers.

Taking the maximum value in the map (via maxOf) gives us the answer to Part 2.

Start earned! See you tomorrow!

Puzzle Input

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading