diff options
Diffstat (limited to '2023/src/bin/day_23.rs')
| -rw-r--r-- | 2023/src/bin/day_23.rs | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/2023/src/bin/day_23.rs b/2023/src/bin/day_23.rs new file mode 100644 index 0000000..40d0b70 --- /dev/null +++ b/2023/src/bin/day_23.rs @@ -0,0 +1,218 @@ +use nalgebra::Point2; +use nom::{ + branch::alt, + character::complete::{char, line_ending}, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::{ + collections::{HashMap, HashSet}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_23.txt")?; + let forest_map = ForestMap::parser(&input).unwrap().1; + let slippery_forked_forest_map = forest_map.build_forked_map(true); + let dry_forked_forest_map = forest_map.build_forked_map(false); + + dbg!(&slippery_forked_forest_map.longest_end_path_length()); + dbg!(&dry_forked_forest_map.longest_end_path_length()); + + Ok(()) +} + +#[derive(Debug)] +struct ForestMap(Vec<Vec<ForestTile>>); + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum ForestTile { + Wall, + Open, + SlopeUp, + SlopeDown, + SlopeLeft, + SlopeRight, +} + +#[derive(Debug, Clone)] +struct DecisionNode { + explored: HashSet<Point2<usize>>, + current: Point2<usize>, +} + +#[derive(Debug)] +struct ForkedForestMap { + start: Point2<usize>, + end: Point2<usize>, + connections: HashMap<Point2<usize>, Vec<ForkConnection>>, +} + +#[derive(Debug)] +struct ForkConnection { + to: Point2<usize>, + distance: usize, +} + +#[derive(Debug, Clone)] +struct ForkedDecisionNode { + explored_forks: HashSet<Point2<usize>>, + current: Point2<usize>, + current_len: usize, +} + +impl ForestMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, many1(ForestTile::parser)), + ForestMap, + )(input) + } + + fn adjacent( + &self, + p: &Point2<usize>, + not_these: &HashSet<Point2<usize>>, + slippery: bool, + ) -> Vec<Point2<usize>> { + let mut adjacent = Vec::with_capacity(4); + let tile = self.at(p); + + if p.x > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeLeft)) { + adjacent.push(Point2::new(p.x - 1, p.y)); + } + if p.y > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeUp)) { + adjacent.push(Point2::new(p.x, p.y - 1)); + } + if p.x < self.0[p.y].len() - 1 + && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeRight)) + { + adjacent.push(Point2::new(p.x + 1, p.y)); + } + if p.y < self.0.len() - 1 + && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeDown)) + { + adjacent.push(Point2::new(p.x, p.y + 1)); + } + + adjacent.retain(|adj_p| self.at(adj_p) != ForestTile::Wall && !not_these.contains(adj_p)); + adjacent + } + + fn at(&self, p: &Point2<usize>) -> ForestTile { + self.0[p.y][p.x] + } + + fn build_forked_map(&self, slippery: bool) -> ForkedForestMap { + let start = Point2::new(1, 0); + let end = Point2::new(self.0[0].len() - 2, self.0.len() - 1); + let mut forks = Vec::new(); + forks.push(start); + forks.push(end); + + for y in 1..self.0.len() - 1 { + for x in 1..self.0[y].len() - 1 { + let p = Point2::new(x, y); + if self.at(&p) != ForestTile::Wall { + let adjacent_count = self.adjacent(&p, &HashSet::new(), false).len(); + if adjacent_count > 2 { + forks.push(p); + } + } + } + } + + let mut connections = HashMap::new(); + + for start_point in &forks { + let mut active_nodes = vec![DecisionNode { + explored: HashSet::new(), + current: start_point.clone(), + }]; + active_nodes[0].explored.insert(start_point.clone()); + + let mut fork_connections = Vec::new(); + + while let Some(node) = active_nodes.pop() { + for adjacent in self.adjacent(&node.current, &node.explored, slippery) { + let mut new_node = node.clone(); + new_node.explored.insert(adjacent); + new_node.current = adjacent; + + if forks.contains(&new_node.current) { + fork_connections.push(ForkConnection { + to: new_node.current, + distance: new_node.path_length(), + }); + } else { + active_nodes.push(new_node); + } + } + } + + connections.insert(start_point.clone(), fork_connections); + } + + ForkedForestMap { + start, + end, + connections, + } + } +} + +impl ForestTile { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(ForestTile::Wall, char('#')), + value(ForestTile::Open, char('.')), + value(ForestTile::SlopeUp, char('^')), + value(ForestTile::SlopeDown, char('v')), + value(ForestTile::SlopeLeft, char('<')), + value(ForestTile::SlopeRight, char('>')), + ))(input) + } +} + +impl DecisionNode { + fn path_length(&self) -> usize { + self.explored.len() - 1 + } +} + +impl ForkedForestMap { + fn longest_end_path_length(&self) -> usize { + let mut active_nodes = vec![ForkedDecisionNode { + explored_forks: HashSet::new(), + current: self.start, + current_len: 0, + }]; + active_nodes[0].explored_forks.insert(self.start); + let mut longest_end_path_length: Option<usize> = None; + + while let Some(node) = active_nodes.pop() { + for adjacent in self.connections.get(&node.current).unwrap() { + if !node.explored_forks.contains(&adjacent.to) { + let mut new_node = node.clone(); + new_node.explored_forks.insert(adjacent.to); + new_node.current = adjacent.to; + new_node.current_len += adjacent.distance; + + if new_node.current == self.end { + longest_end_path_length = + if let Some(current_longest) = longest_end_path_length { + Some(current_longest.max(new_node.current_len)) + } else { + Some(new_node.current_len) + }; + } else { + active_nodes.push(new_node); + } + } + } + } + + longest_end_path_length.unwrap() + } +} |