Advent of Code 2025: Day 2

Problem

tl;dr — You’re given product ID ranges in the format start-end,start-end,... (e.g., 11-22,95-115,998-1012). Find all “invalid” IDs and sum them up.

Part 1: An ID is invalid if it consists of some sequence of digits repeated exactly twice.

55 → “5” × 2 (invalid)
6464 → “64” × 2 (invalid)
123123 → “123” × 2 (invalid)
111 → “1” × 3 (valid — not exactly twice)
No leading zeroes (so 0101 isn’t a valid ID format)

Part 2: An ID is invalid if it consists of some sequence of digits repeated at least twice.

55 → “5” × 2 (invalid)
111 → “1” × 3 (now invalid!)
12341234 → “1234” × 2 (invalid)
123123123 → “123” × 3 (invalid)
1212121212 → “12” × 5 (invalid)

Range	Part 1 Invalid IDs	Part 2 Invalid IDs
`11-22`	11, 22	11, 22
`95-115`	99	99, 111
`998-1012`	1010	999, 1010
`565653-565659`	—	565656
`824824821-824824827`	824824824	824824824

My Solution (Handcrafted)

Part 1: Split and Compare

Part 1 was straightforward — just split the string in half and compare:

pub fn is_invalid_1(id: u64) -> bool {
    let id_str = id.to_string();
    if id_str.len() % 2 != 0 {
        return false;
    }

    return id_str[..id_str.len() / 2] == id_str[id_str.len() / 2..];
}

Clean and simple! If the length is odd, it can’t be two equal halves. Otherwise, slice and compare.

Part 2: The Brute Force Approach (First Attempt)

Part 2 was trickier. My initial thought was to find a mathematical pattern — for xxyyxxyy, dividing by xxyy should work. But I couldn’t derive a clean formula, so I pivoted to string matching:

pub fn is_invalid_2(id: u64) -> bool {
    let id_str = id.to_string();
    for i in 1..=id_str.len() / 2 {
        let repeat_part = id_str[..i].to_string();

        let repeat_count = id_str.matches(&repeat_part).count();

        if repeat_count * i == id_str.len() {
            return true;
        }
    }
    false
}

The logic: Try every possible pattern length from 1 to half the string. Use .matches() to count occurrences. If count × pattern_length == total_length, we have a valid repetition.

The problem: .matches() uses recursion under the hood, making this O(n²) in the worst case. It works, but it’s not elegant.

Part 2: Optimized String Version

After discussing with Gemini, I realized I could keep the string logic but make it smarter:

pub fn is_invalid_2_optimized(id: u64) -> bool {
    let s = id.to_string(); // Only 1 allocation per number
    let n = s.len();

    // We only need to check lengths that divide the total length perfectly
    // e.g., if length is 6, checking a pattern of length 4 is useless (6 % 4 != 0)
    for len in 1..=n / 2 {
        if n % len == 0 {
            let pattern = &s[..len];
            let repetitions = n / len;

            // Check if repeating the pattern creates the original string
            if pattern.repeat(repetitions) == s {
                return true;
            }
        }
    }
    false
}

Key optimizations:

Skip impossible lengths — if n % len != 0, skip immediately
Use .repeat() — cleaner than counting matches
Single allocation — only one to_string() call

Gemini’s Solution: Pure Math

Gemini took a completely different approach — no string manipulation at all!

Part 1: The Divisor Trick

fn is_invalid_id_1(n: u64) -> bool {
    if n < 10 {
        return false;
    }

    let digits = n.ilog10() + 1;

    // If the number of digits is odd, it cannot be two equal halves.
    if digits % 2 != 0 {
        return false;
    }

    // Mathematical Check:
    // If n looks like "XYXY" (digits), mathematically n = XY * 10^k + XY
    // which factors to n = XY * (10^k + 1).
    let half_digits = digits / 2;
    let divisor = 10u64.pow(half_digits) + 1;

    n % divisor == 0
}

The insight: 123123 = 123 × 1000 + 123 = 123 × 1001. So any repeated number must be divisible by 10^k + 1!

Part 2: The Repeater Mask

fn is_invalid_id_2(n: u64) -> bool {
    if n < 10 {
        return false;
    }

    let digits = n.ilog10() + 1;

    // Try all possible repetition counts 'k' from 2 up to total digits.
    for k in 2..=digits {
        if digits % k == 0 {
            let s = digits / k; // 's' is the size of the repeating sequence

            // Construct the "repeater" number mathematically.
            // If sequence size s=2 and repeats k=3 times, repeater is 10101.
            let mut repeater = 0u64;
            for i in 0..k {
                repeater += 10u64.pow(i * s);
            }

            if n % repeater == 0 {
                // Verify that the base sequence fits within 's' digits.
                if (n / repeater) < 10u64.pow(s) {
                    return true;
                }
            }
        }
    }
    false
}

The Math Behind It

When I asked Gemini to explain the formula, here’s what I learned:

The Structure of Repetition

A repeated number can be factored into: Base Value × Repeater Mask

For 123123 (123 repeated twice):

$123123 = 123000 + 123 = 123 \times 1000 + 123 \times 1 = 123 \times 1001$

General formula: If sequence $X$ with length $L$ is repeated $k$ times:

$N = X \cdot (10^{(k-1)L} + 10^{(k-2)L} + ... + 10^L + 1)$

The term in parentheses is the Repeater Mask.

Why False Positives Don’t Happen

You might wonder: “What about 884? It’s divisible by 4, but 884 ≠ 44 × 2.”

The trick is we divide by the Repeater Mask, not the base value:

For 3-digit repetitions (k=3, L=1): Repeater = 111
444 / 111 = 4 (remainder 0, valid)
884 / 111 = 7.96... (remainder 107, invalid)

The Overflow Edge Case

There’s one tricky case: 10201 passes the divisibility check for 101 (2-digit pattern, k=2):

$10201 \div 101 = 101$

But 101 is a 3-digit number — it doesn’t fit in the 2-digit “slot”! Hence the safety check:

$\text{Base} < 10^L$

Comparison: String vs Math

Aspect	My String Solution	Gemini’s Math Solution
Approach	Pattern repeat + compare	Divisibility by repeater
Complexity	O(n²) worst case	O(n) per number
Readability	Intuitive, easy to follow	Requires math understanding
Allocations	1 string per number	Zero allocations
Debug-ability	Easy to step through	Harder to trace edge cases

Follow-Up: Best of Both Worlds

After reviewing my code, Gemini pointed out something valuable:

“You don’t need to derive a complex formula to make your code fast! You can keep your string logic but make it efficient.”

The optimized string version (is_invalid_2_optimized) is the sweet spot:

Readable — the logic is obvious
Efficient — skips impossible lengths, uses .repeat()
Reliable — no tricky math edge cases to worry about

For production code, I’d choose the optimized string version. For competitive programming where every millisecond counts, Gemini’s math approach wins.

Reflection

Gemini excels at pattern recognition — it immediately saw the mathematical structure I was fumbling toward
Code review with AI is valuable — even when my solution worked, Gemini helped me understand why it worked and how to improve it
Sometimes “brute force” is the right choice — my string-based approach is more maintainable, even if it’s technically slower
The best solution depends on context — production vs. competitive programming have different priorities

Time spent: ~25 minutes (including the math rabbit hole)