Day 20

2 files changed, 121 insertions, 1 deletions

diff --git a/2018/src/day20.rs b/2018/src/day20.rs
new file mode 100644
index 0000000..2f90983
--- /dev/null
+++ b/2018/src/day20.rs
@@ -0,0 +1,118 @@
+use std::io;
+use std::io::BufRead;
+use std::collections::BinaryHeap;
+use std::collections::HashMap;
+use std::collections::HashSet;
+
+type Pos = (i32, i32);
+
+fn add(a: Pos, b: Pos) -> Pos {
+    (a.0 + b.0, a.1 + b.1)
+}
+
+struct Room {
+    conn: Vec<Pos>,
+}
+
+struct Chart {
+    rooms: HashMap<Pos, Room>,
+    stk: Vec<Pos>,
+}
+
+impl Chart {
+    fn new() -> Self {
+        let mut hm = HashMap::new();
+        hm.insert((0, 0), Room { conn: vec![] });
+        Chart {
+            rooms: hm,
+            stk: vec![(0, 0)],
+        }
+    }
+
+    fn save(&mut self) {
+        self.stk.push(*self.stk.last().unwrap());
+    }
+
+    fn restore(&mut self) {
+        self.stk.pop();
+    }
+
+    fn walk(&mut self, dir: Pos) {
+        assert!(dir.0 == 0 || dir.1 == 0);
+        assert!(dir.0.abs() + dir.1.abs() == 1);
+
+        let pos = *self.stk.last().unwrap();
+        let newpos = add(pos, dir);
+        match self.rooms.get_mut(&newpos) {
+            Some(newroom) => {
+                if !newroom.conn.contains(&pos) {
+                    newroom.conn.push(pos);
+                    self.rooms.get_mut(&pos).unwrap().conn.push(newpos);
+                }
+            }
+            None => {
+                self.rooms.insert(newpos, Room { conn: vec![pos] });
+                self.rooms.get_mut(&pos).unwrap().conn.push(newpos);
+            }
+        }
+
+        *self.stk.last_mut().unwrap() = newpos;
+    }
+}
+
+fn floodfill(chart: &Chart, mincount: i32) -> (i32, i32) {
+    let mut pqu = BinaryHeap::new();
+    pqu.push((0, (0, 0)));
+
+    let mut seen = HashSet::new();
+
+    let mut highest = 0;
+    let mut count = 0;
+
+    while pqu.len() > 0 {
+        let (md, pos) = pqu.pop().unwrap();
+        let d = -md;
+        if seen.contains(&pos) {
+            continue;
+        }
+
+        seen.insert(pos);
+
+        highest = std::cmp::max(highest, d);
+        if d >= mincount {
+            count += 1;
+        }
+
+        for p2 in &chart.rooms.get(&pos).unwrap().conn {
+            if !seen.contains(p2) {
+                pqu.push((-(d+1), *p2));
+            }
+        }
+    }
+
+    (highest, count)
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let regex = reader.lines().next().unwrap().unwrap();
+
+    let mut chart = Chart::new();
+    for c in regex.chars() {
+        match c {
+            '^' => {},
+            '$' => {},
+            'N' => chart.walk((0, -1)),
+            'E' => chart.walk((1, 0)),
+            'S' => chart.walk((0, 1)),
+            'W' => chart.walk((-1, 0)),
+            '(' => chart.save(),
+            ')' => chart.restore(),
+            '|' => { chart.restore(); chart.save(); },
+            _ => panic!("Unexpected character in input"),
+        }
+    }
+
+    let (part1, part2) = floodfill(&chart, 1000);
+
+    Ok((part1.to_string(), part2.to_string()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 1c38fad..dece97e 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -24,8 +24,9 @@ mod day16;
 mod day17;
 mod day18;
 mod day19;
+mod day20;
 
-static NUM_DAYS: i32 = 19;
+static NUM_DAYS: i32 = 20;
 
 fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
@@ -48,6 +49,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
         17 => day17::main(reader),
         18 => day18::main(reader),
         19 => day19::main(reader),
+        20 => day20::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }