day 16

5 files changed, 368 insertions, 0 deletions

diff --git a/benches/2022.rs b/benches/2022.rs
index 1bf0670..f6ebbc1 100644
--- a/benches/2022.rs
+++ b/benches/2022.rs
@@ -31,6 +31,8 @@ mod day13;
 mod day14;
 #[path = "../src/bin/2022/day15.rs"]
 mod day15;
+#[path = "../src/bin/2022/day16.rs"]
+mod day16;
 // NEXT MOD
 
 day!(2022, 1, day1);
@@ -48,6 +50,7 @@ day!(2022, 12, day12);
 day!(2022, 13, day13);
 day!(2022, 14, day14);
 day!(2022, 15, day15);
+day!(2022, 16, day16);
 // NEXT DAY
 
 fn bench_2022(c: &mut criterion::Criterion) {
@@ -68,6 +71,7 @@ fn bench_2022(c: &mut criterion::Criterion) {
             day_combined!(2022, 13, day13);
             day_combined!(2022, 14, day14);
             day_combined!(2022, 15, day15);
+            day_combined!(2022, 16, day16);
             // NEXT DAY COMBINED
         })
     });
@@ -91,5 +95,6 @@ criterion::criterion_main!(
     bench_2022day13,
     bench_2022day14,
     bench_2022day15,
+    bench_2022day16,
     // NEXT GROUP
 );
