diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/day_10.rs | 353 | ||||
-rw-r--r-- | src/lib.rs | 9 | ||||
-rw-r--r-- | src/main.rs | 3 |
3 files changed, 363 insertions, 2 deletions
diff --git a/src/day_10.rs b/src/day_10.rs new file mode 100644 index 0000000..00d26d7 --- /dev/null +++ b/src/day_10.rs @@ -0,0 +1,353 @@ +use std::{ + cmp::Ordering, + collections::{BTreeMap, HashMap}, +}; + +use anyhow::Context; + +use crate::{Problem, Solution}; + +pub struct Day10; + +impl Problem for Day10 { + const DAY: u8 = 10; + + const INPUT: &'static str = include_str!("../input/day_10.txt"); +} + +impl Solution for Day10 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + let graph: Graph = input.parse()?; + + let mut path = Vec::new(); + let mut pos = graph.start; + let mut c = &'S'; + let mut next_edge = Edge::ALL.into_iter().find(|e| { + e.traverse(pos) + .and_then(|p| graph.inner.get(&p)) + .map(|c| e.valid_edge(c)) + .unwrap_or_default() + }); + + while let Some(edge) = next_edge { + path.push((edge, c)); + pos = edge.traverse(pos).context("Out-of-bounds move")?; + c = graph.inner.get(&pos).context("Failed to get postion")?; + next_edge = edge.exit(c); + if c == &'S' { + break; + } + } + + Ok(path.len() / 2) + } + + fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { + let mut graph: Graph = input.parse()?; + graph.solve()?; + + println!("{graph}"); + Ok(graph + .inner + .iter() + .filter(|(pos, _)| graph.is_included(pos)) + .count()) + + // 543 > + } +} + +type Position = (usize, usize); +type Path = BTreeMap<usize, BTreeMap<usize, char>>; + +#[derive(Default)] +struct Graph { + inner: HashMap<Position, char>, + start: Position, + path: Path, +} + +impl Graph { + fn solve(&mut self) -> anyhow::Result<()> { + let mut pos = self.start; + let mut next_edge = Edge::ALL.into_iter().find(|e| { + e.traverse(pos) + .and_then(|p| self.inner.get(&p)) + .map(|c| e.valid_edge(c)) + .unwrap_or_default() + }); + let mut c = &'S'; + let start_edge = next_edge.to_owned().unwrap(); + + while let Some(edge) = next_edge { + self.path + .entry(pos.0) + .and_modify(|v: &mut BTreeMap<usize, char>| { + v.insert(pos.1, *c); + }) + .or_insert(BTreeMap::from([(pos.1, *c)])); + pos = edge.traverse(pos).context("Out-of-bounds move")?; + c = self.inner.get(&pos).context("Failed to get postion")?; + if c == &'S' { + self.path + .entry(pos.0) + .and_modify(|v: &mut BTreeMap<usize, char>| { + assert_eq!( + Some('S'), + v.insert(pos.1, edge.as_char(&start_edge).unwrap()) + ); + }); + break; + } + next_edge = edge.exit(c); + } + Ok(()) + } + + fn is_included(&self, pos: &Position) -> bool { + let mut seg_start = ' '; + let mut left = 0; + let mut right = 0; + + let line = match self.path.get(&pos.0) { + Some(b) if b.get(&pos.1).is_none() => b, + _ => return false, + }; + + for (col, c) in line.iter() { + let count = match col.cmp(&pos.1) { + Ordering::Less => &mut left, + Ordering::Greater => &mut right, + Ordering::Equal if left % 2 != 0 => return true, + Ordering::Equal => continue, + }; + + match c { + '|' => *count += 1, + 'F' => seg_start = 'F', + 'L' => seg_start = 'L', + 'J' if seg_start == 'F' => *count += 1, + '7' if seg_start == 'L' => *count += 1, + 'J' if seg_start == 'L' => seg_start = ' ', + '7' if seg_start == 'F' => seg_start = ' ', + _ => {} + } + } + + left % 2 != 0 || right % 2 != 0 + } +} + +impl std::str::FromStr for Graph { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + let inner = s + .trim() + .lines() + .enumerate() + .flat_map(|(row, line)| { + line.trim() + .chars() + .enumerate() + .map(move |(col, char)| ((row, col), char)) + }) + .collect::<HashMap<_, _>>(); + + let start = inner + .iter() + .find_map(|(pos, c)| (c == &'S').then_some(pos)) + .context("Failed to find start")?; + + Ok(Graph { + start: *start, + inner, + ..Default::default() + }) + } +} + +impl std::fmt::Debug for Graph { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let (height, width) = self.inner.keys().max().unwrap(); + for row in 0..height + 1 { + let Some(btree) = self.path.get(&row) else { + writeln!(f)?; + continue; + }; + let mut output = String::new(); + for col in 0..width + 1 { + match btree.get(&col) { + Some(c) => output.push(*c), + None if self.is_included(&(row, col)) => output.push('I'), + None => output.push('O'), + }; + } + writeln!(f, "{output}")? + } + Ok(()) + } +} + +impl std::fmt::Display for Graph { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let (height, width) = self.inner.keys().max().unwrap(); + for row in 0..height + 1 { + let Some(btree) = self.path.get(&row) else { + writeln!(f)?; + continue; + }; + let mut output = String::new(); + for col in 0..width + 1 { + match btree.get(&col) { + Some('|') => output.push('│'), + Some('-') => output.push('─'), + Some('L') => output.push('└'), + Some('J') => output.push('┘'), + Some('7') => output.push('┐'), + Some('F') => output.push('┌'), + Some(c) => output.push(*c), + None if self.is_included(&(row, col)) => output.push('I'), + None => output.push('O'), + }; + } + writeln!(f, "{output}")? + } + Ok(()) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum Edge { + Up, + Down, + Left, + Right, +} + +impl Edge { + const ALL: [Edge; 4] = [Self::Up, Self::Down, Self::Left, Self::Right]; + + fn traverse(&self, (row, col): Position) -> Option<Position> { + Some(match self { + Edge::Up => (row.checked_sub(1)?, col), + Edge::Down => (row.checked_add(1)?, col), + Edge::Left => (row, col.checked_sub(1)?), + Edge::Right => (row, col.checked_add(1)?), + }) + } + + fn valid_edge(&self, &c: &char) -> bool { + match self { + Edge::Up => c == '|' || c == '7' || c == 'F', + Edge::Down => c == '|' || c == 'J' || c == 'L', + Edge::Left => c == '-' || c == 'F' || c == 'L', + Edge::Right => c == '-' || c == 'J' || c == '7', + } + } + + fn exit(&self, &c: &char) -> Option<Self> { + Some(match (self, c) { + (Edge::Up, '|') => Edge::Up, + (Edge::Up, '7') => Edge::Left, + (Edge::Up, 'F') => Edge::Right, + (Edge::Down, '|') => Edge::Down, + (Edge::Down, 'J') => Edge::Left, + (Edge::Down, 'L') => Edge::Right, + (Edge::Left, '-') => Edge::Left, + (Edge::Left, 'F') => Edge::Down, + (Edge::Left, 'L') => Edge::Up, + (Edge::Right, '-') => Edge::Right, + (Edge::Right, 'J') => Edge::Up, + (Edge::Right, '7') => Edge::Down, + _ => None?, + }) + } + + fn as_char(&self, other: &Edge) -> Option<char> { + Some(match (self, other) { + (Edge::Up, Edge::Down) | (Edge::Down, Edge::Up) => '|', + (Edge::Up, Edge::Left) | (Edge::Left, Edge::Up) => 'J', + (Edge::Up, Edge::Right) | (Edge::Right, Edge::Up) => 'L', + (Edge::Down, Edge::Left) | (Edge::Left, Edge::Down) => '7', + (Edge::Down, Edge::Right) | (Edge::Right, Edge::Down) => 'F', + (Edge::Left, Edge::Right) | (Edge::Right, Edge::Left) => '-', + _ => None?, + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + const INPUT: &str = indoc::indoc! {" + ..F7. + .FJ|. + SJ.L7 + |F--J + LJ... + "}; + + Ok(assert_eq!(8, Day10::part_1(INPUT)?)) + } + + #[test] + fn test_part_2_1() -> anyhow::Result<()> { + const INPUT: &str = indoc::indoc! {" + FF7FSF7F7F7F7F7F---7 + L|LJ||||||||||||F--J + FL-7LJLJ||||||LJL-77 + F--JF--7||LJLJ7F7FJ- + L---JF-JLJ.||-FJLJJ7 + |F|F-JF---7F7-L7L|7| + |FFJF7L7F-JF7|JL---7 + 7-L-JL7||F7|L7F-7F7| + L.L7LFJ|||||FJL7||LJ + L7JLJL-JLJLJL--JLJ.L + "}; + + Ok(assert_eq!(10, Day10::part_2(INPUT)?)) + } + + #[test] + fn test_part_2_2() -> anyhow::Result<()> { + const INPUT: &str = indoc::indoc! {" + .F----7F7F7F7F-7.... + .|F--7||||||||FJ.... + .||.FJ||||||||L7.... + FJL7L7LJLJ||LJ.L-7.. + L--J.L7...LJS7F-7L7. + ....F-J..F7FJ|L7L7L7 + ....L7.F7||L7|.L7L7| + .....|FJLJ|FJ|F7|.LJ + ....FJL-7.||.||||... + ....L---J.LJ.LJLJ... + "}; + + Ok(assert_eq!(8, Day10::part_2(INPUT)?)) + } + + #[test] + fn test_part_2_3() -> anyhow::Result<()> { + const INPUT: &str = indoc::indoc! {" + ........... + .S-------7. + .|F-----7|. + .||.....||. + .||.....||. + .|L-7.F-J|. + .|..|.|..|. + .L--J.L--J. + ........... + "}; + + Ok(assert_eq!(4, Day10::part_2(INPUT)?)) + } +} @@ -1,4 +1,10 @@ -#![feature(iterator_try_collect, iter_array_chunks, array_windows, let_chains)] +#![feature( + iterator_try_collect, + iter_array_chunks, + array_windows, + array_chunks, + let_chains +)] pub mod day_01; pub mod day_02; @@ -9,6 +15,7 @@ pub mod day_06; pub mod day_07; pub mod day_08; pub mod day_09; +pub mod day_10; pub trait Problem { const DAY: u8; diff --git a/src/main.rs b/src/main.rs index fa19b95..ad87f73 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,6 +1,6 @@ use aoc_2023::{ day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, day_05::Day05, day_06::Day06, - day_07::Day07, day_08::Day08, day_09::Day09, Solution, + day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, Solution, }; fn main() -> anyhow::Result<()> { @@ -13,6 +13,7 @@ fn main() -> anyhow::Result<()> { Day07::solve()?; Day08::solve()?; Day09::solve()?; + Day10::solve()?; Ok(()) } |