diff options
Diffstat (limited to '2018/src/day20.rs')
-rw-r--r-- | 2018/src/day20.rs | 118 |
1 files changed, 118 insertions, 0 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())) +} |