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> { 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 Instructions(Vec); #[derive(Debug)] struct Instruction { direction: Vector2, distance: u32, } #[derive(Debug)] struct FloodFillMap { map: HashMap, Fill>, top_left: Point2, bottom_right: Point2, } #[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> { 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> { 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, 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, 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)); } } } }