You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 117 lines 2.7 KiB Raw Permalink Blame History

 const INPUT: &str = include_str!("../../data/day9"); // store sums of elems in different row and colum, but just once // | 0 | 1 | 2 | 3 | ... // 0 | ----------------- // 1 | x | ------------- // 2 | x | x | --------- // 3 | x | x | x | ----- // 4 | x | x | x | x | - // 5 | x | x | x | x | x | - const fn row_start_offset(pos: usize) -> usize { (pos.overflowing_sub(1).0 * pos) / 2 } const BUFFER: usize = 25; const TRIANGLE_ELEMS: usize = row_start_offset(BUFFER); #[derive(Clone, Copy)] struct Combinations { buffer: [i64; BUFFER], combs: [i64; TRIANGLE_ELEMS], next_pos: usize, } impl std::fmt::Display for Combinations { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut pos = 0; for row in 0..BUFFER { write!(f, "Row {:02}:", row)?; for _ in 0..row { write!(f, " {:4}", self.combs[pos])?; pos += 1; } writeln!(f, "")?; } assert_eq!(pos, TRIANGLE_ELEMS); Ok(()) } } impl Combinations { fn new() -> Self { Self { buffer: [0i64; BUFFER], combs: [0i64; TRIANGLE_ELEMS], next_pos: 0, } } fn _update(&mut self, pos: usize, diff: i64) { let row_offset = row_start_offset(pos); for col in 0..pos { self.combs[row_offset + col] += diff; } let mut offset = row_offset + 2 * pos; for row in pos+1..BUFFER { self.combs[offset] += diff; offset += row; } } fn update(&mut self, elem: i64) { let pos = self.next_pos; let diff = elem - self.buffer[pos]; self.buffer[pos] = elem; self.next_pos = (pos + 1) % BUFFER; self._update(pos, diff); } fn contains(&self, elem: i64) -> bool { self.combs.iter().any(|v| *v == elem) } } fn main() { let input: Vec = INPUT.lines().map(|s| s.parse().unwrap()).collect(); let mut combs = Combinations::new(); for start_elem in &input[..BUFFER] { combs.update(*start_elem); } let mut target_sum = None; for elem in &input[BUFFER..] { if !combs.contains(*elem) { println!("Not a combination: {}", elem); target_sum = Some(*elem); break; } combs.update(*elem); } let target_sum = target_sum.unwrap(); let mut start = 0; let mut end = 2; let mut current_sum = input[0] + input[1]; loop { if current_sum == target_sum { if start + 2 > end { // less than two numbers... continue search, drop first number current_sum -= input[start]; start += 1; } else { let range = &input[start..end]; println!("Weakness: {}", *range.iter().min().unwrap() + *range.iter().max().unwrap()); break; } } else if current_sum < target_sum { // not enough: add next number current_sum += input[end]; end += 1; } else { // too much assert!(current_sum > target_sum); // drop first elem current_sum -= input[start]; start += 1; } } }