isaaccorbrey.com
Advent of Code for 2025!
1use std::ops::RangeInclusive;
2
3fn main() {
4 aoc2025::run(
5 "Day 2: Gift Shop",
6 "inputs/day_02.txt",
7 parse_input,
8 part_1,
9 part_2,
10 )
11 .unwrap();
12}
13
14fn parse_chunk(chunk: &str) -> Option<RangeInclusive<u64>> {
15 let chunk = chunk.trim();
16 let (start, end) = chunk.find('-').map(|i| chunk.split_at(i))?;
17 let start = start.parse::<u64>().ok();
18 let end = end.trim_start_matches('-').parse::<u64>().ok();
19 start.zip(end).map(|(start, end)| start..=end)
20}
21
22fn parse_input(input: &str) -> Vec<RangeInclusive<u64>> {
23 (input.split(','))
24 .filter_map(|ch| parse_chunk(ch))
25 .collect::<Vec<_>>()
26}
27
28fn repeats_once(value: u64) -> bool {
29 let value = value.to_string();
30
31 if value.len() % 2 != 0 {
32 return false;
33 }
34
35 let (start, end) = value.split_at(value.len() / 2);
36 start == end
37}
38
39fn factors(x: usize) -> Vec<usize> {
40 (1..=x)
41 .filter_map(|i| if x % i == 0 { Some(i) } else { None })
42 .collect::<Vec<_>>()
43}
44
45fn repeats_multiple_times(value: u64) -> bool {
46 let value = value.to_string();
47 let value = value.as_bytes();
48
49 if value.len() <= 1 {
50 return false;
51 }
52
53 for l in factors(value.len()) {
54 if l == value.len() {
55 continue;
56 }
57
58 let first = &value[0..l];
59 if value.chunks(l).all(|c| c == first) {
60 return true;
61 }
62 }
63
64 false
65}
66
67fn part_1(ranges: Vec<RangeInclusive<u64>>) -> u64 {
68 (ranges.into_iter())
69 .map(|range| range.filter(|x| repeats_once(*x)).sum::<u64>())
70 .sum()
71}
72
73fn part_2(ranges: Vec<RangeInclusive<u64>>) -> u64 {
74 (ranges.into_iter())
75 .map(|range| range.filter(|x| repeats_multiple_times(*x)).sum::<u64>())
76 .sum()
77}
78
79#[cfg(test)]
80mod tests {
81 use std::ops::RangeInclusive;
82
83 use super::*;
84 use proptest::prelude::*;
85
86 prop_compose! {
87 fn chunk()(
88 x in any::<u64>(),
89 y in any::<u64>(),
90 w0 in "\\s*",
91 w1 in "\\s*"
92 ) -> (RangeInclusive<u64>, String) {
93 let start = x.min(y);
94 let end = x.max(y);
95
96 (start..=end, format!("{}{}-{}{}", w0, start, end, w1))
97 }
98 }
99
100 prop_compose! {
101 fn input()(v in prop::collection::vec(chunk(), 1..100)) -> (Vec<RangeInclusive<u64>>, String) {
102 let (ranges, chunks): (Vec<_>, Vec<_>) = v.into_iter().unzip();
103 (ranges, chunks.join(","))
104 }
105 }
106
107 mod parse_chunk {
108 use super::*;
109
110 proptest! {
111 #[test]
112 fn doesnt_crash(s in "\\PC+") {
113 parse_chunk(s.as_str());
114 }
115
116 #[test]
117 fn parses_chunks(ch in chunk()) {
118 let (expected, input) = ch;
119 prop_assert_eq!(Some(expected), parse_chunk(&input));
120 }
121 }
122 }
123
124 mod parse_input {
125 use super::*;
126
127 proptest! {
128 #[test]
129 fn doesnt_crash(s in "\\PC+") {
130 parse_input(s.as_str());
131 }
132
133 #[test]
134 fn ignores_empty_chunks(s in ",+") {
135 prop_assert_eq!(Vec::<RangeInclusive<u64>>::new(), parse_input(&s));
136 }
137
138 #[test]
139 fn parses_input_correctly(s in input()) {
140 let (ranges, input) = s;
141 prop_assert_eq!(ranges, parse_input(&input));
142 }
143 }
144 }
145
146 mod repeats_once {
147 use super::*;
148
149 fn odd_length() -> impl Strategy<Value = u64> {
150 any::<u64>().prop_filter("must be odd length", |x| x.to_string().len() % 2 != 0)
151 }
152
153 fn even_length_nonrepeating() -> impl Strategy<Value = u64> {
154 any::<u64>()
155 .prop_filter("must be even length", |x| x.to_string().len() % 2 == 0)
156 .prop_filter("must be nonrepeating", |x| {
157 let x = x.to_string();
158 let (a, b) = x.split_at(x.len() / 2);
159 a != b
160 })
161 }
162
163 const MAX_SUBNUMBER: u64 = 1_844_674_407;
164
165 prop_compose! {
166 fn even_length_repeating()(x in 0_u64..MAX_SUBNUMBER) -> u64 {
167 format!("{}{}", x, x).parse::<u64>().unwrap()
168 }
169 }
170
171 proptest! {
172 #[test]
173 fn doesnt_crash(x in any::<u64>()) {
174 repeats_once(x);
175 }
176
177 #[test]
178 fn odd_lengths_cant_repeat(x in odd_length()) {
179 prop_assert!(!repeats_once(x));
180 }
181
182 #[test]
183 fn detects_nonrepeating(x in even_length_nonrepeating()) {
184 prop_assert!(!repeats_once(x));
185 }
186
187 #[test]
188 fn detects_repeating_once(x in even_length_repeating()) {
189 prop_assert!(repeats_once(x));
190 }
191 }
192 }
193
194 mod factors {
195 use super::*;
196
197 // We can test smaller ranges here because `factors` will only be used
198 // on the length of the string representation of a number, not the
199 // number itself.
200
201 proptest! {
202 #[test]
203 fn doesnt_crash(x in 1_usize..=20) {
204 factors(x);
205 }
206
207 #[test]
208 fn always_includes_one(x in 1_usize..=20) {
209 prop_assert!(factors(x).contains(&1))
210 }
211
212 #[test]
213 fn always_includes_input(x in 1_usize..=20) {
214 prop_assert!(factors(x).contains(&x))
215 }
216
217 #[test]
218 fn factors_correctly(x in 1_usize..=10, y in 1_usize..=10) {
219 let f = factors(x * y);
220 prop_assert!(f.contains(&x));
221 prop_assert!(f.contains(&y));
222 }
223 }
224 }
225
226 mod repeats_multiple_times {
227 use proptest::string;
228
229 use super::*;
230
231 // Any string that repeats X times must be a multiple of that length
232 // Therefore, find the factors of len(s) and get the substring chunks
233 // If all are equal for any factor, return true
234
235 const PRIME_LENGTHS: &[usize] = &[2, 3, 5, 7, 11, 13, 17, 19];
236
237 // Doesn't cover all nonrepeating numbers but that's a lot of work and
238 // this should be good enough
239 fn nonrepeating() -> impl Strategy<Value = u64> {
240 prop::sample::select(PRIME_LENGTHS.to_vec()).prop_flat_map(|len| {
241 let pattern = format!("[1-9][0-9]{{{}}}", len - 1);
242 string::string_regex(pattern.as_str())
243 .unwrap()
244 .prop_filter_map("not all digits identical", move |s| {
245 let mut chars = s.chars();
246 let first = chars.next().unwrap();
247 if chars.all(|c| c == first) {
248 return None;
249 }
250
251 s.parse::<u64>().ok()
252 })
253 })
254 }
255
256 fn repeating() -> impl Strategy<Value = u64> {
257 (2_usize..10, 1_usize..10)
258 .prop_filter("total length must fit within u64", |(x, y)| x * y < 20)
259 .prop_flat_map(|(n, length)| {
260 let pattern = match length {
261 1 => "[1-9]".to_string(),
262 l => format!("[1-9][0-9]{{{}}}", l - 1),
263 };
264
265 (string::string_regex(&pattern).unwrap())
266 .prop_filter_map("parseable u64", move |chunk| {
267 chunk.repeat(n).parse::<u64>().ok()
268 })
269 })
270 }
271
272 proptest! {
273 #[test]
274 fn doesnt_crash(x in any::<u64>()) {
275 repeats_multiple_times(x);
276 }
277
278 #[test]
279 fn single_digits_cant_repeat(x in 0_u64..10) {
280 prop_assert!(!repeats_multiple_times(x));
281 }
282
283 #[test]
284 fn detects_nonrepeating_numbers(x in nonrepeating()) {
285 prop_assert!(!repeats_multiple_times(x));
286 }
287
288 #[test]
289 fn detects_repeating_numbers(x in repeating()) {
290 prop_assert!(repeats_multiple_times(x))
291 }
292 }
293 }
294
295 const EXAMPLE_INPUT: &str = "11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124";
296
297 mod part_1 {
298 use super::*;
299
300 const EXAMPLE_ANSWER: u64 = 1227775554;
301
302 #[test]
303 fn solves_example() {
304 let input = parse_input(EXAMPLE_INPUT);
305 assert_eq!(EXAMPLE_ANSWER, part_1(input));
306 }
307 }
308
309 mod part_2 {
310 use super::*;
311
312 const EXAMPLE_ANSWER: u64 = 4174379265;
313
314 #[test]
315 fn solves_example() {
316 let input = parse_input(EXAMPLE_INPUT);
317 assert_eq!(EXAMPLE_ANSWER, part_2(input));
318 }
319 }
320}