use rpds::rbt_set; use rpds::vector; use rpds::vector::Vector; use rpds::RedBlackTreeMap; use rpds::RedBlackTreeSet; use std::io; use std::io::prelude::*; use std::iter; use std::iter::FromIterator; use std::process; use structopt::StructOpt; #[derive(Debug, StructOpt)] #[structopt(name = "Day 18: Many-Worlds Interpretation")] /// Finds the shortest path through a maze with keys /// /// See https://adventofcode.com/2019/day/18 for details. struct Opt {} fn main() { let stdin = io::stdin(); let _opt = Opt::from_args(); let maze: Maze = stdin .lock() .lines() .map(|x| exit_on_failed_assertion(x, "Error reading input")) .collect(); println!("{}", maze.shortest_route()); } fn exit_on_failed_assertion(data: Result, message: &str) -> A { match data { Ok(data) => data, Err(e) => { eprintln!("{}: {}", message, e); process::exit(1); } } } struct Maze { blocks: Vec>, start: BoardState, keys: KeySet, } impl FromIterator for Maze { fn from_iter>(iter: T) -> Self { Maze::from_blocks( iter.into_iter() .map(|line| line.chars().collect()) .collect(), ) } } impl Maze { fn from_blocks(blocks: Vec>) -> Maze { Maze { start: BoardState { robots: blocks .iter() .enumerate() .flat_map(|(y, line)| { line.iter() .enumerate() .filter(|(_x, ch)| **ch == '@') .map(move |(x, _ch)| Location { x, y }) }) .collect(), keys: KeySet::default(), }, keys: blocks .iter() .flat_map(|line| line.iter()) .fold(KeySet::default(), |acc, next| acc.add_key(*next)), blocks, } } fn block_at(&self, location: &Location) -> Option { self.blocks .get(location.y) .and_then(|line| line.get(location.x)) .cloned() } fn shortest_route(&self) -> usize { iter::successors( Some(( ExploredStates::default().insert(&self.start), rbt_set![self.start.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.keys == self.keys)) .unwrap() .0 } fn next_depth_states( explored: ExploredStates, locations: RedBlackTreeSet, ) -> (ExploredStates, RedBlackTreeSet) { ( locations .iter() .fold(explored, |acc, next| acc.insert(next)), locations, ) } fn next_locations( &self, locations: &RedBlackTreeSet, explored: &ExploredStates, ) -> RedBlackTreeSet { locations .iter() .flat_map(|current| { (0..current.robots.len()).flat_map(move |i_robot| { [(-1, 0), (1, 0), (0, -1), (0, 1)] .iter() .map(move |(dx, dy)| current.next(i_robot, *dx, *dy)) .map(move |(state, new_location)| { self.block_at(&new_location) .map(|c| state.with_key(c)) .unwrap_or(state) }) }) }) .filter(|state| self.is_open(state)) .filter(|state| !explored.contains(state)) .collect() } fn is_open(&self, state: &BoardState) -> bool { state.robots.iter().all(|location| { self.block_at(location) .map(|c| Maze::char_is_open(c, state.keys)) .unwrap_or(false) }) } fn char_is_open(c: char, keys: KeySet) -> bool { c != '#' && !keys.door_is_locked(c) } } #[derive(Default, Debug, Clone)] struct ExploredStates { for_key: RedBlackTreeMap, } #[derive(Default, Debug, Clone)] struct ExploredStatesForKey { robots: Vector>, } impl ExploredStates { fn insert(&self, new: &BoardState) -> ExploredStates { ExploredStates { for_key: self.for_key.insert( new.keys.clone(), self.for_key .get(&new.keys) .map(|current| ExploredStatesForKey { robots: current .robots .iter() .zip(new.robots.iter()) .map(|(current_explored, robot)| current_explored.insert(robot.clone())) .collect(), }) .unwrap_or_else(|| ExploredStatesForKey { robots: new .robots .iter() .map(|robot| RedBlackTreeSet::new().insert(robot.clone())) .collect(), }), ), } } fn contains(&self, state: &BoardState) -> bool { self.for_key .get(&state.keys) .filter(|for_key| { state .robots .iter() .zip(for_key.robots.iter()) .all(|(r_state, r_explored)| r_explored.contains(r_state)) }) .is_some() } } #[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] struct BoardState { robots: Vector, keys: KeySet, } impl BoardState { fn next(&self, i_robot: usize, dx: isize, dy: isize) -> (BoardState, Location) { ( BoardState { robots: self .robots .set(i_robot, self.robots[i_robot].next(dx, dy)) .unwrap(), ..self.clone() }, self.robots[i_robot].next(dx, dy), ) } fn with_key(&self, c: char) -> BoardState { BoardState { keys: self.keys.add_key(c), ..self.clone() } } } #[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] struct Location { x: usize, y: usize, } impl Location { fn next(&self, dx: isize, dy: isize) -> Location { Location { x: (self.x as isize + dx) as usize, y: (self.y as isize + dy) as usize, } } } #[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] struct KeySet { bitset: u32, } impl KeySet { fn add_key(self, key: char) -> KeySet { KeySet { bitset: self.bitset | KeySet::key_to_bitset(key), } } fn door_is_locked(self, door: char) -> bool { KeySet::door_to_bitset(door) & (!self.bitset) > 0 } fn key_to_bitset(key: char) -> u32 { if key.is_ascii_alphabetic() && key.is_ascii_lowercase() { 1 << (key as u8 - b'a') } else { 0 } } fn door_to_bitset(door: char) -> u32 { if door.is_ascii_alphabetic() && door.is_ascii_uppercase() { 1 << (door as u8 - b'A') } else { 0 } } } #[test] fn doors_are_locked_without_key() { assert_eq!(true, KeySet::default().door_is_locked('A')) } #[test] fn doors_are_unlocked_with_key() { assert_eq!(false, KeySet::default().add_key('a').door_is_locked('A')) } #[test] fn example_1() { let maze: Maze = r" ######### #b.A.@.a# ######### " .split('\n') .map(|s| s.to_string()) .collect(); assert_eq!(maze.shortest_route(), 8); } #[test] fn example_2() { let maze: Maze = r" ################# #i.G..c...e..H.p# ########.######## #j.A..b...f..D.o# ########@######## #k.E..a...g..B.n# ########.######## #l.F..d...h..C.m# ################# " .split('\n') .map(|s| s.to_string()) .collect(); assert_eq!(maze.shortest_route(), 136); } #[test] fn example_3() { let maze: Maze = r" ############# #DcBa.#.GhKl# #.###@#@#I### #e#d#####j#k# ###C#@#@###J# #fEbA.#.FgHi# ############# " .split('\n') .map(|s| s.to_string()) .collect(); assert_eq!(maze.shortest_route(), 32); } #[test] fn example_4() { let maze: Maze = r" ############# #g#f.D#..h#l# #F###e#E###.# #dCba@#@BcIJ# ############# #nK.L@#@G...# #M###N#H###.# #o#m..#i#jk.# ############# " .split('\n') .map(|s| s.to_string()) .collect(); assert_eq!(maze.shortest_route(), 74); }