Advent of Code 2025 - Day 2 Solution

Core Problem Description

Given a range of numbers, find all numbers within that range that are formed by concatenating multiple identical digit segments. For Part 1, we only need to find numbers formed by exactly two identical segments. For Part 2, we need to find numbers formed by any number of identical segments (at least two).

Thought Process

String-based Approach

The problem itself is not difficult. The simplest approach is to use string operations to determine if a number is composed of repeated segments. Specifically:

1. Convert the number to a string s.
2. Iterate over possible segment lengths k, from 1 to s.len() / 2.
3. For each segment length, check if the string length is divisible by k.
4. If divisible, extract the first segment part = &s[0..k], and check if s equals part repeated the appropriate number of times.
5. If a matching segment is found, the number is valid.

While this method is simple and intuitive, its time complexity is high, especially when dealing with large number ranges.

Mathematical Approach

Starting with Part 1’s requirement, consider how to mathematically determine if a number is formed by two identical segments.

Take the number 123123 as an example. We can express it as:

We can observe that for any even-length number, if it is formed by two identical $k$-digit segments, then it can be written in the form $part \times (10^{k} + 1)$, where $k$ is the length of $part$. Let’s denote $10^{k} + 1$ as $base$. The problem then reduces to checking if a number $x$ is divisible by $base$.

Based on this analysis, we can design the following algorithm:

1. For an even-length number $x$, calculate its length $L$.
2. Compute $k = L / 2$, and then $base = 10^{k} + 1$.
3. Check if $x$ is divisible by $base$.
4. If the condition is met, $x$ is valid.

This method has lower time complexity, as we only need one division operation per number. However, we still need to iterate over all numbers in the given range.

Reverse Thinking - Generation Method

Since we need to find all valid numbers, let’s think in reverse: directly generate these numbers instead of checking each number individually. For Part 1, we can generate all valid numbers with the following steps:

1. For a specific total digit length $L$, compute $k = L / 2$.
2. Compute $base = 10^{k} + 1$.
3. Iterate over all possible segment values $part$. If $part \times base$ falls within the given range, add it to the result set.

Going further, since the final requirement is the sum of all valid numbers, we can directly calculate this sum using the Gaussian summation formula without explicitly generating each number. The algorithm thus becomes:

1. For the given number range $[low, high]$ and each possible even total digit length $L$, compute $k = L / 2$, $base = 10^{k} + 1$, $left = 10^{k-1}$ and $right = 10^{k} - 1$.
2. Calculate the starting and ending values for $part$: $start = \max\left(\left\lceil \frac{low}{base} \right\rceil, left\right)$ and $end = \min\left(\left\lfloor \frac{high}{base} \right\rfloor, right\right)$.
3. Use the Gaussian summation formula to calculate the sum of $part$ values, then multiply by $base$ to get the final sum.

This way, the time complexity is dramatically reduced. We no longer need to iterate over each number but can directly compute the result. The complexity drops from approximately $O(N)$ to $O(\log N)$ (nearly linear with the number of digits, $\log_{10} N$).

Generalizing to Any Number of Segments

Building on the foundation from Part 1, we can attempt to generalize to Part 2, finding numbers formed by any number (at least two) of identical segments. For example, the number 121212 can be expressed as:

We can see that this essentially requires modifying the previously fixed $base$. For a number formed by $r$ identical segments, each of length $k$, we can define $base$ as:

Thus, a valid number can be expressed as:

Based on this, we can design the following algorithm:

1. For the given number range $[low, high]$ and each possible total digit length $L$, find all possible values for $k$ (where $k$ must be a divisor of $L$ and $k < L$).
2. For each $k$, compute $r = L / k$ and $base = \frac{10^{L} - 1}{10^{k} - 1}$.
3. Calculate the starting and ending values for $part$: $start = \max\left(\left\lceil \frac{low}{base} \right\rceil, left\right)$ and $end = \min\left(\left\lfloor \frac{high}{base} \right\rfloor, right\right)$, where $left = 10^{k-1}$, $right = 10^{k} - 1$.
4. Use the Gaussian summation formula to calculate the sum of $part$ values, then multiply by $base$ to get the partial sum for this $(L, k)$ pair.

But is this correct? Let’s think. Consider the number $666666$:

Similarly, for $12121212$:

A problem arises: the same number would be counted multiple times, leading to an incorrect sum. We need to ensure each number is counted only once.

Which numbers are counted multiple times? Precisely those numbers that can be formed using shorter segments. For example, $666666$ can be seen as formed from segment length $1$, so it gets counted again for segment lengths $2$ and $3$. Similarly, $12121212$ is counted for both segment lengths $2$ and $4$.

We can observe that if two segmentation $k_1$ and $k_2$ for the same total length $L$ satisfy $k_1$ being a divisor of $k_2$, then the segmentation with the longer segment length will include numbers generated by the segmentation with the shorter segment length. More formally: for a given total digit count $L$, the segmentation corresponding to a divisor $k$ will include all numbers generated by segmentation corresponding to divisors $d$ of $k$ (where $d$ is also a divisor of $L$).

This leads to a core deduplication idea: for each $L$, only consider segmentation where the repeat count $r$ (where $r = L/k$) is a prime number, then sum all results. Because any repeating pattern with a composite repeat count $r$ can be decomposed into smaller repeats with prime counts, and thus would already be included in the counts for prime $r$. Algorithmically, we can break this down into two steps:

1. Find all prime factors of $L$, denoted $r_1, r_2, \ldots, r_m$. Calculate the results corresponding to using each $r_i$ as the repeat count.
2. Use the inclusion-exclusion principle to remove overlapping counts. Since prime numbers are co-prime, the only possible overlap is the pattern where the segment length is $1$ (i.e., all digits identical). Therefore, we only need to subtract the contribution from the segment length $1$ pattern from the total sum.

This approach not only ensures correctness but also maintains high computational efficiency.

Core Algorithm Implementation

1
type Range = (u64, u64);
2

3
struct Puzzle {
4
    ranges: Vec<Range>,
5
}
6

7
impl Puzzle {
8

9
  fn prime_factors(mut n: u32) -> Vec<u32> {
10
      let mut factors = BTreeSet::new();
11
      while n.is_multiple_of(2) {
12
          factors.insert(2);
13
          n /= 2;
14
      }
15
      let mut divisor = 3;
16
      while divisor * divisor <= n {
17
          while n.is_multiple_of(divisor) {
18
              factors.insert(divisor);
19
              n /= divisor;
20
          }
21
          divisor += 2;
22
      }
23
      if n > 1 {
24
          factors.insert(n);
25
      }
26

27
      factors.into_iter().collect()
28
  }
29

30
  fn get_sum_invalid_ids(range: Range, n: u32, repeat: u32) -> u64 {
31
      // The pattern repeats every k = n / repeat digits
32
      let k = n / repeat;
33
      // Calculate the lower and upper bounds for n-digit numbers with the given
34
      // pattern
35
      let upper = 10u64.pow(n) - 1;
36
      let base = upper / (10u64.pow(k) - 1);
37
      let lower = 10u64.pow(k - 1) * base;
38
      // Get the overlap between the given range and (lower, upper)
39
      let (start, end) = range;
40
      let start = start.max(lower);
41
      let end = end.min(upper);
42
      // Convert back to the base range
43
      let start = start.div_ceil(base);
44
      let end = end / base;
45
      if start > end {
46
          return 0;
47
      }
48

49
      (end - start + 1) * (start + end) / 2 * base
50
  }
51
}
52

53
impl Solution for Puzzle {
54
    fn part1(&self) -> String {
55
        self.ranges
56
            .par_iter()
57
            .map(|&(start, end)| {
58
                let min_n = start.ilog10() + 1;
59
                let max_n = end.ilog10() + 1;
60

61
                (min_n..=max_n)
62
                    .filter(|n| n % 2 == 0)
63
                    .map(|n| Self::get_sum_invalid_ids((start, end), n, 2))
64
                    .sum::<u64>()
65
            })
66
            .sum::<u64>()
67
            .to_string()
68
    }
69

70
    fn part2(&self) -> String {
71
        self.ranges
72
            .par_iter()
73
            .map(|&(start, end)| {
74
                let min_n = start.ilog10() + 1;
75
                let max_n = end.ilog10() + 1;
76

77
                (min_n..=max_n)
78
                    .filter(|&n| n > 1)
79
                    .map(|n| {
80
                        // Sum of all repeating digits (e.g., 1111, 2222, ..., 9999 for n=4)
81
                        let all_same = Self::get_sum_invalid_ids((start, end), n, n);
82
                        // Get all patterns with smaller, prime repeat factors
83
                        Self::prime_factors(n).into_iter().filter(|&k| k < n).fold(
84
                            all_same,
85
                            |mut sum, k| {
86
                                sum += Self::get_sum_invalid_ids((start, end), n, k);
87
                                sum -= all_same;
88
                                sum
89
                            },
90
                        )
91
                    })
92
                    .sum::<u64>()
93
            })
94
            .sum::<u64>()
95
            .to_string()
96
    }
97
}

Summary

The complete code can be found here.

Through in-depth analysis of the problem and the application of mathematical methods, we successfully transformed the task from one requiring iteration over a large number of candidates into an efficient computation problem. By leveraging the structural properties of numbers and the inclusion-exclusion principle, we not only improved algorithmic efficiency but also avoided complex conditional logic. Although the problem itself is not overly complex, the optimization process proved to be quite interesting.