Welcome to the North Pole! Your job is to find all of the invalid IDs that appear in the given ranges.

Github: GCaggianese/AoC-2025/D2

Puzzle Day 2: Gift Shop

• Values II-FF separated by comma, where II means initial range and FF the final (both included).

Input Structure

• No leading 0
• II < FF
• II is separated by - from FF
• Invalid IDs:
  • Reapeating patterns in the range
    • Ej. 11-22: $\forall x \in [11,22] \cap \mathbb{N}^+$, here is easy to see that the only repeating pair of patterns are 11 and 22.
    • Ej. 11-33: $\forall x \in [11,33] \cap \mathbb{N}^+$, the repeating patterns now include 33 [11, 22, 33].
  • Odd-length numbers are ALWAYS valid
    • 111 → 3 digits → can’t split in pairs (valid)
    • 22022 → 5 digits → same (valid)

Part 1: Even Palindromic Numbers

• The approach will be to recognize that “invalid IDs” are numbers that can be expressed as two identical parts
• We can generate them by the formula: $\text{Invalid} = d \times (10^n + 1)$ where:
  • n is half the number of digits
  • d is an n-digit base number

1. Mathematics behind:

   • For a 2n-digit number to be “invalid”, is easy, just $\text{left-part} = \text{right-part}$.
   • This can be expressed as: $\text{number} = d \times 10^n + d$ $\text{number} = d(10^n + 1)$
   • Where d is the n-digit “base” that repeats.

2. Examples by digits:

   1. 2 digits (n=1):

      • This case is elemental, just 11 multiples.

   2. 4 digits (n=2):

      • Multiplier: $10^2 + 1 = 101$
      • Valid d values: ${10, 11, …, 99}$
      • Invalid IDs: $1010, 1111, 1212, …, 9999$
      • Ex.: $1111 = 11 × 101$

   3. 6 digits (n=3):

      • … same logic as n=2 …

   4. 8 digits (n=4):

      • … same logic as n=3 …

   5. 10 digits (n=5):

      • Multiplier: $10^5 + 1 = 100001$
      • Valid d values: ${10000, 10001, …, 99999}$
      • Ex.: $1188511885 = 11885 × 100001$

3. Detection Algorithm:

   For any given value:

   1. Calculate digit count: $\text{digits} = \lfloor \log_{10}(\text{value}) \rfloor + 1$
   2. Check if even: $\text{digits} \equiv 1 \pmod{2} \implies \text{valid (skip)}$
   3. Calculate the multiplier: $M = 10^{n} + 1 \quad \text{where} \quad n = \frac{\text{digits}}{2}$
   4. Test divisibility: $\text{value} \equiv 0 \pmod{M} \implies \text{invalid}$

4. Odd-digit numbers are always valid:

   • Any number with odd digits cannot be split into two parts
   • Ex.: 111, 212, 11011 all have 3 or 5 digits
   • There’s no way to express them as $d \times (10^n + 1)\quad \text{where}\ n = \frac{\text{digits}}{2}$
   • Therefore all odd-digit numbers are valid.

5. Then:

   • No need to check each digit manually
   • Time complexity: O(1) per number

Part 2: Multiple Repetitions

• Now invalid IDs include patterns repeated at least twice (not just exactly twice)
• Examples: 111 (1×3), 123123123 (123×3), 1212121212 (12×5)

1. Extended Formula:

For a pattern of length $p$ repeated $k$ times:

\[\text{number} = s \times \frac{10^{k \cdot p} - 1}{10^p - 1}\]

Where:

• $s$ is the base pattern ($p$ digits)
• $k \geq 2$ is the repetition count
• Total digits: $d = k \times p$

1. Detection Algorithm:

For a number with $d$ digits:

1. Find all divisors of $d$ (excluding $d$ itself): these are possible pattern lengths
2. For each divisor $p$ where $p < d$:
   • Calculate $k = d / p$ (repetition count)
   • Calculate multiplier: $M = \frac{10^d - 1}{10^p - 1}$
   • Check if $\text{value} \equiv 0 \pmod{M}$
   • Verify pattern has exactly $p$ digits (no leading zeros)
   • If both true → invalid
3. Then:
   • Finding divisors: $O(\sqrt{d})$ where $d = \lfloor \log_{10}(\text{value}) \rfloor + 1$

Solution Using C

I built the solution using C and the amazing nob.h as no-build system. If you want to run it just bootstrap nob.c and then run ./nob; it will compile the solution which you can run by ./build/AoC-2025_D2