From 9892e3ebde304726903a1e5c358d05c2e343ea5e Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:26:36 +0200 Subject: Refile for merging repos --- 2019/src/bin/day_18.rs | 365 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 365 insertions(+) create mode 100644 2019/src/bin/day_18.rs (limited to '2019/src/bin/day_18.rs') diff --git a/2019/src/bin/day_18.rs b/2019/src/bin/day_18.rs new file mode 100644 index 0000000..255baa0 --- /dev/null +++ b/2019/src/bin/day_18.rs @@ -0,0 +1,365 @@ +use rpds::rbt_set; +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); +} -- cgit v1.2.3