diff options
Diffstat (limited to '2023/src/bin')
-rw-r--r-- | 2023/src/bin/day_9.rs | 78 |
1 files changed, 70 insertions, 8 deletions
diff --git a/2023/src/bin/day_9.rs b/2023/src/bin/day_9.rs index b3a610b..f0acc5e 100644 --- a/2023/src/bin/day_9.rs +++ b/2023/src/bin/day_9.rs @@ -1,19 +1,81 @@ -use nom::IResult; +use nom::{ + character::complete::{i32 as nom_i32, line_ending, space1}, + combinator::map, + multi::separated_list1, + IResult, +}; use std::fs; fn main() -> Result<(), Box<dyn std::error::Error>> { - let input = fs::read_to_string("inputs/day_2.txt")?; - let parsed = Example::parser(&input).unwrap().1; - dbg!(&parsed); + let input = fs::read_to_string("inputs/day_9.txt")?; + let parsed = DataSequences::parser(&input).unwrap().1; + dbg!(&parsed.sum_extrapolated_values()); + dbg!(&parsed.sum_extrapolated_front_values()); Ok(()) } #[derive(Debug)] -struct Example; +struct DataSequences(Vec<DataSequence>); -impl Example { - fn parser(_input: &str) -> IResult<&str, Self> { - todo!() +#[derive(Debug)] +struct DataSequence(Vec<i32>); + +impl DataSequences { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, DataSequence::parser), + DataSequences, + )(input) + } + + fn sum_extrapolated_values(&self) -> i32 { + self.0.iter().map(|d| d.extrapolate()).sum() + } + + fn sum_extrapolated_front_values(&self) -> i32 { + self.0.iter().map(|d| d.extrapolate_front()).sum() + } +} + +impl DataSequence { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(space1, nom_i32), DataSequence)(input) + } + + fn extrapolate(&self) -> i32 { + let mut differential_tree = vec![self.0.clone()]; + + while !differential_tree + .last() + .map_or(true, |l| l.iter().all(|i| *i == 0)) + { + let last_row = differential_tree.last().unwrap(); + let mut new_row = Vec::with_capacity(last_row.len() - 1); + for i in 0..last_row.len() - 1 { + new_row.push(last_row[i + 1] - last_row[i]); + } + differential_tree.push(new_row); + } + + differential_tree.last_mut().unwrap().push(0); + + while differential_tree.len() > 1 { + let bottom_row = differential_tree.pop().unwrap(); + + let new_last = differential_tree.last_mut().unwrap(); + new_last.push(new_last.last().unwrap() + bottom_row.last().unwrap()); + } + + differential_tree + .last() + .and_then(|l| l.last()) + .copied() + .unwrap() + } + + fn extrapolate_front(&self) -> i32 { + let backwards = DataSequence(self.0.iter().rev().copied().collect()); + backwards.extrapolate() } } |