1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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()))
}
|
