From a1852a921abbb2ea315b0fc908450a71b57f1018 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sun, 10 Dec 2023 14:30:55 +0200 Subject: Day 10 WIP --- 2023/src/bin/day_10.rs | 192 ++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 150 insertions(+), 42 deletions(-) (limited to '2023/src/bin') 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> { 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>>); + +#[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 + } +} -- cgit v1.2.3