73 lines
2.2 KiB
Rust
73 lines
2.2 KiB
Rust
use std::io::BufRead;
|
|
use std::collections::VecDeque;
|
|
|
|
|
|
type DataStream = Vec<usize>;
|
|
|
|
fn find_not_sum(data: &DataStream, preamble_size: usize) -> usize {
|
|
let mut preamble: VecDeque<_> = data.iter().take(preamble_size).map(usize::to_owned).collect();
|
|
|
|
data.iter().skip(preamble_size).find(|&&num| {
|
|
let half = num / 2;
|
|
let (lower, upper): (Vec<usize>, Vec<usize>) = preamble.iter().partition(|&&n| n <= half);
|
|
for first in lower.iter() {
|
|
for second in upper.iter() {
|
|
if first + second == num {
|
|
preamble.push_back(num);
|
|
preamble.pop_front();
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
true
|
|
}).unwrap().to_owned()
|
|
}
|
|
|
|
fn find_range_sum(data: &DataStream, needle: usize) -> Option<&[usize]> {
|
|
let len = data.len();
|
|
for i in 0..len {
|
|
for j in i..len {
|
|
let sum = data[i..j].iter().sum();
|
|
if needle == sum {
|
|
return Some(&data[i..j])
|
|
} else if sum > needle {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
None
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (input: F) {
|
|
let data: Vec<usize> = input.lines()
|
|
.filter_map(|line| line.unwrap().parse::<usize>().ok()).collect();
|
|
println!("{}", find_not_sum(&data, 25));
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (input: F) {
|
|
let data: Vec<usize> = input.lines()
|
|
.filter_map(|line| line.unwrap().parse::<usize>().ok()).collect();
|
|
let needle = find_not_sum(&data, 25);
|
|
let slice = find_range_sum(&data, needle).unwrap();
|
|
let checksum = slice.iter().min().unwrap() + slice.iter().max().unwrap();
|
|
println!("{}", checksum)
|
|
}
|
|
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
pub fn test_not_sum() {
|
|
let data = vec![35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299, 277, 309, 576];
|
|
assert_eq!(find_not_sum(&data, 5), 127);
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_find_range() {
|
|
let data = vec![35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299, 277, 309, 576];
|
|
let expected: &[usize] = &[15, 25, 47, 40];
|
|
assert_eq!(find_range_sum(&data, 127), Some(expected));
|
|
}
|
|
}
|