diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bin/day_20.rs | 152 |
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); +} |