diff options
Diffstat (limited to '2023/src/bin/day_18.rs')
| -rw-r--r-- | 2023/src/bin/day_18.rs | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/2023/src/bin/day_18.rs b/2023/src/bin/day_18.rs new file mode 100644 index 0000000..a4c9355 --- /dev/null +++ b/2023/src/bin/day_18.rs @@ -0,0 +1,214 @@ +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_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()); + dbg!(&parsed.find_internal_area()); + + let hex_parsed = Instructions::hex_parser(&input).unwrap().1; + dbg!(&hex_parsed.find_internal_area()); + + Ok(()) +} + +#[derive(Debug)] +struct Instructions(Vec<Instruction>); + +#[derive(Debug)] +struct Instruction { + direction: Vector2<i64>, + distance: u32, +} + +#[derive(Debug)] +struct FloodFillMap { + map: HashMap<Point2<i64>, Fill>, + top_left: Point2<i64>, + bottom_right: Point2<i64>, +} + +#[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) + } + + fn find_internal_area(&self) -> i64 { + let mut current_point = Point2::new(0, 0); + let mut points = vec![current_point]; + + let mut perimeter = 0; + for instruction in &self.0 { + let next_point = current_point + instruction.direction * instruction.distance as i64; + points.push(next_point); + current_point = next_point; + perimeter += instruction.distance as i64; + } + + let mut area = 0; + for point in points.windows(2) { + if let &[p1, p2] = point { + area += p1.x * p2.y; + area -= p1.y * p2.x; + } else { + unreachable!() + } + } + + (perimeter + 2 + area) / 2 + } +} + +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<i64>> { + 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<i64>> { + 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<i64>, 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<i64>, 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)); + } + } + } +} |