From 736952eeda1f4a77705ba6fe99dd2ed59131451e Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Mon, 30 Dec 2019 22:28:29 +0200 Subject: Parsing for day 20 --- inputs/day_20.txt | 113 +++++++++++++++++++++++++++++++++ src/bin/day_20.rs | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 299 insertions(+) create mode 100644 inputs/day_20.txt create mode 100644 src/bin/day_20.rs diff --git a/inputs/day_20.txt b/inputs/day_20.txt new file mode 100644 index 0000000..09d6330 --- /dev/null +++ b/inputs/day_20.txt @@ -0,0 +1,113 @@ + K Z V U I F + Q T Y Y E E + ###################################.#####.###.###########.#####.#.##################################### + #.......#.#.............#.........#.#.......#.#.#.........#.....#...#...#...........#...#.....#.#.....# + ###.#####.###.###.###.###########.#.###.#####.#.###.#.#.#.###.###.###.#####.#######.###.#####.#.###.### + #.#...#.#.#.#.#.#.#.#.....#...........#.....#.#...#.#.#.#...#.#.#.#.....#.#.#...#.#.#...#.#.#.....#...# + #.#.###.#.#.###.###.#.#########.###.#######.#.#.#.#######.#.#.#.#.#.###.#.#.#.###.#####.#.#.#.#####.### + #.....#...#...............#.#.#.#.#.#.....#.#.#.#...#.....#.#.#.#.#...#.....#.#.#.........#...#.#...#.# + #.#######.###########.###.#.#.###.#.###.#.#.#.#.###.###.###.#.#.#.#.###.#.###.#.#.#.#######.###.###.#.# + #...#.......#...#.#...#...#...#.#.#.#...#...#.....#.#.#.#...#...#...#...#.........#.#.#.#...#.......#.# + #.#######.#.###.#.#######.###.#.#.#.#.#.###.###.#####.#####.###.#.#####.#####.#.#.###.#.###.#.#######.# + #.#.#...#.#...#.......#.......#.#...#.#...#.#.#...#.#.......#...#.#.........#.#.#...............#.....# + #.#.#.#######.#####.#####.###.#.###.#.#####.#.#.###.#####.###.#####.###.###########.###############.### + #.#...#...#.......#...#...#.#.......#.....#.#.....#.#.......#.#...#.#.#.#.......#.......#...#...#.#...# + #.###.###.#####.#.###.#####.#####.#.###.#######.#.#.#######.#.#.#####.#.#.###########.#####.###.#.#.### + #.#.#.#...#...#.#.#...#.#.#.#.#.#.#.#...#.......#.#.#.#.....#.....#...............#...#.#...#.........# + #.#.#.#.#####.#.#####.#.#.#.#.#.###.#.#####.###.###.#.#####.#.#######.#.#######.#######.#.#.###.#####.# + #.......#.#.#...#.#...............#.#...#.#.#.......#...#...#.......#.#.#.#.#...#.#.....#.#.#...#.#...# + #.#######.#.###.#.#.###.#.#.#.###.#.###.#.###.#.###.#.###.#.#.#.#######.#.#.#####.#.#######.#.###.###.# + #.#.#.#.#.#.......#.#.#.#.#.#.#.#.#.#...#...#.#.#.#.#.....#.#.#.#.#.#...#.......#.#.#.#...#.#.#...#.#.# + #.#.#.#.#.#####.#####.#.#####.#.#.#.#.###.#.#.###.#####.#####.#.#.#.#.#####.#.###.#.#.#.###.#.###.#.### + #.#.#.#.#.#.....#.#.....#.......#.#.#.#...#.#...#...#.......#.#.#.#.........#.#...#.......#.#.#.#.#.#.# + #.#.#.#.#.#.###.#.#.#####.###.#.#.#.#.#.###.#.###.#.###.#######.#.#.###.###.#####.#.#.#.###.#.#.#.#.#.# + #.......#.#.#.#.#.#.#...#.#.#.#.#...#...#...#...#.#.#.....#.#...#...#...#.......#...#.#...#.#.#.#...#.# + #####.###.#.#.###.#####.###.###.###.#####.#####.#.#.#.#####.#.#.#####.#######.#####.#######.#.#.#.###.# + #.#...#.........#...#.#.......#...#...#.....#...#.#.#.....#...#.#...........#.#.#.#...#.#.........#...# + #.###.#.#.#######.#.#.#.#########.#########.#.###.#.#.#.###.#.#########.###.###.#.#.###.###.#######.### + #.#.....#...#...#.#...#.....#.......#.......#.....#.#.#...#.#.....#.....#.....#...#.#...#.........#...# + #.###.#.#.#####.###.###.#######.#####.#############.#.#########.###.###########.###.#.#.#.###.#.###.#.# + #...#.#.#.#.#...#.#.#.....# U N Q W Z N #.......#.#...#...#...#.#.# + ###.###.###.###.#.#.###.### Y D P L W J #####.#########.#######.### + #.#.#.#.#...#...#.#...#.#.# #.....#...#...........#.#.# + #.#.#.#.###.###.#.#.###.#.# ###.#.###.###.###.#####.#.# + #...................#.#...# #.#.#.........#...#........CB + #.###.#######.#.###.#.#.#.# #.#.#.###.#####.###.#.#.#.# + #.#.........#.#...#.....#.# #...#.#.....#...#...#.#.#..AA + #######.#######.###.#####.# #.#######.#.###.#.#.###.### + #.....#.......#...#...#...# QJ..#.#...#.#.#.#...#...#.#.# + ###.#.#.###.###########.### ###.#.#######.###########.# +YG....#.....#.#.......#......TY #.........#...........#...# + #.#.#.###########.#.#.##### #.#####.###.#########.#.#.# + #.#.#.#...#...#...#.#.#...# CB..#.#.......#.#.#.#.....#..DN + #######.#####.#.#.#####.### ###.#########.#.#.######### + #.....#...#...#.#.#...#.#.# #...#.........#...#.......# + #.###.#.#.#.#.#.#.#.#.#.#.# ###.###.#####.#.#.#.#####.# +SP..#.....#...#...#...#......YG #.......#...#...#.#.#.....# + ########################### #.#.###.###.#.###.#.#.##### +NJ....#.................#.#.# KQ..#.#.......#.#...#.#.....# + #.#.#.#####.#.#.#####.#.#.# ###.###.###.###.#.#.###.#.# + #.#.#.....#.#.#.#.....#...# #.#...#.#.#.#.#.#.....#.#..IT + ###.#####.###.#####.#####.# #.#.#####.###.############# + #.#.....#...#.....#........WE IE..#.#.#.#...............#.# + #.#.#.#.#.#########.#.###.# #.#.#.#.#.###.###.###.###.# + #...#.#...#.#.#.#...#.#...# #.#.#...#.#.#...#.#...#.#.# + #.#######.#.#.#.#####.##### #.#####.#.#.#.#.#####.#.#.# + #.#.....#.#.........#.#...# #...........#.#.#.#...#....QJ + #######.###.#.#.###.#####.# #######.#.#######.#.#.###.# + #.#.....#...#.#.#.........# #.....#.#.#...#.#...#.....# + #.###.#.#.#######.#.#####.# ###.#########.#.########### +YV..#...#.#...#.#.#.#.#.....# #.......#.........#.#.....# + #.#.###.#.#.#.#.#.###.#.### #.#####.###.#####.#.#.#.#.# + #.....#...#.#...#.#.#.#....QX #.#...#.........#.#...#.#..QP + ###.###.#######.###.###.#.# #.###.#.###.#####.#.#####.# + #.#.#.....#.....#.....#.#.# #.#.#.#.#...#.....#...#...# + #.#####.#######.###.#.##### #.#.#.#####.#.###.###.#.#.# + #.#...#.#.....#.#.#.#...#..DM FE..#.#...#.#.#.#.......#.#.# + #.#.#####.#.###.#.#.###.#.# #.#.#.#.#.###############.# + #.#.......#...#.#.....#...# #.#...#.#.#.....#.......#.# + #.#.#.#.#.###.#.#####.###.# #######.#.#.#######.#.##### +QX....#.#.#.#.............#.# #.......#.#.......#.#.....# + #####.#.#.#.#.#.########### ###.###.#.#.#.###.#.#####.# + #.#.#.#.#.#.#.#.#.........# GX..#.#.......#.#.#.......#..DM + #.#.###############.###.#.# #.#.#####.#.###.###.###.#.# + #.#.#.........#...#...#.#..CS #.....#.#.#.#.#...#.#.#.#.# + #.#.#######.#####.###.#.### #######.#.###.#.#####.##### +WE........#.#.#.#.#.#...#...# MX........#.#.........#......CS + #####.###.#.#.#.#.#.#.##### #####.###.###.#####.###.### + #...#...............#.#.#.# #.#.....#.#.......#...#...# + ###.###################.#.# #.#.###########.#.###.#.#.# + #...............#.#........ME #.#.#.#...#...#.#.#...#.#.# + #.#.#####.#####.#.#.###.#.# #.#.#####.#######.#.#####.# +GX..#...#.#.#...........#.#.# #.................#.......# + #.#.###.#######.###.#####.# J D Z V S I Y #.###.###.#.###.###.#.#.#.# + #.#.......#.......#.....#.# I N T Y P T V #...#...#.#.#.#.#.#.#.#.#.# + #.#.#.#########.#.#.#############.#########.###.#.#.#############.###.###########.###.#.#.#.#.#.#####.# + #.#.#.....#.....#.#...#.......#.....#.......#.....#.#.#.#.#...#...#.........#.....#...#.#.....#...#...# + #.#############.###.#######.#.#####.#.###.###.#####.#.#.#.###.#.#####.#.#.#####.#.#.#.#.#####.###.##### + #...........#.....#.....#...#.......#...#.#.#.....#.#.....#.#.......#.#.#...#...#.#.#.#.#.....#.#.....# + ###.#######.#######.#####.###.#######.#.###.###.#.#.#.###.#.#.#######.#############.#.#######.#.#.###.# + #.#.....#.#.#.#.......#.#.#.#...#...#.#...#...#.#.#.....#...#.......#.....#.#...#...#...#.......#.#...# + #.#.#.###.#.#.#.#.###.#.###.###.#.#.###.#.###.#.#########.#####.#.###.#.###.#.#########.#####.#####.#.# + #...#...#.....#.#.#...#...#.#...#.#...#.#.#.....#.#.#.....#...#.#.#...#.............#.....#.....#...#.# + #####.###########.#####.###.#.###.#.###.#####.#.#.#.###.#.#.#.###.#.#######.###.#########.#.#.######### + #.........#.....#.#...........#...#.#...#.#...#.#...#...#.#.#.....#.......#...#.#.....#.#.#.#.....#.#.# + ###.###.#.###.#####.#.#.#.#.#.#.###.###.#.###.#####.#.#####.#.###.###.#####.#####.#####.#####.#####.#.# + #...#.#.#.#.........#.#.#.#.#...#...#.....#.....#.......#...#.#.#.#.......#.#.#...#.....#.#.#.........# + #.#.#.#.###.###.###########.###.#.###.#.#####.#.#.#.#.#.#.#.###.###.#.###.###.###.#.#.#.#.#.#.###.#.#.# + #.#.#...#...#.....#.........#.#.#...#.#.#.#...#.#.#.#.#.#.#.......#.#...#.#.....#...#.#.#.......#.#.#.# + #.#.###.#.#.#.#.#.#####.#####.#.###.#.###.###.#####.#######.###.###.#########.###.#######.#.#.#####.#.# + #.#.#...#.#.#.#.#.#.#.#.#.......#...#...#...#...#.....#.#.....#.#.#.......#...#.....#.#.#.#.#.#.#...#.# + #.#####.#.#####.###.#.#######.#.#.#.###.###.#.#.###.###.###.#####.#.#.#####.#####.#.#.#.###.#.#.#####.# + #...#...#.#.....#.#.....#.#...#.#.#.#...#.#...#.#.......#.#.#.#.#...#...........#.#.#...#.#.#.....#.#.# + ###.###.#########.#####.#.###.#####.#.###.###.#####.#####.#.#.#.#.#######.#######.###.###.#####.#.#.### + #.....#.#.....................#...#.#.......#.#.....#.....#.....#.#...........#.....#.#.#.#.#...#.#...# + #.###.#####.#.#.#.###.#.#.#.###.###.###.#.###.#####.###.#.#.#########.###########.###.#.#.#.###.###.### + #...#...#...#.#.#.#...#.#.#.#.......#.#.#...#.....#.#...#.#.......#.#.........#.............#.........# + ###.#.#####.#############.#####.#.###.#.###.#####.#.#.###.###.#.#.#.#####.#.###.###.###.###.#.#####.### + #...#.#.#.#...#.#...#.......#...#.....#.#...#.....#...#.#.#.#.#.#...#.....#.....#.....#...#.#...#.....# + #.###.#.#.###.#.###.###.#####.#####.#####.###.#########.#.#.#####.#######.#####.###.#####.#.#.###.###.# + #.#.........#.#.........#.....#.....#.....#.........#.....#.......#...........#...#...#...#.#...#.#...# + ###################################.###.#######.#.###.###.###.#######.################################# + N J W Z Z M M T + D I L W Z X E Y 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::() + .build(); + + 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 MazeBuilder { + map: Vector>, + portals: Vector<([char; 2], Point)>, +} + +impl FromIterator for MazeBuilder { + fn from_iter>(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 + '_ { + 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 + '_ { + // .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 + '_ { + // 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 + '_ { + // .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 + '_ { + // 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>, + 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!() + } +} -- cgit v1.2.3