From d989134cd57c4c3ba0e7a743dc6b0b193d9ec2ba Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sat, 16 Dec 2023 09:25:38 +0200 Subject: Day 16 part 1 --- 2023/inputs/day_16.txt | 110 ++++++++++++++++++++++++++++++++ 2023/src/bin/day_16.rs | 170 ++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 271 insertions(+), 9 deletions(-) create mode 100644 2023/inputs/day_16.txt 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> { - 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>, + light: Vec>>, + 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 = 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 { + 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, + } } } -- cgit v1.2.3