Day 16 part 1

2 files changed, 271 insertions, 9 deletions

diff --git a/2023/inputs/day_16.txt b/2023/inputs/day_16.txt
new file mode 100644
index 0000000..cb1916e
--- /dev/null
+++ b/2023/inputs/day_16.txt
@@ -0,0 +1,110 @@
+\....../..-......-.\.........\.......................-....../......../....................................|...
+......\../../.....\-................../...........|................-../.............-./........|.|............
+..-...-..../..............................-..............\.........-../...........................-.\.......\.
+............./-..........|..............\/.................../........../............\.......|................
+....|.....\.../...|..............\/..|-.................-..........\.\........................\...............
+...........\...........-..|..../..\.-|........................-/.|/....../.........\.....|................/...
+./....-|./.......|......-...-............-.......-......................................../....-............\.
+....\...........|............-............-..\..|...|.........-..||.................\/...........|-|.|-.......
+-............................-....................|........-...............\..................\...............
+...............\......................-....../......|..||.|.-........................./......-............\...
+.-...|........-.......|.........|....|.....-.........|..|............................./.../\...-........\.....
+....................../...........-......-..--.|-...............-....................\......\.................
+-....................-......-......./.......\|./......./........|...........|..................|..............
+..-............../....................|.............-.......-.................-..................\......\.|...
+....................\...............................................|.....\................../..-/............
+...-.-/...\.//...|.............|........................\.............-|..|...........--..\........./...\.....
+....................................................................\..........-......................-/......
+..................................\......-.....-...........-.............-...........\...................|...-
+......................\........|../..............-.........../......-...|......../.\......./..||..............
+................................/......-................................./.........-......\./......|..........
+........../....../....\.\|......-..............................\.....................--......|.............\..
+..-.................-............../\............|.......................................\...|....\...........
+./................\.|....\.........................../................|..............-....-..../..............
+../...........\.\/./........\........-\...-/...........-............../........................|..............
+......\.||.....................|..................\..............|........../......\/........../.....-........
+..|/...........\.....|../.......\...........-.............|..............-........|...............-.....|.....
+....................../.....-..|.......-...-...|.....................|./...\.........-........................
+......................../........../\../.........-...\........./...............................|..\...........
+.......................|\............./...|...............\/-...............|........................../..\...
+..|....-.......\..................................\................................|......../.|..............-
+........../...\.\........-......|.\.|.....................-............/..\..........|.../...-.............../
+..\.-..............-............/..-..\..............\.........\....../...|........|........\....../..........
+.....................|........................../..|....|.-.../........................-.\../-................
+./..........-....|......|.|.................-....|........\......|............../.........................../.
+....-..................................................................................-............|..-....//
+......./...-.......................-..-.........-.............|........................../....................
+.-...................-.......................................|.......-.................../..\...............\|
+.........|.\......-.....\............./-....................../.........-..|....|......-......................
+......./............./..........-......-......\...................................../............/..\.........
+.....\......-................................/..........|.............\........\............/.................
+......../..............\.........................|..........\......-............\.....|.....\....|...\|....-..
+.....\.......\/................/...\.......|./......|............\./..........|/.....\\..\...\...|..-.........
+..................|.....................-..........\....................../...../..............|......../..../
+........./...........|....-..\.....................--..|......|...\|.......|...............|...-.||...........
+..............-.....\...|...|./...|..........-......../......./..........-...../..|........../................
+..|.../...................................|...................|......./..-.....-..............-...............
+...-.........../..................-..........|.........................\..-................//\............/...
+|...............\.........\.../.....................|.....-........................\...........-../.-......-..
+........//..........-......................-....\...-.......-./.../......../........./...........|.|..........
+...................\..../...../...|........--.....\../..........|...........................|.\...............
+.\......................-........|\.....\....|.........\...............|.......\...-...|.................-....
+.....................|......./..-........................../......-.........../........................../....
+--.............\..........\-..../..-........\....-..........|./....|.\.................-..--.....\../.........
+.......|........../|...................|.................\..-..........\../....|\.....|...-.......\..-........
+........../|.|.....\....................|\..\...........-............./.......|.\.............................
+...........|..........-..............|.....|-................/.........|..../.........................-.......
+......-..........................|............-.......|/...-....--/................/..-.........|.............
+......../.-.............|....\.../............................|.|.....|....../...............\............./..
+........./.......\..........\...........\.....\..|....-...../........./........................./..|..........
+...|...|........\.......-.......\..................\....................../............-...|.........\........
+.........-...........|.........\....................../..........-.....\|.\...................\...............
+.....|..........|................................../......................|............/.....|.........|..-|..
+.../.......\....//....../....\....../..........\........................./....................\....-.../......
+/.......\..\...........\................-|............/...-|.|...-..........\.................\.....|.../.....
+.....-\.........|....../.......\.............-..........................\...........................\.........
+.|.............|................\....\...........-................./............./............................
+./...|\...........-\....................\..............-....|....|..........-.........|.../.....-.....\.\.....
+....-...............|........-............./.....\....../..\.|.....|./.\......-...........\....../.\.......\..
+..........\.....\................../......|.\..../.\..-......-.........-............/....\...................\
+..\.........|.....\..........\............./...-....../....|.......-|\-............................../........
+..|...\/........\..-\.|.\......./.....|.........-..|........|......................|..........................
+............|..........................--.-....\..............-................................|...|..........
+.-............../.....................|........../.................-....../.-...........................\-....
+.-.........................-......|-./\.........................\.....|.................|......|..\.......\...
+.....\...|....-......................................-...............\...........\..\...\..-|.....\...........
+|...........|................|.........-............|....................|............-..-.............../....
+.................../.|...........\.......\....|......-..|.....................\...................|..\.....\..
+.|........-.../...|....../...|......|.|.|..-......\............../....|...........\|.......|.......\\.........
+.......|.....-..-.-./....-/\.|./.............|.../......\...|/............/........./...-..........|\.\.......
+..|.........-....\.........\.......\....-................|-..........................-.|............|.........
+......-..\......|..\.../......\|..........|............../........../............/..\........................|
+|/.|................../....|............../..........-........-............................|.\................
+........|.....|/................../....\....../....../...................--..............\/..\................
+.../-..........................|...-.........-.................\\.......-\.........\..|.....|.................
+-./...-.....-....................../.../........./........-........../.........-...........\..................
+.\../............|.\..........-.................................\.............../............../.........\./..
+...-.....-......-......../.\...\................\...........|.................................................
+...........-...//.....-/...-...........\|./......................\.........................|.-|...|...........
+....../.....................-.......|........|-..................\............-.....................|.........
+.....................\.\................../..|/......\........|.\..............|\..............\..-...........
+....\................|\......................./.....-...............................-......../....-...........
+...\....................-....|......|........-.\..|.......................\...\.|..............|............/.
+...................-/.....................................-..\............-............-.............-....\...
+.|....../.....\.....-.../......../..../..\.-...........\.../................|........\.................../....
+.......|........./........................\.....-........-...............\....../....|../....\......./........
+..........|.........../|......|......................-..............|./......................................\
+....................../...../..............|.||............./......-......\...................................
+\........|...-..................\./.................\.\.........-....\........../.../.-...\...................
+....-..........|.......-......../................................./.../....-.............-..........\-........
+..............................-.............\..\......................................-......../..............
+......./.\|......../...-........|.........|................/.........................-....|...\.........|.....
+......|..........-.......-............./........|..\...|.|..-.............................-.-...\.............
+.||...........-.......\...../.....................-././..../.............-................|../.............--.
+................\.-.....-\..........\.............\............/.........\.......-........\...................
+......./...........\........\./.|..............|......-...........\................\...../.\...../..........|.
+.-..-...|.....................-....../..............-.\|....\.......|..|....././.......|......................
+./...-..................../................/....-/..\............/..................................\.........
+....\.-..........\-......../............|...\.............|..................|.....\.................../......
+...........-/..\..-................-....|............/...-.|.......-.|........./.....-/......./...............
+..../...-.....\..............-..\.....\.|............./...|.\..................\...|.........\-./..|...../....
diff --git a/2023/src/bin/day_16.rs b/2023/src/bin/day_16.rs
index b3a610b..f9614be 100644
--- a/2023/src/bin/day_16.rs
+++ b/2023/src/bin/day_16.rs
@@ -1,19 +1,171 @@
-use nom::IResult;
-use std::fs;
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::line_ending,
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    IResult,
+};
+use std::{collections::BTreeSet, fs};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let input = fs::read_to_string("inputs/day_16.txt")?;
+    let mut device = LightDevice::parser(&input).unwrap().1;
+    device.energize();
+    dbg!(&device.count_energized_blocks());
 
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct LightDevice {
+    mirrors: Vec<Vec<LightBlock>>,
+    light: Vec<Vec<BTreeSet<Direction>>>,
+    bounds: Point,
+}
+
+#[derive(Debug, Clone, Copy)]
+enum LightBlock {
+    MirrorForwardLeaning,   // /
+    MirrorBackwardsLeaning, // \
+    Empty,                  // .
+    HorizontalSplitter,     // -
+    VerticalSplitter,       // |
+}
+
+#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)]
+enum Direction {
+    North,
+    South,
+    East,
+    West,
+}
+
+#[derive(Debug, Clone)]
+struct Point {
+    x: usize,
+    y: usize,
+}
+
+impl LightDevice {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(line_ending, many1(LightBlock::parser)),
+            |mirrors| LightDevice {
+                bounds: Point {
+                    x: mirrors[0].len(),
+                    y: mirrors.len(),
+                },
+                light: mirrors
+                    .iter()
+                    .map(|mirror_row| vec![BTreeSet::new(); mirror_row.len()])
+                    .collect(),
+                mirrors,
+            },
+        )(input)
+    }
+
+    fn energize(&mut self) {
+        let mut frontier = vec![(Point { x: 0, y: 0 }, Direction::East)];
+        self.light[0][0].insert(Direction::East);
+
+        while let Some((front_light_p, front_light_dir)) = frontier.pop() {
+            let mirror = self.mirrors[front_light_p.y][front_light_p.x];
+            let new_dirs: Vec<Direction> = match (mirror, front_light_dir) {
+                (LightBlock::MirrorForwardLeaning, Direction::North) => vec![Direction::East],
+                (LightBlock::MirrorForwardLeaning, Direction::South) => vec![Direction::West],
+                (LightBlock::MirrorForwardLeaning, Direction::East) => vec![Direction::North],
+                (LightBlock::MirrorForwardLeaning, Direction::West) => vec![Direction::South],
+                (LightBlock::MirrorBackwardsLeaning, Direction::North) => vec![Direction::West],
+                (LightBlock::MirrorBackwardsLeaning, Direction::South) => vec![Direction::East],
+                (LightBlock::MirrorBackwardsLeaning, Direction::East) => vec![Direction::South],
+                (LightBlock::MirrorBackwardsLeaning, Direction::West) => vec![Direction::North],
+                (LightBlock::HorizontalSplitter, Direction::North)
+                | (LightBlock::HorizontalSplitter, Direction::South) => {
+                    vec![Direction::East, Direction::West]
+                }
+                (LightBlock::VerticalSplitter, Direction::East)
+                | (LightBlock::VerticalSplitter, Direction::West) => {
+                    vec![Direction::North, Direction::South]
+                }
+                (LightBlock::Empty, dir)
+                | (LightBlock::HorizontalSplitter, dir)
+                | (LightBlock::VerticalSplitter, dir) => vec![dir],
+            };
+
+            let new_lights: Vec<(Point, Direction)> = new_dirs
+                .into_iter()
+                .filter_map(|dir| front_light_p.go(dir, &self.bounds).map(|p| (p, dir)))
+                .collect();
+
+            for (new_light_p, new_light_dir) in new_lights {
+                if !self.light[new_light_p.y][new_light_p.x].contains(&new_light_dir) {
+                    self.light[new_light_p.y][new_light_p.x].insert(new_light_dir);
+                    frontier.push((new_light_p, new_light_dir));
+                }
+            }
+
+            //            println!("{:?}", &frontier);
+        }
+    }
+
+    fn count_energized_blocks(&self) -> usize {
+        self.light
+            .iter()
+            .flat_map(|row| row.iter())
+            .filter(|set| set.len() > 0)
+            .count()
+    }
+}
+
+impl LightBlock {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        alt((
+            value(LightBlock::MirrorForwardLeaning, tag("/")),
+            value(LightBlock::MirrorBackwardsLeaning, tag("\\")),
+            value(LightBlock::Empty, tag(".")),
+            value(LightBlock::HorizontalSplitter, tag("-")),
+            value(LightBlock::VerticalSplitter, tag("|")),
+        ))(input)
+    }
+}
+
+impl Point {
+    fn up(&self) -> Point {
+        Point {
+            x: self.x,
+            y: self.y - 1,
+        }
+    }
+
+    fn down(&self) -> Point {
+        Point {
+            x: self.x,
+            y: self.y + 1,
+        }
+    }
+
+    fn left(&self) -> Point {
+        Point {
+            x: self.x - 1,
+            y: self.y,
+        }
+    }
+
+    fn right(&self) -> Point {
+        Point {
+            x: self.x + 1,
+            y: self.y,
+        }
+    }
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+    fn go(&self, dir: Direction, bounds: &Point) -> Option<Point> {
+        match dir {
+            Direction::North if self.y > 0 => Some(self.up()),
+            Direction::South if self.y < bounds.y - 1 => Some(self.down()),
+            Direction::West if self.x > 0 => Some(self.left()),
+            Direction::East if self.x < bounds.x - 1 => Some(self.right()),
+            _ => None,
+        }
     }
 }