Advent of Code 2024 - Day 11, in Kotlin - Plutonian Pebbles • Todd Ginsberg

If you’ve participated in Advent of Code in previous years, there are usually a couple of puzzles that seem to have a simple solution in part 1, but that same solution doesn’t scale for part 2. Today is one of those puzzles.

To solve today’s puzzle, we’ll recognize a couple of things things:

The order of the stones, while prominent in the puzzle description, is completely irrelevant. This is only narrative and does not change the calculations in any way at all.
If we look at a stone and blink once, it always changes in the same way. For example, if a stone has a 2 on it, and I blink, it now has a 4048 on it. This is true for all stones with a 2 on them. So once we know how one stone behaves by blinking a specific number of times, we know how they all behave with the same number of blinks.

Extending on those ideas, we’ll implement today’s solution as a recursive function that caches the results of its calculations. We’ll ask the function to look at a stone with a specific number on it and blink a specific number of times. Because this same question will be asked many times, we’ll benefit from caching our results as we calculate them.

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

Puzzle Input

Today, we will take our input as a single String and convert it to a List<Long> to represent the stones. This is done via split and map, which should be familiar by now if you’ve read any of my other posts.

We’ll also set up a class-wide cache which we will use to speed up our stone counting. Essentially, the key to the cache is a Pair<Long,Int> where the Long is a stone and the Int is how many blinks we have left to perform. The value is the number of stones this eventually turns into.


class Day11(input: String) {

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

    private val cache: MutableMap<Pair<Long, Int>, Long> = mutableMapOf()

}

⭐ Day 11, Part 1

The puzzle text can be found here.

Let’s do some housekeeping before we talk strategy. No matter what we do, we need to perform a couple of operations on Long that we don’t already have.

First to determine if a Long has an even number of digits. Sure, we could do some math here (originally, I had) but I found it confusing to look at and the very slight speedup was not worth the complexity. So we’ll convert the Long to a String and see if that has an even number of characters.

// In Day11

private fun Long.hasEvenDigits(): Boolean =
    toString().length % 2 == 0

Next, we need to split our Long in two without leading zeros. Again, there is a way to do this with math but I found it confusing and not worth the effort. So what we’ll do here is turn our Long into a String, substring out the two parts and return them as a List<Long>. Why a List and not a Pair<Long,Long>? We’ll see later.

// In Day11

private fun Long.split(): List<Long> {
    val s = toString()
    return listOf(
        s.substring(0, s.length / 2).toLong(),
        s.substring(s.length / 2, s.length).toLong()
    )
}

What we need next is a function to count up the number of stones generated by looking at a single stone and blinking some number of times. We will call this function blink and it will take in the stone we are looking at, how many times we should blink, and a key. The key is used for the cache and represents the Pair<Long,Int> - stone and blinks.

We don’t have to worry about key at all. It has a default value and I really only did this so I could turn blink() into a single expression more easily, because we use the key in a few places. Alternatively, we could have made blink take a Pair<Long,Int> directly, but I thought would be messy pulling first and second out all over the place.

Let’s see blink() and then go over it.

// In Day11

private fun blink(
    stone: Long, 
    blinks: Int, 
    key: Pair<Long, Int> = stone to blinks
): Long =
    when {
        blinks == 0 -> 1
        key in cache -> cache.getValue(key)
        else -> {
            val result = when {
                stone == 0L -> blink(1, blinks - 1)
                stone.hasEvenDigits() -> stone.split().sumOf { blink(it, blinks - 1) }
                else -> blink(stone * 2024, blinks - 1)
            }
            cache[key] = result
            result
        }
    }

First, because blink is recursive, we need to check our exit conditions. So if the number of blinks remaining is zero, we know there will only be 1 stone created (by not blinking at the one stone we have).

Next, we check if the key is in the cache. Meaning - have we seen this stone with this number of blinks to do? If so, we know the answer already so return that instead of calculating it again. This saves us a massive amount of time.

The inner when expression basically implements the algorithm set out in the problem description. If the stone is 0, we turn it into a 1 and call blink with the 1 stone we just made, with one less blink to do. If the stone hasEvenDigits, we split the stone in two and get the sumOf calling blink with each of the new stones created. Otherwise, we multiply the value of the stone by 2024 and call blink with that new stone.

At the end, we cache the result before returning it to the caller.

Next, we need a way to get the sumOf all the stones when we blink at them. We’ll write sumBlinks to do that.

// In Day11

private fun sumBlinks(times: Int): Long = 
    stones.sumOf { blink(it, times) }

Finally, we can solve part 1 by calling sumBlinks and telling it we want to blink 25 times.

// In Day11

fun solvePart1(): Long =
    sumBlinks(25)

Star earned! Onward!

⭐ Day 11, Part 2

The puzzle text can be found here.

Well look at that! Because we implemented the cache we can directly solve part 2 by calling sumBlinks with 75 instead of 25.

// In Day11

fun solvePart2(): Long =
    sumBlinks(75)

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading