year2025/
day02.rs

1use utils::prelude::*;
2
3/// Finding numbers with repeated digit patterns within ranges.
4#[derive(Clone, Debug)]
5pub struct Day02 {
6    input: Vec<[u64; 2]>,
7}
8
9impl Day02 {
10    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
11        Ok(Self {
12            input: parser::u64()
13                .repeat_n(b'-')
14                .repeat(b',', 1)
15                .parse_complete(input)?,
16        })
17    }
18
19    #[must_use]
20    pub fn part1(&self) -> u64 {
21        self.invalid_id_sum(|repeats| repeats == 2)
22    }
23
24    #[must_use]
25    pub fn part2(&self) -> u64 {
26        self.invalid_id_sum(|repeats| repeats > 1)
27    }
28
29    fn invalid_id_sum(&self, repeat_filter: impl Fn(u32) -> bool) -> u64 {
30        let mut total = 0;
31        let mut patterns = Vec::new();
32
33        for &[start, end] in &self.input {
34            let min_digits = start.checked_ilog10().unwrap_or(0) + 1;
35            let max_digits = end.checked_ilog10().unwrap_or(0) + 1;
36            for repeat_digits in 1..=max_digits / 2 {
37                for digits in (min_digits.next_multiple_of(repeat_digits)..=max_digits)
38                    .step_by(repeat_digits as usize)
39                {
40                    let repeats = digits / repeat_digits;
41                    if !repeat_filter(repeats) {
42                        continue;
43                    }
44
45                    let pow10 = 10u64.pow(repeat_digits);
46
47                    // Mask that repeats the pattern (e.g. 1,001,001 for 3x 3 digits)
48                    let repeat_mask = (0..repeats).fold(0, |acc, _| acc * pow10 + 1);
49
50                    // Smallest number matching the repeated pattern that is >= start
51                    let range_start = if digits == min_digits {
52                        // Repeat the highest N digits of start, + repeat_mask if smaller than the start
53                        let x = (start / 10u64.pow(min_digits - repeat_digits)) * repeat_mask;
54                        if x < start { x + repeat_mask } else { x }
55                    } else {
56                        (pow10 / 10) * repeat_mask
57                    };
58
59                    // Largest number matching the repeated pattern that is <= end
60                    let range_end = if digits == max_digits {
61                        let x = (end / 10u64.pow(max_digits - repeat_digits)) * repeat_mask;
62                        x.min(end)
63                    } else {
64                        (pow10 - 1) * repeat_mask
65                    };
66
67                    if range_start > range_end || range_end > end {
68                        continue;
69                    }
70
71                    patterns.push((range_start, range_end, repeat_mask));
72                }
73            }
74
75            // Merge and deduplicate multiple sequences
76            while patterns.len() > 1 {
77                let min = patterns.iter().map(|&(n, _, _)| n).min().unwrap();
78                total += min;
79
80                patterns.retain_mut(|(n, end, offset)| {
81                    if *n == min {
82                        *n += *offset;
83                    }
84                    *n <= *end
85                });
86            }
87
88            // Use the formula for the sum of the arithmetic sequence to compute the final sequence
89            if let Some((start, end, step)) = patterns.pop() {
90                let n = ((end - start) / step) + 1;
91                let last = start + (n - 1) * step;
92                total += n * (start + last) / 2;
93            }
94        }
95
96        total
97    }
98}
99
100examples!(Day02 -> (u64, u64) [
101    {
102        input: "11-22,95-115,998-1012,1188511880-1188511890,222220-222224,\
103            1698522-1698528,446443-446449,38593856-38593862,565653-565659,\
104            824824821-824824827,2121212118-2121212124",
105        part1: 1227775554,
106        part2: 4174379265
107    },
108]);
year2025/day02.rs

year2025/
day02.rs
