Parsing for day 20

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