From 610c00174ab6e338ddc11d742e9267f3f46f6058 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sat, 23 Dec 2023 15:31:16 +0200 Subject: Day 23 part 2 --- 2023/src/bin/day_23.rs | 179 +++++++++++++++++++++++++++++++++---------------- 1 file changed, 122 insertions(+), 57 deletions(-) (limited to '2023/src/bin/day_23.rs') diff --git a/2023/src/bin/day_23.rs b/2023/src/bin/day_23.rs index 801b0b4..40d0b70 100644 --- a/2023/src/bin/day_23.rs +++ b/2023/src/bin/day_23.rs @@ -6,13 +6,19 @@ use nom::{ multi::{many1, separated_list1}, IResult, }; -use std::{collections::HashSet, fs}; +use std::{ + collections::{HashMap, HashSet}, + fs, +}; fn main() -> Result<(), Box> { let input = fs::read_to_string("inputs/day_23.txt")?; let forest_map = ForestMap::parser(&input).unwrap().1; - dbg!(forest_map.longest_end_path_length(true)); - dbg!(forest_map.longest_end_path_length(false)); + 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(()) } @@ -36,6 +42,26 @@ struct DecisionNode { current: Point2, } +#[derive(Debug)] +struct ForkedForestMap { + start: Point2, + end: Point2, + connections: HashMap, Vec>, +} + +#[derive(Debug)] +struct ForkConnection { + to: Point2, + distance: usize, +} + +#[derive(Debug, Clone)] +struct ForkedDecisionNode { + explored_forks: HashSet>, + current: Point2, + current_len: usize, +} + impl ForestMap { fn parser(input: &str) -> IResult<&str, Self> { map( @@ -44,60 +70,6 @@ impl ForestMap { )(input) } - fn longest_end_path_length(&self, slippery: bool) -> usize { - let start_point = Point2::new(1, 0); - let end_point = Point2::new(self.0[0].len() - 2, self.0.len() - 1); - - let mut active_nodes = vec![DecisionNode { - explored: HashSet::new(), - current: start_point, - }]; - active_nodes[0].explored.insert(start_point); - let mut longest_end_path_length: Option = None; - - while let Some(mut node) = active_nodes.pop() { - let mut all_adjacent = self.adjacent(&node.current, &node.explored, slippery); - while all_adjacent.len() == 1 { - let adjacent = all_adjacent[0]; - node.explored.insert(adjacent); - node.current = adjacent; - - if node.current == end_point { - let end_path_length = node.path_length(); - longest_end_path_length = if let Some(current_longest) = longest_end_path_length - { - Some(current_longest.max(end_path_length)) - } else { - Some(end_path_length) - }; - all_adjacent = vec![]; - } else { - all_adjacent = self.adjacent(&node.current, &node.explored, slippery); - } - } - - for adjacent in all_adjacent { - let mut new_node = node.clone(); - new_node.explored.insert(adjacent); - new_node.current = adjacent; - - if new_node.current == end_point { - let end_path_length = new_node.path_length(); - longest_end_path_length = if let Some(current_longest) = longest_end_path_length - { - Some(current_longest.max(end_path_length)) - } else { - Some(end_path_length) - }; - } else { - active_nodes.push(new_node); - } - } - } - - longest_end_path_length.unwrap() - } - fn adjacent( &self, p: &Point2, @@ -131,6 +103,63 @@ impl ForestMap { fn at(&self, p: &Point2) -> 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 { @@ -151,3 +180,39 @@ impl DecisionNode { 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 = 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() + } +} -- cgit v1.2.3