Day 18: part 1

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