diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2019-12-26 00:48:20 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2019-12-26 00:48:20 +0200 |
commit | 60528e663297142ff5adbd83bb2d41df5581251e (patch) | |
tree | 4737d79eea07c18c860954ad34bd882cb5c8a5dc /src/bin | |
parent | 65d0a677dfed91d8d08bf6961e8c418a1468566d (diff) |
Day 18: part 1
Diffstat (limited to 'src/bin')
-rw-r--r-- | src/bin/day_18.rs | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/src/bin/day_18.rs b/src/bin/day_18.rs new file mode 100644 index 0000000..71886a2 --- /dev/null +++ b/src/bin/day_18.rs @@ -0,0 +1,194 @@ +use rpds::rbt_set; +use rpds::vector; +use rpds::vector::Vector; +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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +struct Maze { + blocks: Vec<Vec<char>>, + start: Location, + keys: RedBlackTreeSet<char>, +} + +impl FromIterator<String> for Maze { + fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self { + Maze::from_blocks( + iter.into_iter() + .map(|line| line.chars().collect()) + .collect(), + ) + } +} + +impl Maze { + fn from_blocks(blocks: Vec<Vec<char>>) -> 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()), + keys: blocks + .iter() + .flat_map(|line| line.iter()) + .filter(|c| c.is_lowercase() && c.is_alphabetic()) + .cloned() + .collect(), + blocks, + } + } + + fn block_at(&self, location: &Location) -> Option<char> { + self.blocks + .get(location.y) + .and_then(|line| line.get(location.x)) + .cloned() + } + + fn shortest_route(&self) -> usize { + iter::successors( + Some((rbt_set![self.start.clone()], vector![self.start.clone()])), + |(explored, locations)| { + Some(Maze::next_depth_states( + explored.clone(), + self.next_locations(locations, explored), + )) + }, + ) + // .inspect(|(explored, locations)| eprintln!("{:?}", explored.size())) + .take_while(|(_explored, locations)| locations.len() > 0) + .enumerate() + .find(|(_i, (_explored, locations))| { + locations.iter().any(|location| location.keys == self.keys) + }) + .unwrap() + .0 + } + + fn next_depth_states( + explored: RedBlackTreeSet<Location>, + locations: Vector<Location>, + ) -> (RedBlackTreeSet<Location>, Vector<Location>) { + ( + locations + .iter() + .fold(explored, |acc, next| acc.insert(next.clone())), + Maze::dedup_locations(locations), + ) + } + + fn dedup_locations(locations: Vector<Location>) -> Vector<Location> { + 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<Location>, + explored: &RedBlackTreeSet<Location>, + ) -> Vector<Location> { + 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) + }) + }) + .filter(|location| self.is_open(location)) + .filter(|location| !explored.contains(location)) + .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 char_is_open(c: char, keys: &RedBlackTreeSet<char>) -> bool { + c != '#' + && (!c.is_uppercase() || !c.is_alphabetic() || keys.contains(&c.to_ascii_lowercase())) + } +} + +#[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Location { + x: usize, + y: usize, + keys: RedBlackTreeSet<char>, +} + +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, + ..self.clone() + } + } + fn with_key(&self, c: char) -> Location { + if c.is_lowercase() && c.is_alphabetic() { + Location { + keys: self.keys.insert(c), + ..self.clone() + } + } else { + self.clone() + } + } +} |