diff options
Diffstat (limited to 'src/day_09.rs')
-rw-r--r-- | src/day_09.rs | 182 |
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)?)) + } +} |