From f527e4fc95ce1a49239e1d42255eee044fefe64b Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Sat, 16 Dec 2023 19:49:11 -0500 Subject: day 16 --- benches/2023.rs | 5 ++ data/2023/16.txt | 110 ++++++++++++++++++++++++++ src/bin/2023/day16.rs | 209 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2023/main.rs | 2 + 4 files changed, 326 insertions(+) create mode 100644 data/2023/16.txt create mode 100644 src/bin/2023/day16.rs 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 for Tile { + type Error = anyhow::Error; + + fn try_from(value: u8) -> std::result::Result { + 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, +} + +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 { + Ok(Map { + map: parse::grid(parse::raw_lines(fh), |c, _, _| { + c.try_into().unwrap() + }), + }) +} + +pub fn part1(map: Map) -> Result { + Ok(map + .count_energized_from(Row(0), Col(0), Direction::Right) + .try_into() + .unwrap()) +} + +pub fn part2(map: Map) -> Result { + 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), } -- cgit v1.2.3-54-g00ecf