1 files changed, 81 insertions, 0 deletions
diff --git a/2023/src/bin/day_9.rs b/2023/src/bin/day_9.rs
new file mode 100644
index 0000000..f0acc5e
--- /dev/null
+++ b/2023/src/bin/day_9.rs
@@ -0,0 +1,81 @@
+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_9.txt")?;
+    let parsed = DataSequences::parser(&input).unwrap().1;
+    dbg!(&parsed.sum_extrapolated_values());
+    dbg!(&parsed.sum_extrapolated_front_values());
+
+    Ok(())
+}
+
+#[derive(Debug)]
+struct DataSequences(Vec<DataSequence>);
+
+#[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()
+    }
+}