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

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