aoc/year2020/
day09.rs

1//! # Encoding Error
2//!
3//! Part one is solved with a brute force search over every possible pair in the preamble, using a
4//! sliding window to advance to each number. To allow testing with the sample data that uses a
5//! preamble of 5 but preserve compile-time optimization, the `decrypt` method is
6//! [const generic](https://doc.rust-lang.org/reference/items/generics.html#const-generics)
7//! in the size of the preamble.
8//!
9//! Part two uses a sliding search over a variable size window of the input.
10use crate::util::parse::*;
11
12type Input = (u64, u64);
13
14pub fn parse(input: &str) -> Input {
15    decrypt::<25>(input)
16}
17
18pub fn part1(input: &Input) -> u64 {
19    input.0
20}
21
22pub fn part2(input: &Input) -> u64 {
23    input.1
24}
25
26pub fn decrypt<const N: usize>(input: &str) -> Input {
27    let numbers: Vec<_> = input.iter_unsigned().collect();
28
29    let invalid = numbers
30        .windows(N + 1)
31        .find(|w| (0..N - 1).all(|i| (i + 1..N).all(|j| w[i] + w[j] != w[N])))
32        .map(|w| w[N])
33        .unwrap();
34
35    let mut start = 0;
36    let mut end = 2;
37    let mut sum = numbers[0] + numbers[1];
38
39    while sum != invalid {
40        if sum < invalid {
41            sum += numbers[end];
42            end += 1;
43        } else {
44            sum -= numbers[start];
45            start += 1;
46        }
47    }
48
49    let slice = &numbers[start..end];
50    (invalid, slice.iter().min().unwrap() + slice.iter().max().unwrap())
51}
aoc/year2020/day09.rs

aoc/year2020/
day09.rs
