From be2e579acc2012836dc4199ed8b4d4dc276b726e Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sun, 17 Dec 2023 01:11:02 -0600 Subject: refactor(wip): clean up day_16 code (still brute) --- src/day_16.rs | 198 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 99 insertions(+), 99 deletions(-) diff --git a/src/day_16.rs b/src/day_16.rs index f156ba8..133ff13 100644 --- a/src/day_16.rs +++ b/src/day_16.rs @@ -1,4 +1,4 @@ -use std::collections::VecDeque; +use std::collections::{/* HashMap, */ HashSet}; use crate::{Problem, Solution}; @@ -16,24 +16,54 @@ impl Solution for Day16 { type Answer2 = usize; fn part_1(input: &str) -> anyhow::Result { - let mut grid = parse_grid(input)?; - - solve_grid(&mut grid, Beam::default()); + let grid = parse_grid(input)?; - Ok(score_grid(&grid)) + // let mut cache = HashMap::default(); + let score = solve_grid( + &grid, + /* &mut cache, */ Default::default(), + Default::default(), + ); + let score = score.into_iter().map(|(_, p)| p).collect::>(); + + // let mut output = vec![vec!["[00]".to_string(); grid[0].len()]; grid.len()]; + // + // for ((e, (row, col)), score) in cache { + // output[col][row] = format!("[{:02}]", score.len()); + // // println!("{beam:?}: {score}"); + // } + // println!( + // "{}", + // output + // .into_iter() + // .map(|v| v.into_iter().collect::()) + // .collect::>() + // .join("\n") + // ); + + Ok(score.len()) } fn part_2(input: &str) -> anyhow::Result { let grid = parse_grid(input)?; + let edges = Edge::ALL + .into_iter() + .flat_map(|d| { + d.entry_points(&grid.clone()) + .into_iter() + .map(move |p| (d, p)) + }) + .collect::>(); let mut scores = Vec::new(); - for beam in Edge::ALL - .into_iter() - .flat_map(|d| d.entry_points(&grid).into_iter().map(move |p| (d, p))) - { - let mut g = grid.clone(); - solve_grid(&mut g, beam); - scores.push(score_grid(&g)); + // let mut cache = HashMap::new(); + for beam in edges { + let score = solve_grid(&grid, /* &mut cache, */ HashSet::new(), beam) + .into_iter() + .map(|(_, p)| p) + .collect::>() + .len(); + scores.push(score) } scores @@ -45,39 +75,62 @@ impl Solution for Day16 { fn parse_grid(s: &str) -> anyhow::Result { s.lines() - .enumerate() - .map(|(row, v)| { - v.chars() - .enumerate() - .map(|(col, value)| Node::try_from(((row, col), value))) - .try_collect::>() - }) + .map(|v| v.chars().map(Node::try_from).try_collect::>()) .try_collect::() } -fn solve_grid(grid: &mut Grid, start: Beam) { - let mut queue = VecDeque::from([start]); - - while let Some((direction, (row, col))) = queue.pop_front() { - if let Some(node) = grid.get_mut(row).and_then(|v| v.get_mut(col)) { - for (edge, (row, col)) in node.handle_beam(direction) { - if grid - .get_mut(row) - .and_then(|v| v.get_mut(col)) - .is_some_and(|n| !n.incoming.contains(&edge)) - { - queue.push_back((edge, (row, col))) - } - } - }; +fn solve_grid( + grid: &Grid, + // cache: &mut HashMap>, + mut visited: HashSet, + beam: Beam, +) -> HashSet { + if !(0..grid.len()).contains(&beam.1 .0) + || !(0..grid[0].len()).contains(&beam.1 .1) + || !visited.insert(beam) + { + visited + // } else if let Some(n) = cache.get(&beam) { + // println!("{beam:?} (cache hit)"); + // n.clone() + } else { + for v in handle_beam(grid, beam) { + visited = solve_grid(grid, /* cache, */ visited, v); + } + + // cache.insert(beam, visited.clone()); + + visited } } -fn score_grid(grid: &Grid) -> usize { - grid.iter() - .flat_map(|v| v.iter()) - .filter(|n| n.energized()) - .count() +fn handle_beam(grid: &Grid, (edge, (row, col)): Beam) -> Vec { + use Edge::*; + use Node::*; + + let edges = match (edge, grid[row][col]) { + (_, Empty) + | (North, VertSplit) + | (South, VertSplit) + | (East, HorzSplit) + | (West, HorzSplit) => vec![(edge)], + (North, BackMirror) | (South, FwrdMirror) => vec![(West)], + (North, FwrdMirror) | (South, BackMirror) => vec![(East)], + (North, HorzSplit) | (South, HorzSplit) => vec![(East), (West)], + (East, FwrdMirror) | (West, BackMirror) => vec![(North)], + (East, BackMirror) | (West, FwrdMirror) => vec![(South)], + (East, VertSplit) | (West, VertSplit) => vec![(North), (South)], + }; + + let mut beams = Vec::new(); + + for edge in edges { + if let Some(pos) = edge.with_position((row, col)) { + beams.push((edge, pos)); + } + } + + beams } type Position = (usize, usize); @@ -115,61 +168,8 @@ impl Edge { } } -#[derive(Debug, Default, Clone)] -struct Node { - position: Position, - node_type: NodeType, - incoming: Vec, -} - -impl Node { - fn handle_beam(&mut self, edge: Edge) -> Vec { - self.incoming.push(edge); - - self.get_outputs(edge) - .into_iter() - .flat_map(|d| d.with_position(self.position).map(|p| (d, p))) - .collect() - } - - fn get_outputs(&self, edge: Edge) -> Vec { - use Edge::*; - use NodeType::*; - - match (edge, self.node_type) { - (_, Empty) - | (North, VertSplit) - | (South, VertSplit) - | (East, HorzSplit) - | (West, HorzSplit) => vec![edge], - (North, BackMirror) | (South, FwrdMirror) => vec![West], - (North, FwrdMirror) | (South, BackMirror) => vec![East], - (North, HorzSplit) | (South, HorzSplit) => vec![East, West], - (East, FwrdMirror) | (West, BackMirror) => vec![North], - (East, BackMirror) | (West, FwrdMirror) => vec![South], - (East, VertSplit) | (West, VertSplit) => vec![North, South], - } - } - - fn energized(&self) -> bool { - !self.incoming.is_empty() - } -} - -impl TryFrom<(Position, char)> for Node { - type Error = anyhow::Error; - - fn try_from((position, value): (Position, char)) -> Result { - Ok(Self { - position, - node_type: value.try_into()?, - ..Default::default() - }) - } -} - #[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] -enum NodeType { +enum Node { #[default] Empty, HorzSplit, @@ -178,16 +178,16 @@ enum NodeType { BackMirror, } -impl TryFrom for NodeType { +impl TryFrom for Node { type Error = anyhow::Error; fn try_from(value: char) -> Result { Ok(match value { - '.' => NodeType::Empty, - '-' => NodeType::HorzSplit, - '|' => NodeType::VertSplit, - '/' => NodeType::FwrdMirror, - '\\' => NodeType::BackMirror, + '.' => Node::Empty, + '-' => Node::HorzSplit, + '|' => Node::VertSplit, + '/' => Node::FwrdMirror, + '\\' => Node::BackMirror, c => anyhow::bail!("Invalid char: {c}"), }) } -- cgit v1.2.3-70-g09d2