day 16

4 files changed, 326 insertions, 0 deletions

diff --git a/benches/2023.rs b/benches/2023.rs
index ca826ed..337da46 100644
--- a/benches/2023.rs
+++ b/benches/2023.rs
@@ -31,6 +31,8 @@ mod day13;
 mod day14;
 #[path = "../src/bin/2023/day15.rs"]
 mod day15;
+#[path = "../src/bin/2023/day16.rs"]
+mod day16;
 // NEXT MOD
 
 day!(2023, 1, day1);
@@ -48,6 +50,7 @@ day!(2023, 12, day12);
 day!(2023, 13, day13);
 day!(2023, 14, day14);
 day!(2023, 15, day15);
+day!(2023, 16, day16);
 // NEXT DAY
 
 fn bench_2023(c: &mut criterion::Criterion) {
@@ -68,6 +71,7 @@ fn bench_2023(c: &mut criterion::Criterion) {
             day_combined!(2023, 13, day13);
             day_combined!(2023, 14, day14);
             day_combined!(2023, 15, day15);
+            day_combined!(2023, 16, day16);
             // NEXT DAY COMBINED
         })
     });
@@ -91,5 +95,6 @@ criterion::criterion_main!(
     bench_2023day13,
     bench_2023day14,
     bench_2023day15,
+    bench_2023day16,
     // NEXT GROUP
 );
