Parsing for day 20

2 files changed, 299 insertions, 0 deletions

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::<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!()
+    }
+}