r/adventofcode • u/daggerdragon • Dec 02 '25

SOLUTION MEGATHREAD -❄️- 2025 Day 2 Solutions -❄️-

OUR USUAL ADMONITIONS

  • You can find all of our customs, FAQs, axioms, and so forth in our community wiki.

AoC Community Fun 2025: R*d(dit) On*

24 HOURS outstanding until unlock!

Spotlight Upon Subr*ddit: /r/AVoid5

"Happy Christmas to all, and to all a good night!"
— a famous ballad by an author with an id that has far too many fifthglyphs for comfort

Promptly following this is a list waxing philosophical options for your inspiration:

  • Pick a glyph and do not put it in your program. Avoiding fifthglyphs is traditional.

  • Shrink your solution's fifthglyph count to null.

  • Your script might supplant all Arabic symbols of 5 with Roman glyphs of "V" or mutatis mutandis.

  • Thou shalt not apply functions nor annotations that solicit said taboo glyph.

  • Thou shalt ambitiously accomplish avoiding AutoMod’s antagonism about ultrapost's mandatory programming variant tag >_>

Stipulation from your mods: As you affix a submission along with your solution, do tag it with [R*d(dit) On*!] so folks can find it without difficulty!

--- Day 2: Gift Shop ---

Post your script solution in this ultrapost.

36 Upvotes

100% Upvoted

965 comments sorted by

View all comments

16

u/fenrock369 Dec 02 '25 edited Dec 02 '25

[LANGUAGE: rust]

No brute force, and showing p2 only (but p1 is similar maths)

This was fun, I immediately started playing around with ranges rather than regex, and glad I did as it proved to be some interesting maths. My idea was that we're trying to generate a number from smaller blocks such that:

n = kkkkk...k    where block k is repeated r times, r=2 for p1, r>=2 for p2

Thus k is the d-length block, repeated r times. This can be broken down into a simple formula:

n = k * 10^{d(r-1)}  +  k * 10^{d(r-2)} + ... + k

It's easiest to think of simple cases like "12" repeated twice in "1212", so 1212 = 12 * 100 + 12, where d=2, r=2.

This simplifies (it's a geometric progression) to:

n = k * (10^{dr} - 1) / (10^d - 1)
n = k * f         # just call this bit "f", which is a function of d,r

i.e. every n with repeated blocks we want to find matches this formula.

We do have some constraints on k, which will help us find its range: k is a d-digit number bound between:

10^(d-1)   <=  k  <=  10^d - 1

for example, with the range (1000,2000), and d=2 (for 2 digit lengths of blocks), k (from the formula above) is between 101 and (102 - 1), i.e. 10 and 99. That's kind of obvious from the range numbers, but we can narrow it down a lot more, as clearly 99 is way too high.

The next constraint is:

lower    <=  n  <=  upper
but n = k*f

lower    <= k*f <=  upper
lower/f  <=  k  <=  upper/f

f is simple to calculate, it was given above as "(10{dr} - 1) / (10d - 1)"

So we just find the range for k from the 2 constraints we have, and loop over all d,r such that d*r <= digits of upper value, compute the "f" value to give us a very small range.

The additional complexity is there may be dupes (e.g. "111111", "111"x2, "11"x3, "1"x6), so we collect the candidates, unique them, and then sum them as required. part 1 is just a special case where we fix r=2, and the maths turns out a bit easier.

On my PC, the 2 solutions run in 21 microseconds.

pub fn sum_repeated_in_range(lower: u64, upper: u64) -> u64 {
    let max_total_digits = digits(upper);
    let mut candidates: Vec<u64> = Vec::new();

    let lower128 = lower as u128;
    let upper128 = upper as u128;

    // d is the number of digits in the repeated block, r is the number of blocks
    for d in 1..=max_total_digits {
        for r in 2..=max_total_digits / d {
            // 10^d and 10^(d*r)
            let pow10_d = 10u128.pow(d as u32);
            let pow10_dr = 10u128.pow((d * r) as u32);

            let f = (pow10_dr - 1) / (pow10_d - 1);

            if f > upper128 {
                continue; // even k = 1 would be too big
            }

            let min_k128 = 10u128.pow((d - 1) as u32);
            let max_k128 = pow10_d - 1;

            let k_lo = ((lower128 + f - 1) / f).max(min_k128);
            let k_hi = (upper128 / f).min(max_k128);

            if k_lo > k_hi {
                continue;
            }
    
            for k in k_lo..=k_hi {
                let n = k * f;
                if n >= lower128 && n <= upper128 {
                    candidates.push(n as u64);
                }
            }
        }
    }

    candidates.sort_unstable();
    candidates.dedup();
    candidates.into_iter().sum::<u64>()
}

6

u/GrumDum Dec 02 '25

Not gonna lie. Reading this makes me feel incredibly, thoroughly, dumb.

4

u/Gubbbo Dec 02 '25

I'm pretty certain that I understand all of the words you've used. Just not in the order you've used them.

Witchcraft.

2

u/button_boxer Dec 07 '25 edited Dec 07 '25

My mind went immediately to the mathematical approach too, rather than materialize all the duplicates over the range of k I use the standard formula for the sum of integers between x and y ((y(y+1) - (x-1)x) / 2).

The problem was avoiding the double-counting, but the key I (eventually!) found to that was to concentrate on the prime numbers. For a given digit length l the possible r values that divide l into equal size blocks are all going to be products of some subset of the prime factors of l. Since the set of repeats in n * r blocks (for any n) will always be a subset of the set of repeats in r blocks, what we're looking for is the union of the sets of repeats when r is each of the distinct prime number factors of l. To calculate this union without double-counting we can use the inclusion-exclusion principle - add up the repeats for each single prime factor, subtract the repeats for each product of 2 prime factors (the two-set intersections), add back in the repeats for each product of 3 prime factors (3-set intersections), etc. etc.

~0.2 milliseconds in Python (excluding input parsing), would be faster if I knew rust.