diff --git a/data/2023/16.txt b/data/2023/16.txt
new file mode 100644
index 0000000..9e078ce
--- /dev/null
+++ b/data/2023/16.txt
@@ -0,0 +1,110 @@
+\|.......|........|...../........................\.\.......\...-../..........\.........|...\......|...........
+.|.../............|.....|\..../....-.\...........-............./......................|.-.-...........\.....-.
+...............|........-....-...../..../|./.............\..|..................\..........|\.........../.\....
+....................|\..................\..................\/....................-....../................\.|..
+......././-......................................|.....|./.............................../....................
+.......................\.....|............-...\..|......-./...\.........../.............|..-......-...../.....
+.....................-.......\.......|............./........\.......|........../............/.................
+..................-................-./....................|....|...................-..................\.......
+|.......././.................................|.....-............................-.........|......../../.......
+.........../.......-........|................/......-....|.......\/..|..\...|..............-....\....|...-....
+............./-......./.....-./....\........./..|...............|..-......................-...................
+......-\.\..|/......-.|.........-.......-..\|.............................\.-.............\...............\...
+......\..../................\.........\..|...............-.......|..-|.....|-..........................-......
+.....\....../../..........\......-...........\.......-.\........./...........|\............-.............\....
+........\....................|........./...................|.........-.........\..............................
+.........-|.............\-.............................-..............|.....\../......|/......................
+..................../.......\/......./................../...../.......................|......|./.-......-|....
+..................../.........|..-.-./....../.|-..\..|........|......-.................\...\........./...\....
+....-...-....../...............................................|....................\..-..............-..|.-.\
+..........\..\.\....................-...|......................\......|......-.................\....|....../..
+\................../.....-./.......-...........\..../....../....|.........|........................|..........
+../......\.|..............................|../......................-.\..........\...............|..........|.
+.|..............................-...-........|...-........|........../............\...../.\......-....|.......
+............./...................\.\.........|...|../..........-.......\........../.-.-.....-..........-......
+..........................-.|\......|......./|.............../..../......--.....|.........|........../........
+/-....|/...-|..........\......................./..........-.....-.............\....../................\.......
+............-../............\...............................-.........\...\...........|-....|.................
+..............................|........-.........-..................|...........................-.............
+........./...............//.........................................-..........|............|..../............
+...\..||../........................./................|......./.......|....|.....|............|................
+........./...................\-./.......\...../............../..........-|...................|..../.......|...
+...../................/..-............../....................|/......................................-.|......
+\|........................................\...........-......../...\.|......|..\../........|.......\..........
+..|/......\....-...............||......//..................\\..-./...-....................|...................
+./....../................\../.\.....\.........\.\\\..........................-..\..-............./-...........
+........|..........-.....|..\..../....../.................../.............\...-.\...........\...........-.....
+..........\...|/..|......|\/./...........-.|.................-.|....|....................../..................
+-.......................-.|.............-../......./.../...-|..|.........../../..\............\../..........|.
+................./.........\..........-.........../..|.......//..............|..................|.....\.......
+.............-../......\./.../.|.|.....-..|.....|...\.........|.....-/..................-................|....
+|.-\..../...........-.....|....................//........\............./....../........./../\..\....-.........
+......\.|...........|..............|............/....-../.....\..................../...................|......
+../|....\....................................-.....--...|....../........-...................|...\.......\.....
+..........|../..-.........-...........|....................../............/.......................|.|.........
+........./..................\............................\..............|..................................\..
+...-|...........-......\|\...........\...\.........|..../......../..../..../..-|||................-...........
+..|....-\..\......./...........\\.................................|......-./.............../........|..--.....
+.................................../|...........-.......-...|..-............-........../......................
+.......|.............|.......................................................\...............\................
+........\.......|...........|............................\-......................................|............
+......|..\.-../......................|.-.../.....-..|.-.................................-.......\......./.|...
+--\...../..........-...........\...................../.....|/............\..............-............./.......
+......|-...............\........................................../.-\..|.....-........|..\./../.-..........|.
+.........................//.....-...................|...|..-.\....|................|......\..-............/...
+./.........-...-....................../......\\......||..........|....................--.................../..
+....-........\........................../..........|........./.........................\.\....|.......-|......
+.|\/...............|...-.|....|../..|...|...../......\..........|.............|........\.....|................
+...../.-\.-................|......../....-..\......|/.......\.......................\.......................|.
+......................|..........-..../..../.\../................../......................|..............\|...
+........../-\......|............................../....-......................................./..............
+./..........|.....-.............-..-...|../........\.-...........|.........................-................-.
+.-....-................|..................-...-...........-........|.|..........-.-...........................
+...|...............|.................\.......|.............../................\....|.............|.........\..
+..\..............|.............\..................\.......................|..........-........................
+../........./............\.\../.........................\../.....-....|....................-............../...
+...\................\......../......................./\....\..-........\........./..\.........................
+.........../..|.......-.........-|..............................................\...............-./\||...../..
+...............\........-..|..........||......................../..........-...../........................\...
+...........\.....................-................................................................|..........|
+./.........-.......-................................\..........||..|.|..\.........\.../..||......-.......\....
+\......\.........-..\......\...................-..|.....\.....\....................|..........-......-........
+.............|..........\..........-..................\.\..........|.....................|.............-/.....
+........-................|......./..-...............\......|-...\.....\.............|./..\\../....-.../.......
+..................\..||.............-........|............/.........\../...\..|/.....\.........\..........|...
+..|../..................\..............................|...........................................-..........
+\..................../.|.......\...|-............../......\.............././..-...................|...........
+......./..............................\..................|................\............./....-.....-..........
+..............|.........../...............................\.................\..|........-.......-.\.....|.....
+.................|.....\........................................-.\.\..\...................//.....\./.........
+....../..........|..-............/..........\............../.............|....................................
+.............|..........-.|..\..........-....\...........................|.....................\.\....-.......
+..........\............../........-........|.....-./...........................................\..........\...
+..........|.-...|.|...............-...|.|..................-...-........|/.../.............................\..
+.............-....\.....................................................\........................|...........\
+..\|...........|....-.-|........................................|.............................\.....\.-|......
+...........//.|.............-......\.........................|............-|...............././.....|....|....
+.............../.\...............--........|........-....\..../.........-.....................-......../...-..
+.....|......\.........../............/..................../.........|...........-.......-.|...........-.......
+.................-........./..........|...................../..........................|.|...........-.......|
+.....|...-........|...................../.../...................................\.............\...|...........
+.............\.......|........................./....|........./........\.........\.......................\....
+............................/-..................................../........-..............\...|.....\..|\.....
+...-..././....................-.......|................./..........-.....|.|..............\..........-....\...
+.....\\......\...............................-...-........-.|..../........\.\.....-.....................|.....
+..............\.........\.\.|..........-......//./.../....|.............-.../..|.........................\....
+...................../...........\.........................\.-..|..........|........./|...............|/...\|.
+..|.-./.............-.........././.|......../.......\...........-.........../..........\.....-.........-......
+.....|......\....-.........-.............|.......|-........|-...-../-..|.......-................-.............
+.................|.........|....\................................/.-.....|........./..../..........-..........
+-....\......./......\.\..................-..|./......-...\.\...-.........................\.............|......
+......................./..............\/..........-................../............\.......\..\.......\....../.
+.|...............//.................................../.......\.......\.\..........-\...|............-........
+.../......................|.....-.........../................-.../............../.........\.\.../........../..
+..................................|\..................-../........-./..\......./....|../.......|-.............
+.....\..........|................/........\..........-......../\../..../.\-.|...\....|\.............\|..--....
+................./................................././|..../..........|............../............../.........
+..............|......|.......\....|...|......|..................................\.......-....\/...........|...
+......./\..................................-......./......\....\..-..................-................\......|
+...........-.........../..............\............|....../....../.......\........./......../..\.........\...-
+.-..................\............................/\...................|...........|....\....\--/............/.
diff --git a/src/bin/2023/day16.rs b/src/bin/2023/day16.rs
new file mode 100644
index 0000000..3460b5e
--- /dev/null
+++ b/src/bin/2023/day16.rs
@@ -0,0 +1,209 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+fn add_offset(
+    row: Row,
+    col: Col,
+    row_offset: IRow,
+    col_offset: ICol,
+    max_row: Row,
+    max_col: Col,
+) -> Option<(Row, Col)> {
+    if let (Some(row), Some(col)) = (
+        row.0.checked_add_signed(row_offset.0),
+        col.0.checked_add_signed(col_offset.0),
+    ) {
+        let row = Row(row);
+        let col = Col(col);
+        if row < max_row && col < max_col {
+            return Some((row, col));
+        }
+    }
+    None
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug)]
+enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+impl Direction {
+    fn horizontal(&self) -> bool {
+        matches!(self, Self::Left | Self::Right)
+    }
+
+    fn increasing(&self) -> bool {
+        matches!(self, Self::Down | Self::Right)
+    }
+
+    fn offset(&self) -> (IRow, ICol) {
+        match self {
+            Self::Up => (IRow(-1), ICol(0)),
+            Self::Down => (IRow(1), ICol(0)),
+            Self::Left => (IRow(0), ICol(-1)),
+            Self::Right => (IRow(0), ICol(1)),
+        }
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash, Default)]
+pub enum Tile {
+    #[default]
+    Floor,
+    Vertical,
+    Horizontal,
+    Rising,
+    Falling,
+}
+
+impl TryFrom<u8> for Tile {
+    type Error = anyhow::Error;
+
+    fn try_from(value: u8) -> std::result::Result<Self, Self::Error> {
+        Ok(match value {
+            b'.' => Self::Floor,
+            b'|' => Self::Vertical,
+            b'-' => Self::Horizontal,
+            b'/' => Self::Rising,
+            b'\\' => Self::Falling,
+            _ => bail!("unknown tile {value}"),
+        })
+    }
+}
+
+pub struct Map {
+    map: Grid<Tile>,
+}
+
+impl Map {
+    fn count_energized_from(
+        &self,
+        row: Row,
+        col: Col,
+        direction: Direction,
+    ) -> usize {
+        let mut energized = HashMap::new();
+        let mut rays = vec![(row, col, direction)];
+        while let Some(ray) = rays.pop() {
+            let (row, col, direction) = ray;
+            let directions: &mut Vec<_> =
+                energized.entry((row, col)).or_default();
+            if directions.contains(&direction) {
+                continue;
+            }
+            directions.push(direction);
+            let next = self.next(row, col, direction);
+            rays.extend(next);
+        }
+        energized.into_keys().count()
+    }
+
+    fn next(
+        &self,
+        row: Row,
+        col: Col,
+        direction: Direction,
+    ) -> Vec<(Row, Col, Direction)> {
+        let directions = match self.map[row][col] {
+            Tile::Floor => vec![direction],
+            Tile::Vertical => {
+                if direction.horizontal() {
+                    vec![Direction::Up, Direction::Down]
+                } else {
+                    vec![direction]
+                }
+            }
+            Tile::Horizontal => {
+                if direction.horizontal() {
+                    vec![direction]
+                } else {
+                    vec![Direction::Left, Direction::Right]
+                }
+            }
+            Tile::Rising => vec![match direction {
+                Direction::Up => Direction::Right,
+                Direction::Down => Direction::Left,
+                Direction::Left => Direction::Down,
+                Direction::Right => Direction::Up,
+            }],
+            Tile::Falling => vec![match direction {
+                Direction::Up => Direction::Left,
+                Direction::Down => Direction::Right,
+                Direction::Left => Direction::Up,
+                Direction::Right => Direction::Down,
+            }],
+        };
+        directions
+            .into_iter()
+            .filter_map(|direction| {
+                let offsets = direction.offset();
+                add_offset(
+                    row,
+                    col,
+                    offsets.0,
+                    offsets.1,
+                    self.map.rows(),
+                    self.map.cols(),
+                )
+                .map(|(row, col)| (row, col, direction))
+            })
+            .collect()
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    Ok(Map {
+        map: parse::grid(parse::raw_lines(fh), |c, _, _| {
+            c.try_into().unwrap()
+        }),
+    })
+}
+
+pub fn part1(map: Map) -> Result<i64> {
+    Ok(map
+        .count_energized_from(Row(0), Col(0), Direction::Right)
+        .try_into()
+        .unwrap())
+}
+
+pub fn part2(map: Map) -> Result<i64> {
+    Ok(map
+        .map
+        .each_row()
+        .flat_map(|row| {
+            [
+                (row, Col(0), Direction::Right),
+                (row, map.map.cols() - 1, Direction::Left),
+            ]
+        })
+        .chain(map.map.each_col().flat_map(|col| {
+            [
+                (Row(0), col, Direction::Down),
+                (map.map.rows() - 1, col, Direction::Up),
+            ]
+        }))
+        .map(|(row, col, direction)| {
+            map.count_energized_from(row, col, direction)
+        })
+        .max()
+        .unwrap()
+        .try_into()
+        .unwrap())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2023, 16).unwrap()).unwrap()).unwrap(),
+        7498
+    );
+    assert_eq!(
+        part2(parse(parse::data(2023, 16).unwrap()).unwrap()).unwrap(),
+        7846
+    );
+}
diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs
index 31e55c5..842092a 100644
--- a/src/bin/2023/main.rs
+++ b/src/bin/2023/main.rs
@@ -26,6 +26,7 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
 // NEXT MOD
 
 #[paw::main]
@@ -47,6 +48,7 @@ fn main(opt: Opt) -> Result<()> {
         13 => advent_of_code::day!(2023, opt.day, opt.puzzle, day13),
         14 => advent_of_code::day!(2023, opt.day, opt.puzzle, day14),
         15 => advent_of_code::day!(2023, opt.day, opt.puzzle, day15),
+        16 => advent_of_code::day!(2023, opt.day, opt.puzzle, day16),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }