summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authorTom Smeding <tom.smeding@gmail.com>2018-12-20 10:17:17 +0100
committerTom Smeding <tom.smeding@gmail.com>2018-12-20 10:17:17 +0100
commita091837040819f25df4f99176820e6ede0687780 (patch)
tree4a54cbd7241533bda1e2331dee46a376c4629d34 /2018/src
parent98fd03b8e235ac957112d7d661fc8de38cfaaea0 (diff)
Day 20
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day20.rs118
-rw-r--r--2018/src/main.rs4
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"))
}
}