Day 20: Regex pathfinding

1 files changed, 121 insertions, 2 deletions

diff --git a/src/bin/day_20.rs b/src/bin/day_20.rs
index c89a8f9..b9706d5 100644
--- a/src/bin/day_20.rs
+++ b/src/bin/day_20.rs
@@ -4,15 +4,134 @@ use advent_of_code_2018::*;
 use std::error::Error;
 use std::path::PathBuf;
 
+use std::collections::{HashSet, HashMap};
+
 // cargo watch -cs "cargo run --release --bin day_20"
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+enum Dir {
+    N, S, E, W
+}
+
+#[derive(Debug)]
+struct Room {
+    doors: HashSet<Dir>
+}
+
+impl Room {
+    fn new() -> Room {
+        Room {
+            doors: HashSet::new()
+        }
+    }
+}
+
 fn main() -> Result<(), Box<Error>> {
-    let input = read_file(&PathBuf::from("inputs/20.txt"))?;
+    let input = &read_file(&PathBuf::from("inputs/20.txt"))?[0];
 
     println!("Input: {:?}", input);
 
+    let rooms = populate_rooms(input);
+    let distances = distance_map(&rooms);
 
-
+    debug!(distance_to_furthest_room(&distances));
+    debug!(distances_more_than_1000(&distances));
 
     Ok(())
 }
+
+fn populate_rooms(input: &str) -> HashMap<(i32, i32), Room> {
+    let mut rooms: HashMap<(i32, i32), Room> = HashMap::new();
+    rooms.insert((0,0), Room::new());
+
+    let mut coords = vec!((0, 0));
+
+    let mut coord_stack: Vec<(Vec<(i32, i32)>, Vec<(i32, i32)>)> = Vec::new();
+
+    for c in input.chars() {
+        coords.sort();
+        coords.dedup();
+        match c {
+            '^' | '$' => {},
+            'E' => {
+                for coord in &mut coords {
+                    rooms.get_mut(coord).unwrap().doors.insert(Dir::E);
+                    coord.0 += 1;
+                    rooms.entry(*coord).or_insert(Room::new());
+                }
+            },
+            'W' => {
+                for coord in &mut coords {
+                    rooms.get_mut(coord).unwrap().doors.insert(Dir::W);
+                    coord.0 -= 1;
+                    rooms.entry(*coord).or_insert(Room::new());
+                }
+            },
+            'N' => {
+                for coord in &mut coords {
+                    rooms.get_mut(coord).unwrap().doors.insert(Dir::N);
+                    coord.1 -= 1;
+                    rooms.entry(*coord).or_insert(Room::new());
+                }
+            },
+            'S' => {
+                for coord in &mut coords {
+                    rooms.get_mut(coord).unwrap().doors.insert(Dir::S);
+                    coord.1 += 1;
+                    rooms.entry(*coord).or_insert(Room::new());
+                }
+            },
+            '(' => {
+                coord_stack.push((coords.clone(), Vec::new()));
+            },
+            '|' => {
+                coord_stack.last_mut().unwrap().1.append(&mut coords);
+                coords = coord_stack.last().unwrap().0.clone();
+            },
+            ')' => {
+                coord_stack.last_mut().unwrap().1.append(&mut coords);
+                coords = coord_stack.pop().unwrap().1;
+            },
+            c => {
+                panic!("Unknown character {}", c);
+            }
+        }
+    }
+
+    debug!(rooms.len());
+
+    rooms
+}
+
+fn distance_map(rooms: &HashMap<(i32, i32), Room>) -> HashMap<(i32, i32), u32> {
+    let mut distances: HashMap<(i32, i32), u32> = HashMap::new();
+    distances.insert((0,0), 0);
+
+    while distances.len() < rooms.len() {
+        let current_max = *distances.values().max().unwrap();
+        let new_distances = distances.iter()
+            .filter(|(_, &d)| d == current_max)
+            .flat_map(|(&coord, _)| {
+                let room = rooms.get(&coord).unwrap();
+                room.doors.iter().map(|dir| match dir {
+                    Dir::N => (coord.0, coord.1-1),
+                    Dir::S => (coord.0, coord.1+1),
+                    Dir::W => (coord.0-1, coord.1),
+                    Dir::E => (coord.0+1, coord.1)
+                }).collect::<Vec<_>>()
+            })
+            .collect::<Vec<_>>();
+        for coord in new_distances {
+            distances.entry(coord).or_insert(current_max + 1);
+        }
+    }
+    distances
+}
+
+fn distance_to_furthest_room(distances: &HashMap<(i32, i32), u32>) -> u32 {
+    distances.values().max().unwrap().clone()
+}
+
+fn distances_more_than_1000(distances: &HashMap<(i32, i32), u32>) -> u32 {
+    distances.values().filter(|&&x| x >= 1000).count() as u32
+}