feat: impl day 16 (brute force)

4 files changed, 337 insertions, 2 deletions

diff --git a/input/day_16.txt b/input/day_16.txt
new file mode 100644
index 0000000..c3806d1
--- /dev/null
+++ b/input/day_16.txt
@@ -0,0 +1,110 @@
+\...|....||/............\.......-.......................\............./..........--......................./...
+.......-..........................................-..-......../....../........................\...............
+............/....\................-................-....................|..................\..../.............
+.............|.\.................\.................|..................|..-........-...................-\......
+..|...................|.....|......................./|...../......-................/.-..|.........\...........
+.|......-..........\....../....\............\........../..\....|......................................-.......
+....\....|/......../............\..............................-....../\|..-..\../.........\..\|..............
+.........-..........-.........../...................-...........|....|\.......................................
+.....|........................-......./...\../......\./.|................\......|.-...-........|.|/\..........
+././............|............|...........\.....\..../...|....|...-.....|..............|................-......
+................/../....\..........\......-....................-../............../........../-....\...........
+......|........-................/........-......./........|......-\.............../........../.....|..........
+-\.\......|...........//...\-.../..\..-..\.............................../............../.\-.-.......\........
+.\..-...|./......./..............................\.................-....\../.................\..../...........
+-....../......|....-...||...|.................../...-........-................|.......-/......\\...|..........
+...../.........\..............\.................\..|....../....\....../.-\.....................|..\...........
+\|..................\................-........./.......|...........\...../.................../................
+..................../......\..........\..-...............\........-......................................|-...
+................-................../.................................................-..................\-....
+..\...................|....../........................./....-..........|.....................-................
+..............-...................................\...............|./...-../.-|........||.....................
+...........................././...|..........\............|...-....-..../.\\.......\...-.........\......../...
+....\........................\..........-............\/...........|..-..\.....................................
+..../.........../-\..\.........................|.........-........................|...........................
+...|./..\...............................\....................../..............................................
+..-.................\....|......-...-.........\-|..........\.-......|.....\.\....|......................|.....
+......-.........\.....|..............-......................\.\...|\.....-..-..../............................
+.....-..././......\|............................\.-.....................-.....................................
+/-....................................-....................../.................................../.........\\.
+.........|./...................................-..........|..\...\........../\.....\.....|...\.....|../..|....
+............|.....................-.....................--.|-............................\|......../.|.....-..
+-......\.........................\........|.\......../....||..||....................-........|.-.-............
+................././/|............../..\.........-|.....-...|....|.......................-.......|............
+|......|....../..............-............/........................-........\....\....|...../..............-..
+.............//..../.......-........\.............|...../............................/........\......|........
+...................-......-..........\..............\..............................\...................\......
+...............\./......|.-...................-.|.........\.............../................/..................
+.\..........-........|....................-..................||...........|...................................
+....................\......../.........|............-...........-.........\..............-.-......../...\.....
+........-.........|............\/.................-./.............-.......\...................-...............
+....................-...............-./.................|............./.......\.............\........./\......
+......\...............|........-/..................\.............../|.......\.|..............--..|.....|......
+......\...\.....././.........\||.............................|....\.\.............../....-..|/........-.......
+....../...../.................\...........|./.......|...\./....-...\........../.\......./..........-........\.
+..................\..../....|................................................................|.....|....-.....
+|..............................\......-................/|./-......./...........\........-.................|...
+.\..|\....-..............-..|...........\........|....|..|........./.................................../......
+...../...|..||.....\.--..........-....../............\..\.....|./..\....................\|......./............
+.......\...|......-.......|..../......\..\/.|./.\..........|....|..............-.......................|...../
+..............-...........\..\../...................\.........|.|....../..-/..............-...................
+.......-.......\..../................................................|...../....|................|...-........
+......................./........................|..\...|...-..-.........../....../.......-....|........../....
+.......|..................................-.....\-./.\.........................\..../....-...|................
+........../.../........./...........-.......|......./.-.........................\...\-.....................-..
+..........\.\.............|........\..|........./.................../...........\.................\.../.......
+....................-...|......|................../--.-.............-......................./.................
+......./.........|......./../.....................-....//..|..............-..|.............\............\.....
+...|...........-........................../.-..\............................\...|................\.//.......\.
+../.....\..\.......-.............../.....|../.......................\-.................../.......-|/..........
+......\.....................|.....\.............-.....\........../..........\.....-............|....\...-.....
+...../.....................-|...\..-......./.............../.|..../................\..-...........\........./.
+......|..\...........................\.........../.-............|....................-....|-.......-....\.....
+........................................./.......|......-../../.............../....................|..........
+........\.....|....../.......\.........../....../....-.........-.............||\...................-...|......
+...........|.................\..\.............|...............\.....|..............................|..........
+............|....../\....\..../.................\.-./......../\|../|..........................................
+........................................................-|....................\....|.............|..-.........
+/.|.............\\......\......./\.....................|.../.....................-...-.........../.-.....\....
+.........................\/....-...\......./......-...........................--..|........\-..../............
+.............-|...\........./..\........../..../..-.......\\.............................../.......|..../|....
+....-...../......|.................|........-.......|.....|.../........-.....\.../..\.................../.....
+.............../................|...........\............/-..|......../............-./.-./...............-....
+.....\............|..\...............\..............\\.....-......./|....|.....--../...-..............\.......
+................|............../................/......./............-..-.................-....||......./....\
+.\..............\................|.......|.............|.........\|........\....-..../.............\..\/......
+./.....\.......|......|.\..|.../.............-......\...............................-......\......\...........
+.....|...../........../.......|.......................-.-.....\..................\............/....--./..-....
+....................|..............-.\\......\..........\.....\.-.../.-.......-.......-.............\......-..
+........./...................|.../....\...|...............|./../...-.........\-.................-.............
+....................../.....\....-.\.............|............-......\.........\......\.......................
+................\..\...|....-./..............-...\\.........\..........|......-.|/./.|..........\.\......../..
+......\........-.............-/.............../...............................-.............|..........|/.....
+....|.......-|...................................../.........\................./..........................\...
+....\.......\\........-....\........\....\.............\............\........./........................\......
+../.............................................................-......\..............|...................../.
+............/../.........................\................................................../...-.............
+.\........................\/.-...................-.......-...............|.....................-..............
+./........................|.|/................\..............././..................................|.-........
+............/........-..-..........|..............-........\../.|...\............................../..........
+............\/......-.........\\............-.....................\..........\....................|..../..../.
+..........\.../.....\.....................-..\..\.|..|....../-..|......-...|............-.....................
+......................-........\.........-......................|..........-..................................
+.|................\......-...........|.../....../............................................/......../...|../
+.........-..........\...-...-................\............/..-....|\..............-.......\.|..-.../-.........
+..|....../......./../-.............../....-......|-................................./......-...-...........-..
+.............../............../....-....\......../.\../...................-............../\............|.\.|..
+..|....\................-.....|.......................|\......................\.\..-...-..-...........|.......
+.......................|......................\.../......|.................-..../..-..-.\....\................
+..........................................-..........|-......................./-............-.................
+..../...../....\.|........................................././.../...........................\................
+......./...................................-............|-./.-.........\.|.../.-//...................-........
+/......................|............|/.............../-..............-...............|.......|......|...|.....
+....|.....-....-.....................\../..-...................\........./.../................./......-.......
+........................\..............................-.\.-...|..................../............./.....-..../
+......-.-...-........-.......\........../......|.........|..................../.....\./.....--...............|
+.........-/...............-\...\..........\................|........./.../........\.|......|..................
+..|/.................../......................................................../.....\..|.....|......-....-..
+......................./......................\.........-./......................-............................
+.....-.|.\................-............................|.............-........................../....-........
+..../..|..|.\....|....\.................\.........|...-..-................/......|............/..\..........|.
diff --git a/src/day_16.rs b/src/day_16.rs
new file mode 100644
index 0000000..f156ba8
--- /dev/null
+++ b/src/day_16.rs
@@ -0,0 +1,222 @@
+use std::collections::VecDeque;
+
+use crate::{Problem, Solution};
+
+pub struct Day16;
+
+impl Problem for Day16 {
+    const DAY: u8 = 16;
+
+    const INPUT: &'static str = include_str!("../input/day_16.txt");
+}
+
+impl Solution for Day16 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
+        let mut grid = parse_grid(input)?;
+
+        solve_grid(&mut grid, Beam::default());
+
+        Ok(score_grid(&grid))
+    }
+
+    fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
+        let grid = parse_grid(input)?;
+
+        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));
+        }
+
+        scores
+            .into_iter()
+            .max()
+            .ok_or_else(|| anyhow::anyhow!("Failed to get any scores"))
+    }
+}
+
+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<_>>()
+        })
+        .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 score_grid(grid: &Grid) -> usize {
+    grid.iter()
+        .flat_map(|v| v.iter())
+        .filter(|n| n.energized())
+        .count()
+}
+
+type Position = (usize, usize);
+type Grid = Vec<Vec<Node>>;
+type Beam = (Edge, Position);
+
+#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+enum Edge {
+    North,
+    #[default]
+    East,
+    South,
+    West,
+}
+
+impl Edge {
+    const ALL: [Edge; 4] = [Edge::North, Edge::East, Edge::South, Edge::West];
+
+    fn with_position(&self, (row, col): Position) -> Option<Position> {
+        Some(match self {
+            Edge::North => (row.checked_sub(1)?, col),
+            Edge::East => (row, col.checked_add(1)?),
+            Edge::South => (row.checked_add(1)?, col),
+            Edge::West => (row, col.checked_sub(1)?),
+        })
+    }
+
+    fn entry_points(&self, grid: &Grid) -> Vec<Position> {
+        match self {
+            Edge::North => (0..grid[0].len()).map(|c| (grid.len() - 1, c)).collect(),
+            Edge::East => (0..grid.len()).map(|r| (r, 0)).collect(),
+            Edge::South => (0..grid[0].len()).map(|c| (0, c)).collect(),
+            Edge::West => (0..grid.len()).map(|r| (r, grid[0].len() - 1)).collect(),
+        }
+    }
+}
+
+#[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 {
+    #[default]
+    Empty,
+    HorzSplit,
+    VertSplit,
+    FwrdMirror,
+    BackMirror,
+}
+
+impl TryFrom<char> for NodeType {
+    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,
+            c => anyhow::bail!("Invalid char: {c}"),
+        })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const INPUT: &str = indoc::indoc! {r#"
+        .|...\....
+        |.-.\.....
+        .....|-...
+        ........|.
+        ..........
+        .........\
+        ..../.\\..
+        .-.-/..|..
+        .|....-|.\
+        ..//.|....
+    "#};
+
+    #[test]
+    fn test_part_1() -> anyhow::Result<()> {
+        Ok(assert_eq!(46, Day16::part_1(INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2() -> anyhow::Result<()> {
+        Ok(assert_eq!(51, Day16::part_2(INPUT)?))
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 07918e3..2a9c662 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2,7 +2,8 @@
     iterator_try_collect,
     iter_array_chunks,
     array_windows,
-    iter_intersperse
+    iter_intersperse,
+    impl_trait_in_assoc_type
 )]
 
 pub mod day_01;
@@ -20,6 +21,7 @@ pub mod day_12;
 pub mod day_13;
 pub mod day_14;
 pub mod day_15;
+pub mod day_16;
 
 pub trait Problem {
     const DAY: u8;
diff --git a/src/main.rs b/src/main.rs
index 20896a1..5af80db 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,7 +1,7 @@
 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, day_10::Day10, day_11::Day11, day_12::Day12,
-    day_13::Day13, day_14::Day14, day_15::Day15, Solution,
+    day_13::Day13, day_14::Day14, day_15::Day15, day_16::Day16, Solution,
 };
 
 fn main() -> anyhow::Result<()> {
@@ -20,6 +20,7 @@ fn main() -> anyhow::Result<()> {
     Day13::solve()?;
     Day14::solve()?;
     Day15::solve()?;
+    Day16::solve()?;
 
     Ok(())
 }