aoc2020/src/bin/day9.rs

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<i64> = 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;
		}
	}
}