1 files changed, 321 insertions, 0 deletions
diff --git a/2023/src/bin/day_10.rs b/2023/src/bin/day_10.rs
new file mode 100644
index 0000000..84d6327
--- /dev/null
+++ b/2023/src/bin/day_10.rs
@@ -0,0 +1,321 @@
+use nom::{
+    branch::alt,
+    character::complete::{char as nom_char, line_ending},
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    IResult,
+};
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_10.txt")?;
+    let parsed = Maze::parser(&input).unwrap().1;
+    dbg!(&parsed.find_furthest_point_in_loop());
+    dbg!(&parsed.count_blocks_inside_the_pipe_loop());
+
+    Ok(())
+}
+
+#[derive(Debug)]
+struct Maze(Vec<Vec<Pipe>>);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Pipe {
+    Start,
+    Nothing,
+    DownLeft,
+    DownRight,
+    DownUp,
+    LeftRight,
+    UpLeft,
+    UpRight,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+struct Point {
+    x: usize,
+    y: usize,
+}
+
+#[derive(Debug)]
+struct FloodFillMaze(Vec<Vec<Option<FloodFill>>>);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum FloodFill {
+    Outside,
+    Inside,
+    Pipe,
+}
+
+impl Maze {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(separated_list1(line_ending, many1(Pipe::parser)), Maze)(input)
+    }
+
+    fn find_furthest_point_in_loop(&self) -> usize {
+        self.measure_loop_size() / 2
+    }
+
+    fn measure_loop_size(&self) -> usize {
+        let mut position = self.find_start();
+        let mut facing = self.find_start_facing(position);
+        position = position.go(facing);
+        let mut distance = 1;
+
+        while self.at(position) != Pipe::Start {
+            let current_pipe = self.at(position);
+            facing = current_pipe.exit_facing(facing).unwrap();
+            position = position.go(facing);
+            distance += 1;
+        }
+
+        distance
+    }
+
+    fn count_blocks_inside_the_pipe_loop(&self) -> usize {
+        let mut flood_fill_maze = FloodFillMaze::init_for_maze(&self);
+
+        let start_position = self.find_start();
+
+        {
+            // fill the pipe loop
+            let mut position = start_position;
+            flood_fill_maze.fill(position, FloodFill::Pipe);
+
+            let mut facing = self.find_start_facing(position);
+            position = position.go(facing);
+
+            while self.at(position) != Pipe::Start {
+                flood_fill_maze.fill(position, FloodFill::Pipe);
+                facing = self.at(position).exit_facing(facing).unwrap();
+                position = position.go(facing);
+            }
+        }
+
+        for y in 0..self.0.len() {
+            for x in 0..self.0[y].len() {
+                if flood_fill_maze.0[y][x].is_none() {
+                    let trace_range = if y <= start_position.y {
+                        0..y
+                    } else {
+                        y + 1..self.0.len()
+                    };
+                    let mut outside = true;
+                    for trace_y in trace_range {
+                        if flood_fill_maze.0[trace_y][x] == Some(FloodFill::Pipe)
+                            && self
+                                .at(Point { x, y: trace_y })
+                                .crossed_by_vertical_hanging_right()
+                        {
+                            outside = !outside;
+                        }
+                    }
+                    flood_fill_maze.fill(
+                        Point { x, y },
+                        if outside {
+                            FloodFill::Outside
+                        } else {
+                            FloodFill::Inside
+                        },
+                    );
+                }
+            }
+        }
+
+        flood_fill_maze
+            .0
+            .iter()
+            .flat_map(|row| row.iter())
+            .filter(|x| **x == Some(FloodFill::Inside))
+            .count()
+    }
+
+    fn at(&self, p: Point) -> Pipe {
+        self.0[p.y][p.x]
+    }
+
+    fn find_start(&self) -> Point {
+        for (y, row) in self.0.iter().enumerate() {
+            for (x, pipe) in row.iter().enumerate() {
+                if *pipe == Pipe::Start {
+                    return Point { x, y };
+                }
+            }
+        }
+        panic!("No Start!");
+    }
+
+    fn find_start_facing(&self, start: Point) -> Direction {
+        if start.y > 0 && self.at(start.up()).connections().contains(&Direction::Down) {
+            Direction::Up
+        } else if start.y < self.0.len() - 1
+            && self.at(start.down()).connections().contains(&Direction::Up)
+        {
+            Direction::Down
+        } else if start.x > 0
+            && self
+                .at(start.left())
+                .connections()
+                .contains(&Direction::Right)
+        {
+            Direction::Left
+        } else if start.x < self.0[start.y].len() - 1
+            && self
+                .at(start.right())
+                .connections()
+                .contains(&Direction::Left)
+        {
+            Direction::Right
+        } else {
+            panic!()
+        }
+    }
+}
+
+impl Pipe {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        use Pipe::*;
+
+        alt((
+            value(Start, nom_char('S')),
+            value(Nothing, nom_char('.')),
+            value(DownLeft, nom_char('7')),
+            value(DownRight, nom_char('F')),
+            value(DownUp, nom_char('|')),
+            value(LeftRight, nom_char('-')),
+            value(UpLeft, nom_char('J')),
+            value(UpRight, nom_char('L')),
+        ))(input)
+    }
+
+    fn connections(&self) -> Vec<Direction> {
+        use Direction::*;
+
+        match self {
+            Pipe::Start => vec![],
+            Pipe::Nothing => vec![],
+            Pipe::DownLeft => vec![Down, Left],
+            Pipe::DownRight => vec![Down, Right],
+            Pipe::DownUp => vec![Down, Up],
+            Pipe::LeftRight => vec![Left, Right],
+            Pipe::UpLeft => vec![Up, Left],
+            Pipe::UpRight => vec![Up, Right],
+        }
+    }
+
+    fn exit_facing(&self, facing: Direction) -> Option<Direction> {
+        use Direction::*;
+
+        match self {
+            Pipe::Start => None,
+            Pipe::Nothing => None,
+            Pipe::DownLeft => match facing {
+                Up => Some(Left),
+                Right => Some(Down),
+                _ => None,
+            },
+            Pipe::DownRight => match facing {
+                Up => Some(Right),
+                Left => Some(Down),
+                _ => None,
+            },
+            Pipe::DownUp => match facing {
+                Up => Some(Up),
+                Down => Some(Down),
+                _ => None,
+            },
+            Pipe::LeftRight => match facing {
+                Left => Some(Left),
+                Right => Some(Right),
+                _ => None,
+            },
+            Pipe::UpLeft => match facing {
+                Down => Some(Left),
+                Right => Some(Up),
+                _ => None,
+            },
+            Pipe::UpRight => match facing {
+                Down => Some(Right),
+                Left => Some(Up),
+                _ => None,
+            },
+        }
+    }
+
+    fn crossed_by_vertical_hanging_right(&self) -> bool {
+        match self {
+            Pipe::Start => panic!("Undefined crossing over the start"),
+            Pipe::Nothing => false,
+            Pipe::DownLeft => false,
+            Pipe::DownRight => true,
+            Pipe::DownUp => false,
+            Pipe::LeftRight => true,
+            Pipe::UpLeft => false,
+            Pipe::UpRight => true,
+        }
+    }
+}
+
+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,
+        }
+    }
+
+    fn go(&self, facing: Direction) -> Point {
+        match facing {
+            Direction::Up => self.up(),
+            Direction::Down => self.down(),
+            Direction::Left => self.left(),
+            Direction::Right => self.right(),
+        }
+    }
+}
+
+impl FloodFillMaze {
+    fn init_for_maze(maze: &Maze) -> FloodFillMaze {
+        FloodFillMaze(
+            maze.0
+                .iter()
+                .map(|row| row.iter().map(|_| None).collect())
+                .collect(),
+        )
+    }
+
+    fn fill(&mut self, point: Point, fill: FloodFill) {
+        if self.0[point.y][point.x].is_none() {
+            self.0[point.y][point.x] = Some(fill);
+        }
+    }
+}