diff options
author | Toby Vincent <tobyv@tobyvin.dev> | 2023-12-16 19:43:25 -0600 |
---|---|---|
committer | Toby Vincent <tobyv@tobyvin.dev> | 2023-12-16 19:46:22 -0600 |
commit | 765ab00a633b648a7d6d21e0e0a13b1e62243e06 (patch) | |
tree | aa27067a1a6f063a0365f40bd98285f40d5dd67d /src/day_16.rs | |
parent | ae6bbe50b76d73c60eb109b1a0916b093eb3adc9 (diff) |
feat: impl day 16 (brute force)
Diffstat (limited to 'src/day_16.rs')
-rw-r--r-- | src/day_16.rs | 222 |
1 files changed, 222 insertions, 0 deletions
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)?)) + } +} |