Advent of Code 2024: Day 11

Code for solutions available on GitHub.

Plutonian Pebbles

The out of memory saga.

Problem description

The input is just a space-separated list of numbers:

0 1 10 99 999

They all represent stones in a row with said number each written on them. However, these stones are weird. Every time you blink, they change! But they remain in a line. They change according to one of three rules:

1. 0s turn into 1s
2. If a stone’s number has an even number of digits, it gets replaced by two stones. Each gets one half of the digits, split down the middle. E.g. one stone with the number 1234 gets replaced by two stones with the numbers 12 and 34.
3. All other stones’ numbers get multiplied by 2024.

Part 1

This is one of those problems that can easily run out of memory if you do it naïvely. I will chronicle my first solution to part 1, which did not work for part 2. Then my solution to part 2. In the repo, part 1 is solved in the exact same manner as part 2. There’s no trace of this older solution.

First, what is a stone? As always, I began by modelling the problem with some data structure:

enum Stone {
    Number(u128),
    Split(Rc<RefCell<Stone>>, Rc<RefCell<Stone>>),
}

What the heck is that Split variant? Well, since Rust types have to have a defined size, you can’t define them in terms of themselves. So they need the outer Rc for some indirection. Then I want to be able to mutate each stone in a split. Hence the inner RefCell. Conceptually, this is actually just

enum Stone {
    Number(u128),
    Split(Stone, Stone),
}

If Rust allowed recursive types like this.

But why even this in the first place? Why not represent the line of stones with a simple Vec? Well, since there will be a lot of splitting, and the problem specifically pointed out that stones remain in a line and in the same order, I figured I would avoid the extra shuffling around of memory by creating a tree structure. Then we have a Vec of trees with a well-defined ordering still.

Consider the example given in the problem description. Initially, this is modelled as

0   -   1   -   10   -   99   -   999

But after one blink, 10 and 99 will split. Applying this and the other rules, the Vec<Stone> conceptually looks like this:

1   -   2024   -   X   -   X   -   2021976
                  / \     / \
                 1   0   9   9

Note how the last element stayed in place. No moving things around in the Vec. I figured I would need to traverse things in order somehow in part 2, so I modelled it this way to save on memmoves and Vec-growing.

But anyway, back to the problem at hand. The task is to figure out how many numbers will be in the list after 25 blinks. As you can imagine, this number will be pretty big. I wrote some code to traverse the Stones depending on whether they were simple numbers or trees of numbers:

impl Stone {
    fn count(self) -> usize {
        match self {
            Stone::Number(_) => 1,
            Stone::Split(a, b) => {
                a.borrow().count() + b.borrow.count()
            }
        }
    }
}

Then, this can simply be mapped over the Vec<Stone> after applying the rules 25 times:

stones
    .into_iter()
    .map(Stone::count)
    .sum()

And it’s complete.

Part 2

Part 2 simply asks: “What about after 75 blinks?”. This is where the naïve approach of actually saving every single number runs out of memory. Or maybe it doesn’t, I don’t know I simply stopped it when it took more than 10 seconds. Either way it’s a bad solution.

The description of part 2 reveals that there’s no reason to model them as in a line, or even the order of them. Also, all stones are fungible and get the rules applied to them at the same time. Instead of iterating over every single number in a loooooong list with deeeeeep trees, just store the count of each number you’ve seen in a HashMap and update it every blink.

let mut number_count = HashMap::<u128, u128>::new();

// Count all initial stone values
stones.into_iter().for_each(|stone| {
    number_count
        .entry(stone)
        .and_modify(|count| *count += 1)
        .or_insert(1);
});

// Blink blink blink
for _ in 0..75 {
    // Have to make a copy of the HashMap,
    // since entries are iterated over in
    // an arbitrary order.
    let mut copy = number_count.clone();
    for (number, count) in number_count.iter() {
        let num_digits = number.checked_ilog10().unwrap_or(0) + 1;

        // Rule 1
        if *number == 0 {
            *copy.entry(1).or_insert(0) += *count;

        // Rule 2
        } else if num_digits % 2 == 0 {
            let modulus = 10u128.pow((num_digits + 1) / 2);
            let left = number / modulus;
            let right = number % modulus;

            *copy.entry(left).or_insert(0) += *count;
            *copy.entry(right).or_insert(0) += *count;

        // Rule 3
        } else {
            *copy.entry(*number * 2024).or_insert(0) += *count;
        }

        // Update applies to all instances of
        // the current stone number.
        copy.entry(*number).and_modify(|c| *c -= *count);
    }

    // Write the copy back to finalize the update.
    number_count = copy;
}

number_count.values().sum()

This terminates much faster (9.9ms) than whatever the previous solution would have terminated in. And also fits in my RAM.

Reflections on a conjecture

This whole thing reminded me of the Collatz conjecture with simple rules for how to get from each number to the next. But obviously, this particular set of rules can’t make the numbers explode in size, otherwise it wouldn’t have been an Advent of Code problem. It must be provable that all numbers converge (or at least stay small in a loop, I suppose).

Rules 1 and 2 don’t really increase the number drastically. So no need to analyze them. Rule 1 just increments, and rule 2 increases the total count of numbers, but the numbers themselves are guaranteed to be smaller.

Rule 3 is more interesting though. It definitely makes numbers bigger. Can this ever get out of hand?

Well, rule 3 only applies to numbers with an odd amount of digits. If we write the odd-digit’ed number X in scientific notation, it looks like this:

X = c * 10^(2k)

A number with an odd amount of digits will have an even power of 10 in scientific notation and vice-versa. We multiply this by 2024, an even number:

X * 2024 = (c *  10^(2k)) * (2.024 * 10^3)
         = 2.024c * 10^(2k + 3)

An odd power of 10 in the result, meaning we will get an even number of digits. The next step will therefore guaranteed split the resulting number into half the amount of digits.

A number with an even amount of digits (odd power of 10, i.e. 10^(2n - 1)) will be split into two numbers with n + 1 digits. Thus their powers of 10 will be simply n, which in turn means all such numbers are strictly less than 10^(n + 1).

Taking these facts, and substituting n = k + 1 into the calculation for X * 2024:

X * 2024 = 2.024c * 10^(2n + 1)
→ X_a < 10^(n + 1) = 10^(k + 2)

Thus for an initial k greater than 2, i.e. X > 10000, this is guaranteed to make the odd-digit’ed numbers smaller after multiplying by 2024 and then splitting once. Restricting numbers to converge to less than 10000 means they fit in the HashMap nicely, which is why this solution is guaranteed to work. And which is why this is a valid problem to pose for Advent of Code.

I wrote all this mathematical hand-wavy proof down on an envelope on my desk in a moment of inspiration and figured I should share it here as well :)