Day 16

2 files changed, 294 insertions, 0 deletions

diff --git a/2022/inputs/day_16.txt b/2022/inputs/day_16.txt
new file mode 100644
index 0000000..2ab3e62
--- /dev/null
+++ b/2022/inputs/day_16.txt
@@ -0,0 +1,58 @@
+Valve QZ has flow rate=0; tunnels lead to valves IR, FA
+Valve FV has flow rate=0; tunnels lead to valves AA, GZ
+Valve GZ has flow rate=0; tunnels lead to valves FV, PO
+Valve QL has flow rate=0; tunnels lead to valves MR, AA
+Valve AA has flow rate=0; tunnels lead to valves QL, GQ, EV, FV
+Valve SQ has flow rate=23; tunnel leads to valve ZG
+Valve PK has flow rate=8; tunnels lead to valves MN, GN, WF, TY, CX
+Valve GQ has flow rate=0; tunnels lead to valves AA, MT
+Valve TI has flow rate=22; tunnels lead to valves GM, CS
+Valve JU has flow rate=17; tunnels lead to valves TT, RR, UJ, JY
+Valve YD has flow rate=7; tunnels lead to valves AT, ZS, BS
+Valve YB has flow rate=0; tunnels lead to valves EA, MW
+Valve FA has flow rate=0; tunnels lead to valves QZ, JT
+Valve TN has flow rate=0; tunnels lead to valves ZS, PO
+Valve MW has flow rate=0; tunnels lead to valves YB, YL
+Valve XN has flow rate=0; tunnels lead to valves VL, VM
+Valve MN has flow rate=0; tunnels lead to valves PK, TT
+Valve IP has flow rate=9; tunnels lead to valves YC, SA, CH, PI
+Valve PD has flow rate=0; tunnels lead to valves YZ, VM
+Valve ZS has flow rate=0; tunnels lead to valves TN, YD
+Valve PC has flow rate=0; tunnels lead to valves MR, XT
+Valve VM has flow rate=13; tunnels lead to valves CX, XN, PD
+Valve PO has flow rate=4; tunnels lead to valves GZ, TN, SA, XT, BM
+Valve GN has flow rate=0; tunnels lead to valves PK, YL
+Valve YL has flow rate=5; tunnels lead to valves MT, YZ, GN, SU, MW
+Valve IR has flow rate=6; tunnels lead to valves LK, PI, BM, QZ, EV
+Valve GM has flow rate=0; tunnels lead to valves TI, RH
+Valve CS has flow rate=0; tunnels lead to valves UJ, TI
+Valve EA has flow rate=18; tunnels lead to valves VL, YB, WF, JY
+Valve LK has flow rate=0; tunnels lead to valves IR, MR
+Valve BM has flow rate=0; tunnels lead to valves IR, PO
+Valve JZ has flow rate=0; tunnels lead to valves RH, RR
+Valve SA has flow rate=0; tunnels lead to valves IP, PO
+Valve XT has flow rate=0; tunnels lead to valves PO, PC
+Valve YC has flow rate=0; tunnels lead to valves IP, IL
+Valve RH has flow rate=15; tunnels lead to valves WJ, JZ, GM
+Valve CH has flow rate=0; tunnels lead to valves IP, BS
+Valve JY has flow rate=0; tunnels lead to valves EA, JU
+Valve TY has flow rate=0; tunnels lead to valves WJ, PK
+Valve WJ has flow rate=0; tunnels lead to valves TY, RH
+Valve IL has flow rate=0; tunnels lead to valves YC, MR
+Valve BS has flow rate=0; tunnels lead to valves YD, CH
+Valve AT has flow rate=0; tunnels lead to valves YD, UX
+Valve UJ has flow rate=0; tunnels lead to valves CS, JU
+Valve VL has flow rate=0; tunnels lead to valves EA, XN
+Valve JT has flow rate=21; tunnels lead to valves ZG, FA
+Valve UX has flow rate=10; tunnel leads to valve AT
+Valve RR has flow rate=0; tunnels lead to valves JZ, JU
+Valve TT has flow rate=0; tunnels lead to valves JU, MN
+Valve MT has flow rate=0; tunnels lead to valves GQ, YL
+Valve EV has flow rate=0; tunnels lead to valves AA, IR
+Valve ZG has flow rate=0; tunnels lead to valves JT, SQ
+Valve WF has flow rate=0; tunnels lead to valves EA, PK
+Valve YZ has flow rate=0; tunnels lead to valves PD, YL
+Valve MR has flow rate=3; tunnels lead to valves LK, IL, QL, SU, PC
+Valve PI has flow rate=0; tunnels lead to valves IR, IP
+Valve CX has flow rate=0; tunnels lead to valves VM, PK
+Valve SU has flow rate=0; tunnels lead to valves YL, MR
diff --git a/2022/src/bin/day_16.rs b/2022/src/bin/day_16.rs
new file mode 100644
index 0000000..e35f04e
--- /dev/null
+++ b/2022/src/bin/day_16.rs
@@ -0,0 +1,236 @@
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::{alpha1, line_ending, u32},
+    combinator::map,
+    multi::separated_list1,
+    sequence::tuple,
+    IResult,
+};
+use std::{
+    collections::{BTreeMap, BTreeSet},
+    fs,
+};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_16.txt")?;
+    let nodes = Nodes::parser(&input).unwrap().1;
+    let mut condensed = nodes.condense();
+
+    let mut initial_open_valves = BTreeSet::new();
+    initial_open_valves.insert(0);
+
+    let initial_state = State {
+        actors: vec![Actor {
+            position: 0,
+            time_remaining: 30,
+        }],
+        open_valves: initial_open_valves.clone(),
+    };
+
+    dbg!(condensed.find_optimal_pressure_relieved(&initial_state));
+
+    let initial_state_with_elephant = State {
+        actors: vec![
+            Actor {
+                position: 0,
+                time_remaining: 26
+            };
+            2
+        ],
+        open_valves: initial_open_valves,
+    };
+    dbg!(condensed.find_optimal_pressure_relieved(&initial_state_with_elephant));
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct Nodes {
+    nodes: BTreeMap<String, Node>,
+}
+
+#[derive(Debug, Clone)]
+struct Node {
+    id: String,
+    flow_rate: u32,
+    exits: BTreeMap<String, u32>,
+}
+
+#[derive(Debug)]
+struct CondensedNodes {
+    nodes: Vec<CondensedNode>,
+    cache: BTreeMap<State, u32>,
+}
+
+#[derive(Debug, Clone)]
+struct CondensedNode {
+    flow_rate: u32,
+    exits: Vec<u32>,
+}
+
+impl Nodes {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(separated_list1(line_ending, Node::parser), |nodes| Nodes {
+            nodes: nodes
+                .into_iter()
+                .map(|node| (node.id.clone(), node))
+                .collect(),
+        })(input)
+    }
+
+    fn condense(&self) -> CondensedNodes {
+        let node_ids: Vec<String> = self
+            .nodes
+            .values()
+            .filter(|n| n.id == "AA" || n.flow_rate > 0)
+            .map(|n| n.id.clone())
+            .collect();
+
+        let mut condensed = CondensedNodes {
+            nodes: self
+                .nodes
+                .values()
+                .filter(|n| n.id == "AA" || n.flow_rate > 0)
+                .map(|n| CondensedNode {
+                    flow_rate: n.flow_rate,
+                    exits: Vec::new(),
+                })
+                .collect(),
+            cache: BTreeMap::new(),
+        };
+
+        for (id, mut node) in condensed.nodes.iter_mut().enumerate() {
+            node.exits = node_ids
+                .iter()
+                .map(|original_destination_id| {
+                    // +1 because in condensed it includes opening the valve
+                    self.find_shortest_path(&node_ids[id], &original_destination_id) + 1
+                })
+                .collect()
+        }
+
+        condensed
+    }
+
+    fn find_shortest_path(&self, from: &str, to: &str) -> u32 {
+        let mut frontier: BTreeSet<&str> = BTreeSet::new();
+        let mut explored: BTreeSet<&str> = BTreeSet::new();
+        let mut distance = 0;
+
+        explored.insert(from);
+        frontier.insert(from);
+
+        while !frontier.is_empty() {
+            let mut next_frontier: BTreeSet<&str> = BTreeSet::new();
+            distance += 1;
+
+            for frontier_point in frontier {
+                for adjacent_point in self.nodes.get(frontier_point).unwrap().exits.keys() {
+                    if adjacent_point == to {
+                        return distance;
+                    }
+                    if !explored.contains(&adjacent_point.as_ref()) {
+                        explored.insert(adjacent_point);
+                        next_frontier.insert(adjacent_point);
+                    }
+                }
+            }
+
+            frontier = next_frontier;
+        }
+        panic!("Didn't reach end");
+    }
+}
+
+impl Node {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((
+                tag("Valve "),
+                alpha1,
+                tag(" has flow rate="),
+                u32,
+                alt((
+                    tag("; tunnels lead to valves "),
+                    tag("; tunnel leads to valve "),
+                )),
+                separated_list1(tag(", "), alpha1),
+            )),
+            |(_, id, _, flow_rate, _, exits): (_, &str, _, u32, _, Vec<&str>)| Node {
+                id: id.to_owned(),
+                flow_rate,
+                exits: exits
+                    .into_iter()
+                    .map(|destination| (destination.to_owned(), 1))
+                    .collect(),
+            },
+        )(input)
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct State {
+    actors: Vec<Actor>,
+    open_valves: BTreeSet<usize>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Actor {
+    position: usize,
+    time_remaining: u32,
+}
+
+impl State {
+    fn sort_actors(&mut self) {
+        self.actors.sort()
+    }
+}
+
+impl CondensedNodes {
+    fn find_optimal_pressure_relieved(&mut self, state: &State) -> u32 {
+        let cache_value = self.cache.get(state);
+        if let Some(cache_value) = cache_value {
+            return *cache_value;
+        }
+
+        let mut computed_value = 0;
+        for (actor_i, actor) in state.actors.iter().enumerate() {
+            let exits_to_investigate: Vec<(usize, u32)> = self.nodes[actor.position]
+                .exits
+                .iter()
+                .enumerate()
+                .filter(|(destination, distance)| {
+                    !state.open_valves.contains(destination) && **distance <= actor.time_remaining
+                })
+                .map(|(destination, distance)| (destination.clone(), distance.clone()))
+                .collect();
+
+            for (destination, distance) in exits_to_investigate {
+                let mut open_valves = state.open_valves.clone();
+                open_valves.insert(destination.clone());
+                let new_actor = Actor {
+                    time_remaining: actor.time_remaining - distance,
+                    position: destination.clone(),
+                };
+                let relief_from_this_valve =
+                    self.nodes[destination].flow_rate * new_actor.time_remaining as u32;
+                let mut actors = state.actors.clone();
+                actors[actor_i] = new_actor;
+
+                let mut state_this_way = State {
+                    actors,
+                    open_valves,
+                };
+                state_this_way.sort_actors();
+
+                let recursive_relief = self.find_optimal_pressure_relieved(&state_this_way);
+                let relief = relief_from_this_valve + recursive_relief;
+                computed_value = computed_value.max(relief);
+            }
+        }
+
+        self.cache.insert(state.clone(), computed_value);
+        computed_value
+    }
+}