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, } struct Chart { rooms: HashMap, stk: Vec, } 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(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())) }