diff --git a/data/2022/16.txt b/data/2022/16.txt
new file mode 100644
index 0000000..ca73ce3
--- /dev/null
+++ b/data/2022/16.txt
@@ -0,0 +1,57 @@
+Valve ED has flow rate=0; tunnels lead to valves PS, AW
+Valve SI has flow rate=0; tunnels lead to valves AA, HX
+Valve LX has flow rate=22; tunnels lead to valves DY, YH
+Valve CR has flow rate=0; tunnels lead to valves BE, HX
+Valve BI has flow rate=0; tunnels lead to valves GC, AY
+Valve PB has flow rate=4; tunnels lead to valves IX, YG, RI, KR, BV
+Valve YY has flow rate=0; tunnels lead to valves PH, GJ
+Valve PH has flow rate=11; tunnels lead to valves YY, VE, ZG, MM
+Valve DY has flow rate=0; tunnels lead to valves LX, AW
+Valve SD has flow rate=0; tunnels lead to valves AY, EC
+Valve SV has flow rate=24; tunnels lead to valves CC, GF
+Valve RL has flow rate=0; tunnels lead to valves OW, IN
+Valve GF has flow rate=0; tunnels lead to valves RQ, SV
+Valve BE has flow rate=5; tunnels lead to valves CR, JC, MF, IT
+Valve PR has flow rate=0; tunnels lead to valves BV, GJ
+Valve AW has flow rate=21; tunnels lead to valves VE, DY, TR, ED
+Valve FY has flow rate=17; tunnels lead to valves GG, KJ
+Valve GC has flow rate=0; tunnels lead to valves BI, GJ
+Valve RI has flow rate=0; tunnels lead to valves PB, AY
+Valve RQ has flow rate=0; tunnels lead to valves HH, GF
+Valve IT has flow rate=0; tunnels lead to valves MZ, BE
+Valve XG has flow rate=0; tunnels lead to valves BL, AA
+Valve MK has flow rate=0; tunnels lead to valves HX, DV
+Valve IX has flow rate=0; tunnels lead to valves PB, JC
+Valve BV has flow rate=0; tunnels lead to valves PR, PB
+Valve TR has flow rate=0; tunnels lead to valves CD, AW
+Valve PS has flow rate=0; tunnels lead to valves ED, AY
+Valve HH has flow rate=12; tunnels lead to valves RQ, NL, ZQ
+Valve AA has flow rate=0; tunnels lead to valves KR, SI, XG, EC, ZG
+Valve FT has flow rate=0; tunnels lead to valves IN, YH
+Valve YG has flow rate=0; tunnels lead to valves PB, HX
+Valve HX has flow rate=14; tunnels lead to valves MK, ZQ, YG, SI, CR
+Valve DV has flow rate=0; tunnels lead to valves MK, QR
+Valve GJ has flow rate=3; tunnels lead to valves PR, CD, YY, GC, BL
+Valve BL has flow rate=0; tunnels lead to valves GJ, XG
+Valve CD has flow rate=0; tunnels lead to valves TR, GJ
+Valve GG has flow rate=0; tunnels lead to valves FY, NL
+Valve JC has flow rate=0; tunnels lead to valves IX, BE
+Valve JN has flow rate=0; tunnels lead to valves OW, QR
+Valve RM has flow rate=18; tunnel leads to valve KJ
+Valve NL has flow rate=0; tunnels lead to valves GG, HH
+Valve QR has flow rate=20; tunnels lead to valves CC, DV, PN, JN
+Valve ZG has flow rate=0; tunnels lead to valves AA, PH
+Valve AY has flow rate=6; tunnels lead to valves RI, PS, SD, BI, MM
+Valve VE has flow rate=0; tunnels lead to valves PH, AW
+Valve OW has flow rate=25; tunnels lead to valves MZ, RL, JN
+Valve MM has flow rate=0; tunnels lead to valves AY, PH
+Valve KJ has flow rate=0; tunnels lead to valves RM, FY
+Valve MF has flow rate=0; tunnels lead to valves BE, PN
+Valve YH has flow rate=0; tunnels lead to valves LX, FT
+Valve ZQ has flow rate=0; tunnels lead to valves HX, HH
+Valve KR has flow rate=0; tunnels lead to valves AA, PB
+Valve PN has flow rate=0; tunnels lead to valves MF, QR
+Valve CC has flow rate=0; tunnels lead to valves SV, QR
+Valve MZ has flow rate=0; tunnels lead to valves OW, IT
+Valve EC has flow rate=0; tunnels lead to valves SD, AA
+Valve IN has flow rate=16; tunnels lead to valves RL, FT
diff --git a/src/bin/2022/day16.rs b/src/bin/2022/day16.rs
new file mode 100644
index 0000000..77ab621
--- /dev/null
+++ b/src/bin/2022/day16.rs
@@ -0,0 +1,274 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+#[derive(Debug)]
+pub struct Map {
+    names: Vec<String>,
+    connectivity: Vec<Vec<usize>>,
+    paths: Vec<Vec<u64>>,
+    flow: Vec<u16>,
+    pos: usize,
+    elephant: usize,
+}
+
+impl advent_of_code::graph::Graph<usize, usize> for Map {
+    type Edges = Vec<usize>;
+
+    fn edges(&self, v: usize) -> Self::Edges {
+        self.connectivity[v].clone()
+    }
+
+    fn edge(&self, v: usize, e: usize) -> (usize, u64) {
+        (e, 1)
+    }
+}
+
+impl Map {
+    fn len(&self) -> usize {
+        self.flow.len()
+    }
+
+    fn room(&self, elephant: bool) -> &str {
+        &self.names[self.pos(elephant)]
+    }
+
+    fn can_stay(&self, elephant: bool) -> bool {
+        self.flow[self.pos(elephant)] > 0
+    }
+
+    fn done(&self) -> bool {
+        self.flow.iter().copied().all(|f| f == 0)
+    }
+
+    fn pos(&self, elephant: bool) -> usize {
+        if elephant {
+            self.elephant
+        } else {
+            self.pos
+        }
+    }
+
+    fn set_pos(&mut self, elephant: bool, pos: usize) {
+        if elephant {
+            self.elephant = pos;
+        } else {
+            self.pos = pos;
+        }
+    }
+
+    fn flow(&self, elephant: bool) -> u16 {
+        self.flow[self.pos(elephant)]
+    }
+
+    fn set_flow(&mut self, elephant: bool, flow: u16) {
+        let pos = self.pos(elephant);
+        self.flow[pos] = flow;
+    }
+
+    fn neighbors(&self, elephant: bool) -> &[usize] {
+        &self.connectivity[self.pos(elephant)]
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    let mut room_names = HashMap::new();
+    let mut connectivity = vec![];
+    let mut flow = vec![];
+    let room_idx = |s,
+                    room_names: &mut HashMap<_, _>,
+                    connectivity: &mut Vec<_>,
+                    flow: &mut Vec<_>| {
+        *room_names.entry(s).or_insert_with(|| {
+            connectivity.push(vec![]);
+            flow.push(0);
+            flow.len() - 1
+        })
+    };
+    let mut pos = None;
+    for line in parse::raw_lines(fh) {
+        let cap = regex_captures!(
+            r"Valve ([^ ]+) has flow rate=(\d+); tunnels? leads? to valves? (.*)",
+            &line
+        )
+        .ok_or_else(|| anyhow!("failed to parse"))?;
+        let node_name = cap[1].to_string();
+        let node = room_idx(
+            node_name.clone(),
+            &mut room_names,
+            &mut connectivity,
+            &mut flow,
+        );
+        if node_name == "AA" {
+            pos = Some(node);
+        }
+        flow[node] = cap[2].parse()?;
+        connectivity[node] = cap[3]
+            .split(", ")
+            .map(|s| {
+                room_idx(
+                    s.to_string(),
+                    &mut room_names,
+                    &mut connectivity,
+                    &mut flow,
+                )
+            })
+            .collect();
+    }
+    let mut names = vec![];
+    names.resize_with(flow.len(), Default::default);
+    for (name, idx) in room_names {
+        names[idx] = name;
+    }
+    let mut map = Map {
+        names,
+        connectivity,
+        paths: vec![],
+        flow,
+        pos: pos.unwrap(),
+        elephant: pos.unwrap(),
+    };
+    for i in 0..map.connectivity.len() {
+        let mut paths = vec![0; map.connectivity.len()];
+        let prevs = map.dijkstra_full(i);
+        for (from, (_, distance)) in map.dijkstra_full(i) {
+            paths[from] = distance;
+        }
+        map.paths.push(paths);
+    }
+    Ok(map)
+}
+
+pub fn part1(mut map: Map) -> Result<u64> {
+    fn step(map: &mut Map, total: u64, time: u16) -> u64 {
+        if time >= 30 || map.done() {
+            return total;
+        }
+
+        let mut max = 0;
+        if map.can_stay(false) {
+            let stay_value = map.flow(false) as u64 * (29 - time as u64);
+            let flow = map.flow(false);
+            map.set_flow(false, 0);
+            let value = step(map, total + stay_value, time + 1);
+            if value > max {
+                max = value;
+            }
+            map.set_flow(false, flow);
+        } else {
+            let pos = map.pos(false);
+            for idx in 0..map.len() {
+                if idx == pos || map.flow[idx] == 0 {
+                    continue;
+                }
+                let distance = map.paths[pos][idx];
+                map.set_pos(false, idx);
+                let value = step(map, total, time + distance as u16);
+                if value > max {
+                    max = value;
+                }
+                map.set_pos(false, pos);
+            }
+        }
+        max
+    }
+
+    Ok(step(&mut map, 0, 0))
+}
+
+pub fn part2(mut map: Map) -> Result<u64> {
+    fn step(
+        map: &mut Map,
+        elephant: bool,
+        total: u64,
+        time: u16,
+        transit: u64,
+        elephant_transit: u64,
+    ) -> u64 {
+        if time >= 26 || map.done() {
+            return total;
+        }
+
+        if elephant {
+            let elephant_transit = elephant_transit.saturating_sub(1);
+            if elephant_transit > 0 {
+                return step(
+                    map,
+                    !elephant,
+                    total,
+                    if elephant { time + 1 } else { time },
+                    transit,
+                    elephant_transit,
+                );
+            }
+        } else {
+            let transit = transit.saturating_sub(1);
+            if transit > 0 {
+                return step(
+                    map,
+                    !elephant,
+                    total,
+                    if elephant { time + 1 } else { time },
+                    transit,
+                    elephant_transit,
+                );
+            }
+        }
+
+        let mut max = 0;
+        if map.can_stay(elephant) {
+            let stay_value = map.flow(elephant) as u64 * (25 - time as u64);
+            let flow = map.flow(elephant);
+            map.set_flow(elephant, 0);
+            let value = step(
+                map,
+                !elephant,
+                total + stay_value,
+                if elephant { time + 1 } else { time },
+                transit,
+                elephant_transit,
+            );
+            if value > max {
+                max = value;
+            }
+            map.set_flow(elephant, flow);
+        } else {
+            let pos = map.pos(elephant);
+            for idx in 0..map.len() {
+                if idx == pos || map.flow[idx] == 0 {
+                    continue;
+                }
+                let distance = map.paths[pos][idx];
+                map.set_pos(elephant, idx);
+                let value = step(
+                    map,
+                    !elephant,
+                    total,
+                    if elephant { time + 1 } else { time },
+                    if elephant { transit } else { distance },
+                    if elephant { distance } else { elephant_transit },
+                );
+                if value > max {
+                    max = value;
+                }
+                map.set_pos(elephant, pos);
+            }
+        }
+        max
+    }
+
+    Ok(step(&mut map, false, 0, 0, 0, 0))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 16).unwrap()).unwrap()).unwrap(),
+        2359
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 16).unwrap()).unwrap()).unwrap(),
+        2999
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
index f295b53..dff9ae4 100644
--- a/src/bin/2022/main.rs
+++ b/src/bin/2022/main.rs
@@ -26,6 +26,7 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
 // NEXT MOD
 
 #[paw::main]
