year2020/
day09.rs

1use utils::prelude::*;
2
3/// Finding the missing sum.
4#[derive(Clone, Debug)]
5pub struct Day09 {
6    numbers: Vec<u64>,
7    part1: u64,
8}
9
10impl Day09 {
11    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
12        let numbers = parser::u64().parse_lines(input)?;
13
14        let part1 = match input_type {
15            InputType::Example => Self::find_invalid::<5>(&numbers),
16            InputType::Real => Self::find_invalid::<25>(&numbers),
17        };
18        let Some(part1) = part1 else {
19            return Err(InputError::new(input, 0, "expected invalid number"));
20        };
21
22        Ok(Self { numbers, part1 })
23    }
24
25    fn find_invalid<const PREAMBLE: usize>(numbers: &[u64]) -> Option<u64> {
26        numbers
27            .array_windows::<PREAMBLE>()
28            .zip(&numbers[PREAMBLE..])
29            .find_map(|(window, &target)| {
30                for i in 0..PREAMBLE - 1 {
31                    for j in i + 1..PREAMBLE {
32                        if window[i] + window[j] == target {
33                            return None;
34                        }
35                    }
36                }
37                Some(target)
38            })
39    }
40
41    #[must_use]
42    pub fn part1(&self) -> u64 {
43        self.part1
44    }
45
46    #[must_use]
47    pub fn part2(&self) -> u64 {
48        let (mut start, mut end, mut total) = (0, 2, self.numbers[0] + self.numbers[1]);
49        while total != self.part1 || end - start < 2 {
50            if total < self.part1 {
51                assert!(end < self.numbers.len(), "no solution found");
52                total += self.numbers[end];
53                end += 1;
54            } else {
55                total -= self.numbers[start];
56                start += 1;
57            }
58        }
59
60        let (min, max) = self.numbers[start..end]
61            .iter()
62            .fold((u64::MAX, 0), |(min, max), &value| {
63                (min.min(value), max.max(value))
64            });
65        min + max
66    }
67}
68
69examples!(Day09 -> (u64, u64) [
70    {file: "day09_example0.txt", part1: 127, part2: 62},
71]);
year2020/day09.rs

year2020/
day09.rs
