From 765ab00a633b648a7d6d21e0e0a13b1e62243e06 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sat, 16 Dec 2023 19:43:25 -0600 Subject: feat: impl day 16 (brute force) --- input/day_16.txt | 110 +++++++++++++++++++++++++++ src/day_16.rs | 222 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 4 +- src/main.rs | 3 +- 4 files changed, 337 insertions(+), 2 deletions(-) create mode 100644 input/day_16.txt create mode 100644 src/day_16.rs 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 { + let mut grid = parse_grid(input)?; + + solve_grid(&mut grid, Beam::default()); + + Ok(score_grid(&grid)) + } + + fn part_2(input: &str) -> anyhow::Result { + 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 { + s.lines() + .enumerate() + .map(|(row, v)| { + v.chars() + .enumerate() + .map(|(col, value)| Node::try_from(((row, col), value))) + .try_collect::>() + }) + .try_collect::() +} + +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>; +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 { + 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 { + 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, +} + +impl Node { + fn handle_beam(&mut self, edge: Edge) -> Vec { + 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 { + 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 { + 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 for NodeType { + type Error = anyhow::Error; + + fn try_from(value: char) -> Result { + 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(()) } -- cgit v1.2.3-70-g09d2