refactor: move to single year per repoHEADmain

1 files changed, 182 insertions, 0 deletions

diff --git a/src/day_09.rs b/src/day_09.rs
new file mode 100644
index 0000000..d73a93d
--- /dev/null
+++ b/src/day_09.rs
@@ -0,0 +1,182 @@
+use std::{cmp::Ordering, collections::HashSet, fmt::Display, str::FromStr};
+
+use crate::{Problem, Solution};
+
+type Unit = isize;
+type Position = (Unit, Unit);
+
+enum Motion {
+    Up(Unit),
+    Down(Unit),
+    Left(Unit),
+    Right(Unit),
+}
+
+impl FromStr for Motion {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        match s.split_once(' ') {
+            Some(("U", n)) => Ok(Motion::Up(n.parse()?)),
+            Some(("D", n)) => Ok(Motion::Down(n.parse()?)),
+            Some(("L", n)) => Ok(Motion::Left(n.parse()?)),
+            Some(("R", n)) => Ok(Motion::Right(n.parse()?)),
+            _ => Err(anyhow::format_err!("Improper motion format: {}", s)),
+        }
+    }
+}
+
+impl Display for Motion {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Motion::Up(n) => write!(f, "U {}", n),
+            Motion::Down(n) => write!(f, "D {}", n),
+            Motion::Left(n) => write!(f, "L {}", n),
+            Motion::Right(n) => write!(f, "R {}", n),
+        }
+    }
+}
+
+#[derive(Clone)]
+enum List {
+    Cons(Position, Box<List>),
+    None,
+}
+
+impl List {
+    fn new() -> Self {
+        Self::None
+    }
+
+    fn prepend(self) -> List {
+        Self::Cons(Default::default(), Box::new(self))
+    }
+
+    fn update_from_motion(&mut self, motion: Motion) -> Vec<Position> {
+        let Self::Cons(position, next) = self else {
+            panic!("update_from_motion must be called on a head with at least one tail.");
+        };
+
+        let (dx, dy, count) = match motion {
+            Motion::Up(n) => (0, 1, n),
+            Motion::Down(n) => (0, -1, n),
+            Motion::Left(n) => (-1, 0, n),
+            Motion::Right(n) => (1, 0, n),
+        };
+
+        let mut visited = Vec::new();
+        for _ in 0..count {
+            position.0 += dx;
+            position.1 += dy;
+            visited.push(next.as_mut().update_from_position(position));
+        }
+
+        visited
+    }
+
+    fn update_from_position(&mut self, head: &Position) -> Position {
+        let Self::Cons(position, next) = self else {
+            return *head;
+        };
+
+        if position.0.abs_diff(head.0) > 1 || position.1.abs_diff(head.1) > 1 {
+            match position.0.cmp(&head.0) {
+                Ordering::Less => position.0 += 1,
+                Ordering::Equal => {}
+                Ordering::Greater => position.0 -= 1,
+            }
+
+            match position.1.cmp(&head.1) {
+                Ordering::Less => position.1 += 1,
+                Ordering::Equal => {}
+                Ordering::Greater => position.1 -= 1,
+            }
+        }
+
+        next.as_mut().update_from_position(position)
+    }
+}
+
+pub struct Day09;
+
+impl Problem for Day09 {
+    const DAY: u8 = 9;
+
+    const INPUT: &'static str = include_str!("../input/day_9.txt");
+}
+
+impl Solution for Day09 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> {
+        let mut head = List::new();
+        head = head.prepend();
+        head = head.prepend();
+
+        input
+            .lines()
+            .flat_map(Motion::from_str)
+            .flat_map(|motion| head.update_from_motion(motion))
+            .try_fold(HashSet::new(), |mut set, pos| {
+                set.insert(pos);
+                Ok(set)
+            })
+            .map(|s| s.len())
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> {
+        let mut head = List::new();
+        for _ in 0..10 {
+            head = head.prepend();
+        }
+
+        input
+            .lines()
+            .flat_map(Motion::from_str)
+            .flat_map(|motion| head.update_from_motion(motion))
+            .try_fold(HashSet::new(), |mut set, pos| {
+                set.insert(pos);
+                Ok(set)
+            })
+            .map(|s| s.len())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_part_1_example() -> Result<(), anyhow::Error> {
+        let test_input = indoc::indoc! {r#"
+            R 4
+            U 4
+            L 3
+            D 1
+            R 4
+            D 1
+            L 5
+            R 2
+        "#};
+
+        Ok(assert_eq!(13, Day09::part_1(test_input)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<(), anyhow::Error> {
+        let test_input = indoc::indoc! {r#"
+            R 5
+            U 8
+            L 8
+            D 3
+            R 17
+            D 10
+            L 25
+            U 20
+        "#};
+
+        Ok(assert_eq!(36, Day09::part_2(test_input)?))
+    }
+}