diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2023-12-18 19:07:20 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2023-12-18 19:07:20 +0200 |
commit | a2ce5eb7f720d17aac648a5b3fd8e97df198803c (patch) | |
tree | f3685b77f5f2313687e1327e2bbffb81a39289c4 /2023/src/bin | |
parent | 29ad35f8c97b0adb61987ff51cee122814927c73 (diff) |
Day 18 part 1
Diffstat (limited to '2023/src/bin')
-rw-r--r-- | 2023/src/bin/day_18.rs | 186 |
1 files changed, 177 insertions, 9 deletions
diff --git a/2023/src/bin/day_18.rs b/2023/src/bin/day_18.rs index b3a610b..c3e9f58 100644 --- a/2023/src/bin/day_18.rs +++ b/2023/src/bin/day_18.rs @@ -1,19 +1,187 @@ -use nom::IResult; -use std::fs; +use nalgebra::{Point2, Vector2}; +use nom::{ + branch::alt, + bytes::complete::{tag, take}, + character::complete::{char, hex_digit1, line_ending, space1, u32}, + combinator::{map, map_res, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::HashMap, fs}; fn main() -> Result<(), Box<dyn std::error::Error>> { - 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_18.txt")?; + let parsed = Instructions::parser(&input).unwrap().1; + let mut fill_map = parsed.draw_map(); + fill_map.derive_inside_outside(); + dbg!(&fill_map.count_inside()); + let hex_parsed = Instructions::hex_parser(&input).unwrap().1; + dbg!(&hex_parsed); Ok(()) } #[derive(Debug)] -struct Example; +struct Instructions(Vec<Instruction>); -impl Example { - fn parser(_input: &str) -> IResult<&str, Self> { - todo!() +#[derive(Debug)] +struct Instruction { + direction: Vector2<i32>, + distance: u32, +} + +#[derive(Debug)] +struct FloodFillMap { + map: HashMap<Point2<i32>, Fill>, + top_left: Point2<i32>, + bottom_right: Point2<i32>, +} + +#[derive(Debug, PartialEq, Eq, Clone, Copy)] +enum Fill { + Outside, + Inside, +} + +impl Instructions { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, Instruction::parser), + Instructions, + )(input) + } + + fn hex_parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, Instruction::hex_parser), + Instructions, + )(input) + } + + fn draw_map(&self) -> FloodFillMap { + let mut trench = HashMap::new(); + let mut current = Point2::new(0, 0); + for instruction in &self.0 { + for _ in 0..instruction.distance { + current += instruction.direction; + trench.insert(current.clone(), Fill::Inside); + } + } + + FloodFillMap::new(trench) + } +} + +impl Instruction { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + dir_parser, + space1, + u32, + space1, + tag("(#"), + hex_digit1, + tag(")"), + )), + |(direction, _, distance, _, _, _, _)| Instruction { + direction, + distance, + }, + )(input) + } + + fn hex_parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + dir_parser, + space1, + u32, + space1, + tag("(#"), + map_res(take(5usize), |hex| u32::from_str_radix(hex, 16)), + hex_dir_parser, + tag(")"), + )), + |(_, _, _, _, _, distance, direction, _)| Instruction { + direction, + distance, + }, + )(input) + } +} + +fn dir_parser(input: &str) -> IResult<&str, Vector2<i32>> { + alt(( + value(Vector2::new(0, -1), char('U')), + value(Vector2::new(0, 1), char('D')), + value(Vector2::new(-1, 0), char('L')), + value(Vector2::new(1, 0), char('R')), + ))(input) +} + +fn hex_dir_parser(input: &str) -> IResult<&str, Vector2<i32>> { + alt(( + value(Vector2::new(0, -1), char('3')), + value(Vector2::new(0, 1), char('1')), + value(Vector2::new(-1, 0), char('2')), + value(Vector2::new(1, 0), char('0')), + ))(input) +} + +impl FloodFillMap { + fn new(map: HashMap<Point2<i32>, Fill>) -> FloodFillMap { + let top_left = Point2::new( + map.keys().map(|key| key.x).min().unwrap() - 1, + map.keys().map(|key| key.y).min().unwrap() - 1, + ); + + let bottom_right = Point2::new( + map.keys().map(|key| key.x).max().unwrap() + 1, + map.keys().map(|key| key.y).max().unwrap() + 1, + ); + + FloodFillMap { + map, + top_left, + bottom_right, + } + } + + fn derive_inside_outside(&mut self) { + self.flood_fill(self.top_left.clone(), &Fill::Outside); + for y in self.top_left.y..=self.bottom_right.y { + for x in self.top_left.x..=self.bottom_right.x { + let current = Point2::new(x, y); + self.map.entry(current).or_insert(Fill::Inside); + } + } + } + + fn count_inside(&self) -> usize { + self.map + .values() + .filter(|fill| **fill == Fill::Inside) + .count() + } + + fn flood_fill(&mut self, start: Point2<i32>, fill: &Fill) { + let mut to_fill = vec![start]; + + while let Some(next) = to_fill.pop() { + if next.y >= self.top_left.y + && next.x >= self.top_left.x + && next.y <= self.bottom_right.y + && next.x <= self.bottom_right.x + && !self.map.contains_key(&next) + { + self.map.insert(next.clone(), fill.clone()); + to_fill.push(next + Vector2::new(-1, 0)); + to_fill.push(next + Vector2::new(1, 0)); + to_fill.push(next + Vector2::new(0, -1)); + to_fill.push(next + Vector2::new(0, 1)); + } + } } } |