refactor(wip): clean up day_16 code (still brute)

1 files 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<Self::Answer1> {
-        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::<HashSet<_>>();
+
+        // 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::<String>())
+        //         .collect::<Vec<_>>()
+        //         .join("\n")
+        // );
+
+        Ok(score.len())
     }
 
     fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
         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::<Vec<_>>();
 
         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::<HashSet<_>>()
+                .len();
+            scores.push(score)
         }
 
         scores
@@ -45,39 +75,62 @@ impl Solution for Day16 {
 
 fn parse_grid(s: &str) -> anyhow::Result<Grid> {
     s.lines()
-        .enumerate()
-        .map(|(row, v)| {
-            v.chars()
-                .enumerate()
-                .map(|(col, value)| Node::try_from(((row, col), value)))
-                .try_collect::<Vec<_>>()
-        })
+        .map(|v| v.chars().map(Node::try_from).try_collect::<Vec<_>>())
         .try_collect::<Grid>()
 }
 
-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<Beam, HashSet<Beam>>,
+    mut visited: HashSet<Beam>,
+    beam: Beam,
+) -> HashSet<Beam> {
+    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<Beam> {
+    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<Edge>,
-}
-
-impl Node {
-    fn handle_beam(&mut self, edge: Edge) -> Vec<Beam> {
-        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<Edge> {
-        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<Self, Self::Error> {
-        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<char> for NodeType {
+impl TryFrom<char> for Node {
     type Error = anyhow::Error;
 
     fn try_from(value: char) -> Result<Self, Self::Error> {
         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}"),
         })
     }