Day 10 WIP

1 files changed, 150 insertions, 42 deletions

diff --git a/2023/src/bin/day_10.rs b/2023/src/bin/day_10.rs
index e351c34..33937b8 100644
--- a/2023/src/bin/day_10.rs
+++ b/2023/src/bin/day_10.rs
@@ -11,6 +11,7 @@ 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(())
 }
@@ -44,6 +45,16 @@ struct Point {
     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)
@@ -55,58 +66,60 @@ impl Maze {
 
     fn measure_loop_size(&self) -> usize {
         let mut position = self.find_start();
-        let mut facing = if position.y > 0
-            && self
-                .at(position.up())
-                .connections()
-                .contains(&Direction::Down)
-        {
-            position = position.up();
-            Direction::Up
-        } else if position.y < self.0.len() - 1
-            && self
-                .at(position.down())
-                .connections()
-                .contains(&Direction::Up)
-        {
-            position = position.down();
-            Direction::Down
-        } else if position.x > 0
-            && self
-                .at(position.left())
-                .connections()
-                .contains(&Direction::Right)
-        {
-            position = position.left();
-            Direction::Left
-        } else if position.x < self.0[position.y].len() - 1
-            && self
-                .at(position.right())
-                .connections()
-                .contains(&Direction::Left)
-        {
-            position = position.right();
-            Direction::Right
-        } else {
-            panic!()
-        };
+        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 = match facing {
-                Direction::Up => position.up(),
-                Direction::Down => position.down(),
-                Direction::Left => position.left(),
-                Direction::Right => position.right(),
-            };
+            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);
+
+        {
+            // flood fill the pipe loop
+            let mut position = self.find_start();
+            flood_fill_maze.fill_one(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_one(position, FloodFill::Pipe);
+                facing = self.at(position).exit_facing(facing).unwrap();
+                position = position.go(facing);
+            }
+        }
+
+        let (normal, start_pipe_position) = {
+            // flood fill from the boundary until I find a pipe loop piece
+            let mut position = Point { x: 0, y: 0 };
+            let mut found_pipes = Vec::new();
+
+            while found_pipes.len() == 0 {
+                found_pipes = flood_fill_maze
+                    .fill_flood(position, FloodFill::Outside)
+                    .into_iter()
+                    .filter(|(_, p)| self.at(*p).connections().len() == 2)
+                    .collect();
+                position = position.right();
+            }
+            found_pipes[0]
+        };
+
+        // use this to identify the inner side of the pipe
+        // trace along the inner side of the pipe, floor filling inside
+        // count the number of inner fills
+        todo!()
+    }
+
     fn at(&self, p: Point) -> Pipe {
         self.0[p.y][p.x]
     }
@@ -121,6 +134,32 @@ impl Maze {
         }
         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 {
@@ -222,6 +261,75 @@ impl Point {
             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(),
+        }
+    }
 }
 
-// 6756 is too low
+impl FloodFillMaze {
+    fn init_for_maze(maze: &Maze) -> FloodFillMaze {
+        FloodFillMaze(
+            maze.0
+                .iter()
+                .map(|row| row.iter().map(|_| None).collect())
+                .collect(),
+        )
+    }
+
+    fn fill_one(&mut self, point: Point, fill: FloodFill) {
+        if self.0[point.y][point.x].is_none() {
+            self.0[point.y][point.x] = Some(fill);
+        }
+    }
+
+    /// Returns a list of touched pipes, and the direction they were touched
+    /// from.
+    fn fill_flood(&mut self, point: Point, fill: FloodFill) -> Vec<(Direction, Point)> {
+        let mut pipes = Vec::new();
+
+        if self.0[point.y][point.x].is_none() {
+            self.0[point.y][point.x] = Some(fill);
+
+            if point.y > 0 {
+                let up = point.up();
+                if self.0[up.y][up.x] == Some(FloodFill::Pipe) {
+                    pipes.push((Direction::Up, up));
+                } else {
+                    pipes.append(&mut self.fill_flood(up, fill));
+                }
+            }
+            if point.y < self.0.len() - 1 {
+                let down = point.down();
+                if self.0[down.y][down.x] == Some(FloodFill::Pipe) {
+                    pipes.push((Direction::Down, down));
+                } else {
+                    pipes.append(&mut self.fill_flood(down, fill))
+                }
+            }
+            if point.x > 0 {
+                let left = point.left();
+                if self.0[left.y][left.x] == Some(FloodFill::Pipe) {
+                    pipes.push((Direction::Left, left));
+                } else {
+                    pipes.append(&mut self.fill_flood(left, fill))
+                };
+            }
+            if point.x < self.0[point.y].len() - 1 {
+                let right = point.right();
+                if self.0[right.y][right.x] == Some(FloodFill::Pipe) {
+                    pipes.push((Direction::Right, right));
+                } else {
+                    pipes.append(&mut self.fill_flood(right, fill))
+                }
+            }
+        }
+
+        pipes
+    }
+}