From 7b994344a3fe38fa0e59109070be169ceeda06e1 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Thu, 26 Dec 2019 14:23:22 +0200 Subject: Day 18 part 2. This needed some optimization --- inputs/day_18_2.txt | 81 ++++++++++++++ readme.org | 6 +- src/bin/day_18.rs | 315 ++++++++++++++++++++++++++++++++++++++++------------ 3 files changed, 330 insertions(+), 72 deletions(-) create mode 100644 inputs/day_18_2.txt diff --git a/inputs/day_18_2.txt b/inputs/day_18_2.txt new file mode 100644 index 0000000..8fda759 --- /dev/null +++ b/inputs/day_18_2.txt @@ -0,0 +1,81 @@ +################################################################################# +#.............#.....#.................#.#.....#...#.......#...................#a# +#.#####.#######.#.###.#########.#####.#.#.###Y###.#.#####.#.#####.###########.#.# +#.#...#.#.....#.#..c#.........#...#.#...#...#.#...#.#.#...#.#.#...#...#...#.....# +#.#.###.#.###.#.###.#.###########.#.###.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.####### +#.#...#...#.#...#.#...#...........#.#...#.#.#...#.#.#.#.#.#.#.#...#.#.#.#.#.....# +#.#.#.#####.#####.#####.###.#######.#.###.#.#######.#.#.###.#.###.#.#.#.#.#.###.# +#.#.#.............#.#...#.#.#..e..#.....#.#...........#...#.#...#...#...#.....#.# +#.#########.#####.#.#.###.#.#.###.#####.#.###############.#T#.#.###############.# +#...#..k....#.....#.#.Z.#...#...#.....#.#.........#.#.....#.#.#.....#.L.....#...# +###.#.#.#######.###.###.#######.#####.#.#########.#.#.###.#.#.###.#.###.###.#.### +#...#.#.#.....#.#...#...#.....#.....#.#.#...#...#.#.#.#...#.#.#...#...#.#...#...# +#.###.#.#.###.#.#.###.###.###.#####.#.#.#.#.#.#.#.#.#.###.#.###.#####.#.#.#####.# +#.#...#.#.#...#.#...#.....#.#.....#.#.#.#.#...#...#.#...#.#.#...#.#...#.#.#.....# +#.###.#.#.#.###.###.#######.#.#####.#.#.#.#########.###.###.#.###.#.###.#.#.###.# +#...#.#.#.#...#...#.........#.#.....#.#.#.............#.......#...#.#...#.#...#.# +###.#.###.###.###.###.#.#####.#.#####.###############.#########.#.#.###.#.###.#.# +#.....#...#...#.J...#.#.#.....#.....#...#...........#.#...#...#.#.......#...#.#.# +#######.###.#######.#.###.#####.#######.#########.#.#.###.#.#.#########.#####.#.# +#.......#.#...#...#...#...#...#.#.......#.....O.#.#.#.#...#.#.......#...#.....#s# +#.#######.###.#.#.#####.###.#.#.#.#######.#####.#.#.#.#.###.#####.#.#.###.#####.# +#...#...#...#...#...#.#.#...#...#.......#.....#.#.#.#.#...#.#...#.#.#...#...#...# +###.#.#.#.#########.#.#.#.#######.#####.#.#####.#.###.###.#.###.###.#.#####.#.### +#.#...#.#.........#...#...#....d#.....#.#.#.....#.#...#...#.#.#...#.#.#.....#.#.# +#.#####.#######.#######.###.###.#####.#.#.#.#####.#.###.#.#.#.###.#.#.#.#####.#.# +#...#.#.......#.......#...#.#...#.....#.#.#.....#.......#.#.....#.#.#.#.#.......# +#.#.#.#######.#.#.#####.###.#.#####.###.#.#####.#############.###.#.#.#.#######.# +#.#...#.....#.#.#...#...#...#.....#...#.#.#...#.#...........#.#...#.#.#.#...#.#.# +#.###.###.#.#.#.###.#.###.#######.#####.#.###.#.#.#########.#.#.###.#.#.#.#.#.#.# +#...#.....#.#.#...#...#...#.......#.....#...#.#.#.....#...#...#...#.#.#...#.#...# +#.#.#######.#.###.#####.###.#######.#######.#.#.#####.###.#######.#.#####.#.#.### +#.#.#.....#.#.#.#.#.#...#.#.#...#...#...#...#.#.....#...#.....#...#.....#.#.#w#.# +#.#.#.###.#.#.#.#.#.#.###.#.#.#.###.#.#.#.###.#.###.###.#.###.#.###.###.###.#.#.# +#.#.#.#.#.#.#.#.#.#.#.#m..#...#...#...#.#.#...#...#...#.#...#.#.#.....#.#...#.#.# +###.#.#.#.###W#.#.#.#.#.#########.#####.#.#.#.###.#####.###.#.#.#######.#.###.#.# +#...#...#.#...#.....#.#.......#...#...#.#.#.#.#.#.....#.....#.#.........#.#.#...# +#.###.###.#.###.#####.#.###.###.###.#.#.#.#.#.#.#####.#######.###########.#.###.# +#.#...#...#.#...#.S...#...#.....#...#.#.#...#.....#.#.........#...#...#...#.....# +#.#.###.###.#####.#######.#######.###.#.#########.#.###########.#.#.#.#.###.##### +#.....#...........#.......F.......#....@#@...........f..........#...#...#.......# +################################################################################# +#.....#.#...........#.....#............@#@..........#...#.....#.M.......#.....#.# +###P#.#.#.#######.###.###.#.#######.###.#.#########.#.#.#.###.###.#####.###.#.#.# +#...#...#...#.#...#.....#.#.#.......#...#...#.........#...#.......#...#.....#.#.# +#.#.#######.#.#.###.#####.#.#.#######.#####.###############.#########.#######.#.# +#.#.#.....#.#.#.#...#...#.#.#.#.........#...#.......#...#.....#.....#.#.......#.# +#.###.###.#.#.#.#.###.#.#.#.#.###########.###.#####.#.#.#######.###.#.#.#######.# +#...#.#.#.#...#.#.#...#...#.#...........#...#...#.#...#.......#.#.#.#.#.........# +#.#.#.#.#.#.###.#.#.#####.#######.#####.###.###.#.###########.#.#.#.#.#.#######.# +#.#.#...#...#...#.#r#.....#.....#.....#.#...#.#.#.......#...#.....#.#...#.....#.# +#.#.###.#####.###.#.#######.###.#####.#.#.#.#.#.###.#####.#.#######.#.###.###.#.# +#.#...#.#...#...#.#.........#...#...#.#.#.#...#...#.#.....#.#......p#...#.#.#.#.# +###.#.#.#.#.###.#.###########.###.#.#.#.#.###.###.#.#.#####.#.###.#######.#.#.### +#...#.#.#.#...#.......#.....#.#...#...#.#...#.#...#.....#...#.#...#.K...#.#.#...# +#.#####.#.###.#######.#.###Q#.#.#######.###.#.#.#####.###.###.#.###.###.#.#.###.# +#.....#...#...#.#...#.#.#.#...#...#.....#...#.#.....#.#...#...#.#...#.#..j#.#...# +#.###.#####.###.#.#.###.#.#########.###.#.#########.###.#.#.###.#.###.#####.#.### +#...#.#.....#...#.#.B...#...#...#...#...#.#.......#.....#.#...#.#...........#.R.# +#.###.#.#######.#.#######.#.#.#.#.###.###.#.#.###.#######.###.###.#############.# +#.#...#.......#.#n....#...#.#.#...#...#.#...#...#.....#...#.#.....#..u..#.....#.# +###.#.#######.#.#####.#.###.#.#####.###.#.#####.###.###.###.###.###.###.#.###.#.# +#...#.#...#...#.....#.#.#...#...#.#...#.#...#...#...#...#...#.#.#...#...#.#...#.# +#.#####.#.#.###.#.#####.#.###.#.#.###.#.#####.#######.#####.#.###.###.###.###.#.# +#...#...#.#.#...#.......#.#...#.#...#...#.....#.......#.....#.U...#.#...#...#...# +#.#.#.###.#.#.#########.#.#####.###.###.#.#.###.#######.###########.###X#.#.###.# +#.#..l#...#.#...#.......#.....#...#...#.#.#o#...#.#.....#...#......x....#.#.#...# +#.#####C###.#.###.###########.###.#.###.#.###.###.#.###.#.#.#I#############.#.### +#.....#...#.#.#...#...#.....#.#...#.#...#.#...#.....#...#.#...#v......G.#...#..q# +###.#####.#.###.###.#.#.###.#.#.###.#.###.#.###.#####.#.#.#####.#######.#.#####.# +#.#y#...#.#...#.#...#.#...#.#...#...#...#.#.#...#.....#.#..i..#...#.....#...#...# +#.#.#.#.#.###.#.#.###.#.#.#.#####.#.###.#.#.###.#.###########H#.#.#.#####.#.#.### +#...#.#.#...#.#.....#.#.#.#.#...#.#.....#.#...#.#...........#.#.#.#g..#...#.#...# +#.###.#.###A#.#######.#.#.#.#.###.#######.###.#.#########.#.#.#.#.###.#####.###.# +#.#...#.....#.........#.#.#.#.#...#.....#...#.#.......#...#.#.#.#.#.#.#...#...#.# +###.#####################.#.#.#.#####.###.#.#.#########.###.#.###.#.#.#.#.###.#.# +#...#.......#.............#..t#.#...#...#.#.#.#.......#.#...#...#.#.#.N.#.....#.# +#.###.#####.#.#########.#######.#.#D#.#.#.#.#.#.#####.#.#.#####.#.#.###########.# +#.#...#...#..z#.#.......#.....#...#.#.#.#.#.#...#...#...#.#.#..h#.#.....#......b# +#.#.###.#.#####.#.#######.###.#####.###.#.#.#####.#.#####.#.#.###.#.###.#.####### +#.......#.......#...........#...........#.#.....E.#.........#...V.#...#.........# +################################################################################# diff --git a/readme.org b/readme.org index 936550a..e189346 100644 --- a/readme.org +++ b/readme.org @@ -18,4 +18,8 @@ program should only be pure expressions. - Using "new type" structs can be a pain. derive_more crate made most of that pain go away. - With immutable types, 'reset the machine to try again' type - constraints were handled for free. + constraints were handled for free. This made many later puzzles easier. +- The 'no statement' constraint meant that some functions ended up + nested in a way that makes it harder to name and read. +- The persistent data structures don't integrate with Rayon iterators. +- Easier to test subsets, but harder to inspect and audit runtime behaviour. diff --git a/src/bin/day_18.rs b/src/bin/day_18.rs index 71886a2..8714e4f 100644 --- a/src/bin/day_18.rs +++ b/src/bin/day_18.rs @@ -1,6 +1,8 @@ +use rayon::prelude::*; use rpds::rbt_set; use rpds::vector; use rpds::vector::Vector; +use rpds::RedBlackTreeMap; use rpds::RedBlackTreeSet; use std::io; use std::io::prelude::*; @@ -18,7 +20,7 @@ struct Opt {} fn main() { let stdin = io::stdin(); - let opt = Opt::from_args(); + let _opt = Opt::from_args(); let maze: Maze = stdin .lock() @@ -41,8 +43,8 @@ fn exit_on_failed_assertion(data: Result, message struct Maze { blocks: Vec>, - start: Location, - keys: RedBlackTreeSet, + start: BoardState, + keys: KeySet, } impl FromIterator for Maze { @@ -58,27 +60,23 @@ impl FromIterator for Maze { impl Maze { fn from_blocks(blocks: Vec>) -> Maze { Maze { - start: blocks - .iter() - .enumerate() - .filter_map(|(y, line)| { - line.iter() - .enumerate() - .find(|(x, ch)| **ch == '@') - .map(|(x, _ch)| Location { - x, - y, - keys: RedBlackTreeSet::new(), - }) - }) - .next() - .unwrap_or(Location::default()), + 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()) - .filter(|c| c.is_lowercase() && c.is_alphabetic()) - .cloned() - .collect(), + .fold(KeySet::default(), |acc, next| acc.add_key(*next)), blocks, } } @@ -92,7 +90,10 @@ impl Maze { fn shortest_route(&self) -> usize { iter::successors( - Some((rbt_set![self.start.clone()], vector![self.start.clone()])), + Some(( + ExploredStates::default().insert(&self.start), + rbt_set![self.start.clone()], + )), |(explored, locations)| { Some(Maze::next_depth_states( explored.clone(), @@ -100,69 +101,138 @@ impl Maze { )) }, ) - // .inspect(|(explored, locations)| eprintln!("{:?}", explored.size())) - .take_while(|(_explored, locations)| locations.len() > 0) + // .inspect(|(explored, states)| eprintln!("{:?}", states)) + .take_while(|(_explored, states)| states.size() > 0) .enumerate() - .find(|(_i, (_explored, locations))| { - locations.iter().any(|location| location.keys == self.keys) - }) + .find(|(_i, (_explored, states))| states.iter().any(|state| state.keys == self.keys)) .unwrap() .0 } fn next_depth_states( - explored: RedBlackTreeSet, - locations: Vector, - ) -> (RedBlackTreeSet, Vector) { + explored: ExploredStates, + locations: RedBlackTreeSet, + ) -> (ExploredStates, RedBlackTreeSet) { ( locations .iter() - .fold(explored, |acc, next| acc.insert(next.clone())), - Maze::dedup_locations(locations), + .fold(explored, |acc, next| acc.insert(next)), + locations, ) } - fn dedup_locations(locations: Vector) -> Vector { - locations.iter().fold(Vector::new(), |acc, next| { - if acc.iter().any(|loc| loc == next) { - acc - } else { - acc.push_back(next.clone()) - } - }) - } - fn next_locations( &self, - locations: &Vector, - explored: &RedBlackTreeSet, - ) -> Vector { + locations: &RedBlackTreeSet, + explored: &ExploredStates, + ) -> RedBlackTreeSet { locations .iter() .flat_map(|current| { - [(-1, 0), (1, 0), (0, -1), (0, 1)] - .iter() - .map(move |(dx, dy)| current.next(*dx, *dy)) - .map(move |location| { - self.block_at(&location) - .map(|c| location.with_key(c)) - .unwrap_or(location) - }) + (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(|location| self.is_open(location)) - .filter(|location| !explored.contains(location)) + .filter(|state| self.is_open(state)) + .filter(|state| !explored.contains(state)) .collect() } - fn is_open(&self, location: &Location) -> bool { - self.block_at(location) - .map(|c| Maze::char_is_open(c, &location.keys)) - .unwrap_or(false) + 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 char_is_open(c: char, keys: &RedBlackTreeSet) -> bool { - c != '#' - && (!c.is_uppercase() || !c.is_alphabetic() || keys.contains(&c.to_ascii_lowercase())) + fn with_key(&self, c: char) -> BoardState { + BoardState { + keys: self.keys.add_key(c), + ..self.clone() + } } } @@ -170,7 +240,6 @@ impl Maze { struct Location { x: usize, y: usize, - keys: RedBlackTreeSet, } impl Location { @@ -178,17 +247,121 @@ impl Location { Location { x: (self.x as isize + dx) as usize, y: (self.y as isize + dy) as usize, - ..self.clone() } } - fn with_key(&self, c: char) -> Location { - if c.is_lowercase() && c.is_alphabetic() { - Location { - keys: self.keys.insert(c), - ..self.clone() - } +} + +#[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 { - self.clone() + 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