diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bin/day_20.rs | 186 |
1 files changed, 186 insertions, 0 deletions
diff --git a/src/bin/day_20.rs b/src/bin/day_20.rs new file mode 100644 index 0000000..eb10864 --- /dev/null +++ b/src/bin/day_20.rs @@ -0,0 +1,186 @@ +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 20: Donut Maze")] +/// Finds the shortest path through a maze with portals. +/// +/// See https://adventofcode.com/2019/day/20 for details. +struct Opt {} + +fn main() { + let stdin = io::stdin(); + let _opt = Opt::from_args(); + + let maze = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .collect::<MazeBuilder>() + .build(); + + 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 MazeBuilder { + map: Vector<Vector<char>>, + portals: Vector<([char; 2], Point)>, +} + +impl FromIterator<String> for MazeBuilder { + fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self { + MazeBuilder { + map: iter + .into_iter() + .map(|line| line.chars().collect()) + .collect(), + portals: Vector::new(), + } + } +} + +impl MazeBuilder { + fn build(self) -> Maze { + Maze { + walls: self + .map + .iter() + .map(|line| line.iter().map(|ch| *ch != '.').collect()) + .collect(), + portals: self.grouped_portals(), + entrance: self + .all_portals() + .find(|(id, _)| *id == ['A', 'A']) + .unwrap() + .1, + exit: self + .all_portals() + .find(|(id, _)| *id == ['Z', 'Z']) + .unwrap() + .1, + } + } + + fn grouped_portals(&self) -> Vector<(Point, Point)> { + self.all_portals() + .fold( + (Vector::new(), RedBlackTreeMap::new()), + |(matched, unmatched): ( + Vector<(Point, Point)>, + RedBlackTreeMap<[char; 2], Point>, + ), + (next_id, next_p)| match unmatched.get(&next_id) { + Some(pair) => ( + matched.push_back((pair.clone(), next_p)), + unmatched.remove(&next_id), + ), + None => (matched, unmatched.insert(next_id, next_p)), + }, + ) + .0 + } + + fn all_portals(&self) -> impl Iterator<Item = ([char; 2], Point)> + '_ { + self.horizontal_trailing_portals() + .chain(self.horizontal_leading_portals()) + .chain(self.vertical_trailing_portals()) + .chain(self.vertical_leading_portals()) + } + + fn horizontal_trailing_portals(&self) -> impl Iterator<Item = ([char; 2], Point)> + '_ { + // .XX + (0..self.map.len()) + .flat_map(move |y| (0..self.map[y].len() - 2).map(move |x| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x] == '.' + && self.map[p.y][p.x + 1].is_alphabetic() + && self.map[p.y][p.x + 2].is_alphabetic() + }) + .map(move |p| ([self.map[p.y][p.x + 1], self.map[p.y][p.x + 2]], p)) + } + + fn horizontal_leading_portals(&self) -> impl Iterator<Item = ([char; 2], Point)> + '_ { + // XX. + (0..self.map.len()) + .flat_map(move |y| (0..self.map[y].len() - 2).map(move |x| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x + 2] == '.' + && self.map[p.y][p.x + 1].is_alphabetic() + && self.map[p.y][p.x].is_alphabetic() + }) + .map(move |p| { + ( + [self.map[p.y][p.x], self.map[p.y][p.x + 1]], + Point { x: p.x + 2, y: p.y }, + ) + }) + } + + fn vertical_trailing_portals(&self) -> impl Iterator<Item = ([char; 2], Point)> + '_ { + // .XX + (0..self.map[0].len()) + .flat_map(move |x| (0..self.map.len() - 2).map(move |y| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x] == '.' + && self.map[p.y + 1][p.x].is_alphabetic() + && self.map[p.y + 2][p.x].is_alphabetic() + }) + .map(move |p| ([self.map[p.y + 1][p.x], self.map[p.y + 2][p.x]], p)) + } + + fn vertical_leading_portals(&self) -> impl Iterator<Item = ([char; 2], Point)> + '_ { + // XX. + (0..self.map[0].len()) + .flat_map(move |x| (0..self.map.len() - 2).map(move |y| Point { x, y })) + .filter(move |p| { + self.map[p.y + 2][p.x] == '.' + && self.map[p.y + 1][p.x].is_alphabetic() + && self.map[p.y][p.x].is_alphabetic() + }) + .map(move |p| { + ( + [self.map[p.y][p.x], self.map[p.y + 1][p.x]], + Point { x: p.x, y: p.y + 2 }, + ) + }) + } +} + +#[derive(Debug)] +struct Maze { + walls: Vector<Vector<bool>>, + portals: Vector<(Point, Point)>, + entrance: Point, // AA + exit: Point, // ZZ +} + +#[derive(Debug, Clone)] +struct Point { + x: usize, + y: usize, +} + +impl Maze { + fn shortest_route(&self) -> usize { + unimplemented!() + } +} |