From a2ce5eb7f720d17aac648a5b3fd8e97df198803c Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Mon, 18 Dec 2023 19:07:20 +0200
Subject: Day 18 part 1

---
 2023/src/bin/day_18.rs | 186 ++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 177 insertions(+), 9 deletions(-)

(limited to '2023/src')

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));
+            }
+        }
     }
 }
-- 
cgit v1.2.3