Advent of Code 2025 is back, this time with only 12 puzzles, but as always they’re fun to do. We’re at Day 3, but I’m mostly impressed by Day 2, it has something special, and shows the genius behind the puzzle-making ❤️

Please make sure you take a look at it before reading further. Here’s a generated image to make sure you do not accidentally read the solution down below.

Part 1

In Part 1, you have to compute the sum of “invalid” identifiers. An invalid identifier is any number formed by repeating a sequence of digits twice:

• 99 has 9 repeated twice
• 1212 has 12 repeated twice too
• and so is 38593859 which has 3859 repeated twice

The input is an inclusive start-end range, and for each range you’ll have to find all invalid identifiers and sum them. For example 75-120 should return the sum 77 + 88 + 99.

This looks like a simple sum:

(start..=end).filter(is_invalid_id).sum();

Let’s look closer at is_invalid_id, we can already see that it must respect two conditions:

• Has an even number of characters
• First half == Second half

You can play with this solution on the playground. And it looks something like:

fn compute_sum(start: &str, end: &str) -> u64 {
    let start = start.parse::<u64>().unwrap();
    let end = end.parse::<u64>().unwrap();

    (start..end).filter(is_invalid_id).sum()
}

fn is_invalid_id(v: &u64) -> bool {
    let representation = v.to_string();
    // for odd length the two halfs wont have same size, which is fine
    let middle = representation.len() / 2;
    let (first, second) = representation.split_at(middle);
    first == second
}

This will run fast for the part 1 problem

Part 1: 3xxxxxxxxx3 (41.8ms)

Now what if I told you we could go down by a few orders of magnitude?

Part 1: 3xxxxxxxxx3 (3.4µs)

Yup, that’s more than 12_000x speedup.

Numbers, numbers everywhere

Let’s look again at our problem and take some examples:

• 99 > 9
• 1212 > 12
• 123123 > 123
• 38593859 > 3859

You might say, hey @moze, we know we’ve seen this before. And I might say, sure, but look closely, look at that beautiful number! Let’s decompose these numbers. Notice a pattern?

• 99 = 9 + 9 * 10
• 1212 = 12 + 12 * 100
• 123123 = 123 + 123 * 1000
• 38593859 = 3859 + 3859 * 1000

Yup, any invalid number of digits (i.e., even number of digits), can be written as where is the first half of the number .

Knowing that we can mathematically compute the sum of the first digits, we can play a bit with our formula above:

Where does our sum start and end? This depends on what I’ll be calling a bin. Each bin is a range of ( start) to (end), where is the first number with digits that fits in the initial range, and is the last one. For example, for an initial range = 75-1300, the first bin is 7-9 and the last bin is 10-12. Hence, our formula becomes:

The sum of numbers from to can be written using an arithmetic series formula as

where is the number of numbers in the bin. Which gives us a simple function to compute the sum of a bin:

fn main() {
    assert_eq!(compute_sum(7, 9, 1), 77 + 88 + 99);
    assert_eq!(compute_sum(10, 12, 2), 1010 + 1111 + 1212);
}

fn compute_sum(s: u64, e: u64, len: u32) -> u64 {
    let count = e - s + 1;
    let sum_base = count * (s + e) / 2;
    let multiplier = 10u64.pow(len) + 1;
    sum_base * multiplier
}

Now I leave it to you to find a simple way to find all the bins for a given range. As a hint, you can use this simple technique to find the start and end of a bin without checking for min and max, i.e. for the first bin you’ll get 1..9 rather than 7..9:

for len in 1..=4u32 {
    let min_seed = 10u64.pow(len - 1);
    let max_seed = 10u64.pow(len) - 1;
    println!("min = {min_seed}, max = {max_seed}");
}

Part 2

So you thought that we were done? Nah, the puzzle gets nicer, and you’ll have to throw most of what you’ve done in the first one :)

Now the invalid identifiers are not just a number repeated twice, but any number containing repeating blocks of digits.

• 99 is 9 twice
• 123123 is 123 two times
• 121212 is 12 three times
• 111111 is 1 six times
• etc.

We see that the same ideas as we had before apply here, notice that 121212 can be written as 12 + 12*10^2 + 12*10^4. That 123123 can be written 123 + 123*10^3, and 111111 can be written 1 + 1*10^1 + 1*10^2 + ... + 1*10^5.

Notice anything here? Each term is multiplied by a power of 10. That’s a geometric series, and there’s a closed-form formula for that. I will let you enjoy the rest of the puzzle 😄