@@ -47,6 +48,7 @@ fn main(opt: Opt) -> Result<()> {
         13 => advent_of_code::day!(2022, opt.day, opt.puzzle, day13),
         14 => advent_of_code::day!(2022, opt.day, opt.puzzle, day14),
         15 => advent_of_code::day!(2022, opt.day, opt.puzzle, day15),
+        16 => advent_of_code::day!(2022, opt.day, opt.puzzle, day16),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }
diff --git a/src/graph.rs b/src/graph.rs
index 9312e7c..f8fbf3c 100644
--- a/src/graph.rs
+++ b/src/graph.rs
@@ -9,6 +9,36 @@ where
     fn edges(&self, v: Vertex) -> Self::Edges;
     fn edge(&self, v: Vertex, e: Edge) -> (Vertex, u64);
 
+    fn dijkstra_full(&self, start: Vertex) -> HashMap<Vertex, (Vertex, u64)> {
+        let mut to_visit = priority_queue::PriorityQueue::new();
+        let mut prev = HashMap::new();
+        prev.insert(start, (start, 0));
+        to_visit.push(start, std::cmp::Reverse(0));
+        while let Some((v, std::cmp::Reverse(distance))) = to_visit.pop() {
+            for e in self.edges(v) {
+                let (next, weight) = self.edge(v, e);
+                let visited = prev.contains_key(&next);
+                let new_distance = distance + weight;
+                if to_visit.get(&next).is_some() {
+                    prev.insert(next, (v, new_distance));
+                    if new_distance < to_visit.get_priority(&next).unwrap().0
+                    {
+                        to_visit.change_priority(
+                            &next,
+                            std::cmp::Reverse(new_distance),
+                        );
+                    }
+                } else {
+                    if !visited {
+                        prev.insert(next, (v, new_distance));
+                        to_visit.push(next, std::cmp::Reverse(new_distance));
+                    }
+                }
+            }
+        }
+        prev
+    }
+
     fn dijkstra<F: Fn(Vertex) -> bool>(
         &self,
         start: Vertex,