Day 20 part 1

1 files changed, 147 insertions, 5 deletions

diff --git a/src/bin/day_20.rs b/src/bin/day_20.rs
index eb10864..1bce235 100644
--- a/src/bin/day_20.rs
+++ b/src/bin/day_20.rs
@@ -1,5 +1,4 @@
 use rpds::rbt_set;
-use rpds::vector;
 use rpds::vector::Vector;
 use rpds::RedBlackTreeMap;
 use rpds::RedBlackTreeSet;
@@ -43,7 +42,6 @@ fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message
 
 struct MazeBuilder {
     map: Vector<Vector<char>>,
-    portals: Vector<([char; 2], Point)>,
 }
 
 impl FromIterator<String> for MazeBuilder {
@@ -53,7 +51,6 @@ impl FromIterator<String> for MazeBuilder {
                 .into_iter()
                 .map(|line| line.chars().collect())
                 .collect(),
-            portals: Vector::new(),
         }
     }
 }
@@ -173,14 +170,159 @@ struct Maze {
     exit: Point,     // ZZ
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
 struct Point {
     x: usize,
     y: usize,
 }
 
+impl Point {
+    fn add(&self, x: isize, y: isize) -> Point {
+        Point {
+            x: (self.x as isize + x) as usize,
+            y: (self.y as isize + y) as usize,
+        }
+    }
+}
+
 impl Maze {
     fn shortest_route(&self) -> usize {
-        unimplemented!()
+        iter::successors(
+            Some((
+                rbt_set![self.entrance.clone()],
+                rbt_set![self.entrance.clone()],
+            )),
+            |(explored, locations)| {
+                Some(Maze::next_depth_states(
+                    explored.clone(),
+                    self.next_locations(locations, explored),
+                ))
+            },
+        )
+        // .inspect(|(explored, states)| eprintln!("{:?}", states))
+        .take_while(|(_explored, states)| states.size() > 0)
+        .enumerate()
+        .find(|(_i, (_explored, states))| states.iter().any(|state| *state == self.exit))
+        .unwrap()
+        .0
+    }
+
+    fn next_depth_states(
+        explored: RedBlackTreeSet<Point>,
+        locations: RedBlackTreeSet<Point>,
+    ) -> (RedBlackTreeSet<Point>, RedBlackTreeSet<Point>) {
+        (
+            locations
+                .iter()
+                .fold(explored, |acc, next| acc.insert(next.clone())),
+            locations,
+        )
+    }
+
+    fn next_locations(
+        &self,
+        locations: &RedBlackTreeSet<Point>,
+        explored: &RedBlackTreeSet<Point>,
+    ) -> RedBlackTreeSet<Point> {
+        locations
+            .iter()
+            .flat_map(|p| {
+                [(-1, 0), (1, 0), (0, -1), (0, 1)]
+                    .iter()
+                    .map(move |(dx, dy)| p.add(*dx, *dy))
+                    .chain(
+                        self.portals
+                            .iter()
+                            .filter(move |(from, _to)| p == from)
+                            .map(|(_from, to)| to)
+                            .cloned(),
+                    )
+                    .chain(
+                        self.portals
+                            .iter()
+                            .filter(move |(_to, from)| p == from)
+                            .map(|(to, _from)| to)
+                            .cloned(),
+                    )
+            })
+            .filter(|p_next| !self.walls[p_next.y][p_next.x])
+            .filter(|state| !explored.contains(state))
+            .collect()
     }
 }
+
+#[test]
+fn portal_maze_example_1() {
+    let maze: Maze = r"         A           
+         A           
+  #######.#########  
+  #######.........#  
+  #######.#######.#  
+  #######.#######.#  
+  #######.#######.#  
+  #####  B    ###.#  
+BC...##  C    ###.#  
+  ##.##       ###.#  
+  ##...DE  F  ###.#  
+  #####    G  ###.#  
+  #########.#####.#  
+DE..#######...###.#  
+  #.#########.###.#  
+FG..#########.....#  
+  ###########.#####  
+             Z       
+             Z       "
+        .split('\n')
+        .map(|s| s.to_string())
+        .collect::<MazeBuilder>()
+        .build();
+
+    assert_eq!(maze.shortest_route(), 23);
+}
+
+#[test]
+fn portal_maze_example_2() {
+    let maze: Maze = r"                   A               
+                   A               
+  #################.#############  
+  #.#...#...................#.#.#  
+  #.#.#.###.###.###.#########.#.#  
+  #.#.#.......#...#.....#.#.#...#  
+  #.#########.###.#####.#.#.###.#  
+  #.............#.#.....#.......#  
+  ###.###########.###.#####.#.#.#  
+  #.....#        A   C    #.#.#.#  
+  #######        S   P    #####.#  
+  #.#...#                 #......VT
+  #.#.#.#                 #.#####  
+  #...#.#               YN....#.#  
+  #.###.#                 #####.#  
+DI....#.#                 #.....#  
+  #####.#                 #.###.#  
+ZZ......#               QG....#..AS
+  ###.###                 #######  
+JO..#.#.#                 #.....#  
+  #.#.#.#                 ###.#.#  
+  #...#..DI             BU....#..LF
+  #####.#                 #.#####  
+YN......#               VT..#....QG
+  #.###.#                 #.###.#  
+  #.#...#                 #.....#  
+  ###.###    J L     J    #.#.###  
+  #.....#    O F     P    #.#...#  
+  #.###.#####.#.#####.#####.###.#  
+  #...#.#.#...#.....#.....#.#...#  
+  #.#####.###.###.#.#.#########.#  
+  #...#.#.....#...#.#.#.#.....#.#  
+  #.###.#####.###.###.#.#.#######  
+  #.#.........#...#.............#  
+  #########.###.###.#############  
+           B   J   C               
+           U   P   P               "
+        .split('\n')
+        .map(|s| s.to_string())
+        .collect::<MazeBuilder>()
+        .build();
+
+    assert_eq!(maze.shortest_route(), 58);
+}