Advent of Code 2022 Day 16
Day 16: Proboscidea Volcanium
https://adventofcode.com/2022/day/16
The distress signal lead you into a vulcano!
It came from an other communication device just like yours. An elephant is standing beside it, it must have triggered a distress signal somehow, clever elephant.
The vulcano will erupt in 30 minutes! There’s not enough time to leave the way you came.
There appear to be a series of pressure-release valves and pipes nearby.
Each valve has a flow rate with a number for relieved pressure per minute if opened. You can use the pipes to move between valves.
You want to relieve as much pressure as you can in those 30 minutes.
Your device scans the network of valves and pipes. Today’s input is the results of that scan.
Some of the valves are blocked, and opening them does not result in relieved pressure.
An example input looks like this:
Valve AA has flow rate=0; tunnels lead to valves DD, II, BBValve BB has flow rate=13; tunnels lead to valves CC, AAValve CC has flow rate=2; tunnels lead to valves DD, BBValve DD has flow rate=20; tunnels lead to valves CC, AA, EEValve EE has flow rate=3; tunnels lead to valves FF, DDValve FF has flow rate=0; tunnels lead to valves EE, GGValve GG has flow rate=0; tunnels lead to valves FF, HHValve HH has flow rate=22; tunnel leads to valve GGValve II has flow rate=0; tunnels lead to valves AA, JJValve JJ has flow rate=21; tunnel leads to valve II
- Opening a valve takes exactly 1 minute.
- Traversing a pipe takes exactly 1 minute.
Parsing
A valve in the input can be represented by:
struct Valve {flow: u32,neighbours: HashSet<&str>,}
and each Valve
has a name.
The series of valves and pipes can be represented as a HashMap<&str, Valve>
:
use std::collections::{HashMap, HashSet};struct Valve<'a> {flow: u32,neighbours: HashSet<&'a str>,}fn parse(input: &str) -> HashMap<&str, Valve> {input.lines().map(|line| {let (valve, neighbours) = line.split_once("; ").unwrap();let valve = valve.strip_prefix("Valve ").unwrap();let (name, flow) = valve.split_once(" has flow rate=").unwrap();let flow = flow.parse().unwrap();let neighbours = neighbours.strip_prefix("tunnels lead to valves ").or_else(|| neighbours.strip_prefix("tunnel leads to valve ")).unwrap();let neighbours = neighbours.split_terminator(", ").collect();(name, Valve { flow, neighbours })}).collect()}
Part 1
The question asks what the largest amount of pressure you can release in 30 minutes is.
I want to tackle this problem in 2 parts.
- figuring out the shortest path in minutes from any flowing valve (and the start) to an other flowing valve
- figuring out the greatest relieved pressure by checking the relieved pressure when visiting every combination of those locations
That way, this problem is reduced to 2 more manageable problems.
- A bunch of shortest path problems (Hello Dijkstra my old friend)
- A travelling salesman-ish problem
let map = parse(input);let dist_map = min_distances(map); // key: (from, to), value: move_cost// simulate all possible routes, recording the max_relieved as you gomax_relieved
Helpers
A helper to calculate the shortest path from one valve to an other valve.
Edsger gave me a hammer, and I will wield it!
#[derive(PartialEq, Eq)]struct Node<'a> {cost: u32,curr: &'a str,}impl<'a> Ord for Node<'a> {fn cmp(&self, other: &Self) -> Ordering {other.cost.cmp(&self.cost)}}impl<'a> PartialOrd for Node<'a> {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))}}/// return lowest cost to move from a valve to an other valvefn min_cost(from: &str, to: &str, map: &HashMap<&str, Valve>) -> u32 {// shortest path:// Dijkstra's algorithm// nodes in the priority queue are sorted so the lowest cost gets popped firstlet mut pq = BinaryHeap::new();// prevent backtracking by keeping track of valve rooms we already sawlet mut seen = HashSet::new();pq.push(Node {cost: 0,curr: from,});seen.insert(from);while let Some(Node { cost, curr }) = pq.pop() {if curr == to {return cost;}for neighbour in map[curr].neighbours.iter() {// only insert into the pq if we did not already see the neighbour valveif seen.insert(neighbour) {pq.push(Node {cost: cost + 1,curr: neighbour,});}}}u32::MAX}
Now the helper function I wrote in the pseudocode above.
It creates a map with shortest distances:
- key:
(from_name, to_name)
- value:
move_cost
It starts by only keeping the flowing valves from the input.
- It records the shortest distance from our starting point
"AA"
to that valve. - It records the shortest distance from that flowing valve to every other flowing valve.
/// map shortest distance from "AA" to any flowing valve/// map shortest distance from any flowing valve to an otherfn min_distances<'a>(map: &'a HashMap<&str, Valve>) -> HashMap<(&'a str, &'a str), u32> {map.iter()// only keep flowing valves.filter(|(_, valve)| valve.flow > 0)// get the name of flowing valves.map(|(&name, _)| name)// iterate over every combination of 2 flowing valves.tuple_combinations()// record shortest distance between those 2// (and the dist from "AA" to a flowing valve because we start there).fold(HashMap::new(), |mut acc, (name1, name2)| {// from AA to name1acc.entry(("AA", name1)).or_insert_with(|| min_cost("AA", name1, map));// from AA to name2acc.entry(("AA", name2)).or_insert_with(|| min_cost("AA", name2, map));let dist = min_cost(name1, name2, map);// from name1 to name2acc.insert((name1, name2), dist);// from name2 to name1acc.insert((name2, name1), dist);acc})}
With that done, time for the simulation.
We represent each state in the simulation as a State
struct.
#[derive(Debug, Hash, PartialEq, Eq, Clone)]struct State<'a> {opened: BTreeSet<&'a str>,curr: &'a str,elapsed: u32,relieved: u32,}
It has information about the state a simulation is currently in:
- which valves are open (starting at an empty set)
- which room we are in (starting at
"AA"
) - how many time has elapsed (starting at
0
) - how much pressure was relieved so far (starting at
0
)
We start at:
State {curr: "AA",opened: BTreeSet::new(),elapsed: 0,relieved: 0,}
and insert that state into a queue.
Then, every iteration of the loop, we pop off a state and continue until the queue is empty.
Inside the loop:
- If all valves are open, there’s nothing more we can do but wait until the end and let all the valves relieve pressure.
- If the time limit has been met, we record how much pressure has been relieved and move on to the next state in the queue.
// if all flowing valves are opened, wait until the endif opened.len() == flowing.len() || elapsed >= 30 {let relieved_at_end = wait_until_ending(30, elapsed, relieved, &opened, &map);max_relieved = max_relieved.max(relieved_at_end);continue;}
The helper function is quite short. Given a few parameters about the state and a time limit, it returns how much pressure would be relieved when that time limit is reached.
fn wait_until_ending(max_time: u32,elapsed: u32,relieved: u32,opened: &BTreeSet<&str>,map: &HashMap<&str, Valve>,) -> u32 {let time_left = max_time - elapsed;let relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();relieved + (relieved_per_min * time_left)}
Then, for every choice of valve to open next, we potentially add a new state to the queue.
We only consider flowing valves, moving to a non-flowing one makes no sense.
We know how long it will take to move there because we have a dist_map
.
Opening that valve will take 1 additional minute.
We add the valve we just opened to the opened
for that new state.
We also know the elapsed
time for that new state now:
The time that was already elapsed + the cost to move + 1 to open the valve.
We also know the relieved
for that new state:
While we move, and open the valve, pressure releases.
If the new elapsed time would exceed (or match) the time limit.
We calculate how much pressure would be relieved by the valves that are already open using our wait_until_ending
helper and update our max_relieved
variable.
Eventually, the queue empties.
The value in max_relieved
at that time is the maximum that can possibly be relieves in that time limit.
To speed the algorithm up a bit, I added a seen
set.
That set contains items that are almost the same as a State
, but the current position doesn’t matter.
We only add a new state to the queue if we haven’t seen a state with the same valves open that’s also at the same elapsed time, and has the same amount relieved.
Final code
pub fn part_1(input: &str) -> u32 {let map = parse(input);let dist_map = min_distances(&map); // key: (from, to), value: move_costlet flowing: HashSet<_> = map.iter().filter(|(_, valve)| valve.flow > 0).map(|(&name, _)| name).collect();let mut max_relieved = 0;let mut q = VecDeque::new();let mut seen = HashSet::new();q.push_back(State {curr: "AA",opened: BTreeSet::new(),elapsed: 0,relieved: 0,});// current position doesn't matter for seenseen.insert((BTreeSet::new(), 0, 0));while let Some(State {opened,curr,elapsed,relieved,}) = q.pop_front(){// if all flowing valves are opened, wait until the endif opened.len() == flowing.len() || elapsed >= 30 {let relieved_at_end = wait_until_ending(30, elapsed, relieved, &opened, &map);max_relieved = max_relieved.max(relieved_at_end);continue;}// for every unopened valve, run simulationlet unopened = flowing.iter().filter(|name| !opened.contains(*name));for dest in unopened {// how long would moving to dest take? +1 to open the valvelet cost = dist_map[&(curr, *dest)] + 1;let new_elapsed = elapsed + cost;// if opening the dest valve would exceed the time limit, wait until the endif new_elapsed >= 30 {let relieved_at_end = wait_until_ending(30, elapsed, relieved, &opened, &map);max_relieved = max_relieved.max(relieved_at_end);continue;}// relieve pressure of opened valves while we move to dest and open itlet relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();let new_relieved = relieved + (relieved_per_min * cost);// add opened valve to opened valveslet mut new_opened = opened.clone();new_opened.insert(dest);if seen.insert((new_opened.clone(), new_elapsed, new_relieved)) {q.push_back(State {opened: new_opened,curr: dest,elapsed: new_elapsed,relieved: new_relieved,});}}}max_relieved}
Part 2
Wait a minute, that’s one smart, magical elephant.
You can teach it to open valves.
It takes you 4 minutes to teach the elephant how to open a series of valves.
After that, there are 26 minutes left and you both start opening valves.
The question asks what the largest amount of pressure is that you and an elephant working together for 26 minutes could release.
For part2, run the same simulation. Record the maximum relieved pressure per opened valve combination at the end. It doesn’t matter in wich order they were opened, only which ones were, and the maximum amount of pressure that was released at the end.
To track this, introduce a map that starts off empty before we even start the simulation.
// key: opened, val: relieved_at_endlet mut max_relieved_states: HashMap<BTreeSet<&str>, u32> = HashMap::new();
While going through the simulation (every time a state is popped off the queue). Calculate how much pressure would be released at the end with that combination of open valves. If it beats the number that already exists for a same combination, update it.
let relieved_at_end = wait_until_ending(26, elapsed, relieved, &opened, &map);// record state. only update state if it beats the `relieved_at_end` number for this combination of opened valvesmax_relieved_states.entry(opened.clone()).and_modify(|val| *val = relieved_at_end.max(*val)).or_insert(relieved_at_end);
We exited the loop and arrived at the end of the part2 function.
The elephant and the human both have to choose a path to take that results in the most relieved pressure when combined.
That means they each have to take a path that visits valves that don’t overlap! Trying to open the same valve twice is a waste of effort.
In our code that means that the set of visited valves can not have overlap, it has to be disjoint.
The path they each take for a combination of valves is the one with the most relieved pressure at the end.
We tracked those, in max_relieved_states
.
max_relieved_states.iter().tuple_combinations().filter(|(human, elephant)| human.0.is_disjoint(elephant.0)).map(|(human, elephant)| human.1 + elephant.1).max().unwrap()
Final code
pub fn part_2(input: &str) -> u32 {let map = parse(input);let dist_map = min_distances(&map); // key: (from, to), value: move_costlet flowing: HashSet<_> = map.iter().filter(|(_, valve)| valve.flow > 0).map(|(&name, _)| name).collect();// key: opened, val: relieved_at_endlet mut max_relieved_states: HashMap<BTreeSet<&str>, u32> = HashMap::new();let mut q = VecDeque::new();q.push_back(State {curr: "AA",opened: BTreeSet::new(),elapsed: 0,relieved: 0,});while let Some(State {opened,curr,elapsed,relieved,}) = q.pop_front(){let relieved_at_end = wait_until_ending(26, elapsed, relieved, &opened, &map);// record state. only update state if it beats the `relieved_at_end` numbermax_relieved_states.entry(opened.clone()).and_modify(|val| *val = relieved_at_end.max(*val)).or_insert(relieved_at_end);// if all flowing valves are opened or the timelimit was reached, skipif opened.len() == flowing.len() || elapsed >= 26 {continue;}// for every unopened valve, run simulationlet unopened = flowing.iter().filter(|name| !opened.contains(*name));for dest in unopened {// how long would moving to dest take? +1 to open the valvelet cost = dist_map[&(curr, *dest)] + 1;let new_elapsed = elapsed + cost;// if opening the dest valve would exceed the time limit, skipif new_elapsed >= 26 {continue;}// relieve pressure of opened valves while we move to dest and open itlet relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();let new_relieved = relieved + (relieved_per_min * cost);// add opened valve to opened valveslet mut new_opened = opened.clone();new_opened.insert(dest);q.push_back(State {opened: new_opened,curr: dest,elapsed: new_elapsed,relieved: new_relieved,});}}max_relieved_states.iter().tuple_combinations().filter(|(human, elephant)| human.0.is_disjoint(elephant.0)).map(|(human, elephant)| human.1 + elephant.1).max().unwrap()}
Final code
1use std::{2 cmp::Ordering,3 collections::{BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque},4};56use itertools::Itertools;78#[derive(Debug)]9struct Valve<'a> {10 flow: u32,11 neighbours: HashSet<&'a str>,12}1314fn parse(input: &str) -> HashMap<&str, Valve> {15 input16 .lines()17 .map(|line| {18 let (valve, neighbours) = line.split_once("; ").unwrap();19 let valve = valve.strip_prefix("Valve ").unwrap();20 let (name, flow) = valve.split_once(" has flow rate=").unwrap();21 let flow = flow.parse().unwrap();22 let neighbours = neighbours23 .strip_prefix("tunnels lead to valves ")24 .or_else(|| neighbours.strip_prefix("tunnel leads to valve "))25 .unwrap();26 let neighbours = neighbours.split_terminator(", ").collect();2728 (name, Valve { flow, neighbours })29 })30 .collect()31}3233#[derive(PartialEq, Eq)]34struct Node<'a> {35 cost: u32,36 curr: &'a str,37}3839impl<'a> Ord for Node<'a> {40 fn cmp(&self, other: &Self) -> Ordering {41 other.cost.cmp(&self.cost)42 }43}4445impl<'a> PartialOrd for Node<'a> {46 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {47 Some(self.cmp(other))48 }49}5051/// return lowest cost to move from a valve to an other valve52fn min_cost(from: &str, to: &str, map: &HashMap<&str, Valve>) -> u32 {53 // shortest path:54 // Dijkstra's algorithm55 // nodes in the priority queue are sorted so the lowest cost gets popped first56 let mut pq = BinaryHeap::new();57 // prevent backtracking by keeping track of valve rooms we already saw58 let mut seen = HashSet::new();5960 pq.push(Node {61 cost: 0,62 curr: from,63 });64 seen.insert(from);6566 while let Some(Node { cost, curr }) = pq.pop() {67 if curr == to {68 return cost;69 }7071 for neighbour in map[curr].neighbours.iter() {72 // only insert into the pq if we did not already see the neighbour valve73 if seen.insert(neighbour) {74 pq.push(Node {75 cost: cost + 1,76 curr: neighbour,77 });78 }79 }80 }8182 u32::MAX83}8485/// map shortest distance from "AA" to any flowing valve86/// map shortest distance from any flowing valve to an other87fn min_distances<'a>(map: &'a HashMap<&str, Valve>) -> HashMap<(&'a str, &'a str), u32> {88 map.iter()89 // only keep flowing valves90 .filter(|(_, valve)| valve.flow > 0)91 // get the name of flowing valves92 .map(|(&name, _)| name)93 // iterate over every combination of 2 flowing valves94 .tuple_combinations()95 // record shortest distance between those 296 // (and the dist from "AA" to a flowing valve because we start there)97 .fold(HashMap::new(), |mut acc, (name1, name2)| {98 // from AA to name199 acc.entry(("AA", name1))100 .or_insert_with(|| min_cost("AA", name1, map));101 // from AA to name2102 acc.entry(("AA", name2))103 .or_insert_with(|| min_cost("AA", name2, map));104105 let dist = min_cost(name1, name2, map);106 // from name1 to name2107 acc.insert((name1, name2), dist);108 // from name2 to name1109 acc.insert((name2, name1), dist);110111 acc112 })113}114115fn wait_until_ending(116 max_time: u32,117 elapsed: u32,118 relieved: u32,119 opened: &BTreeSet<&str>,120 map: &HashMap<&str, Valve>,121) -> u32 {122 let time_left = max_time - elapsed;123 let relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();124 relieved + (relieved_per_min * time_left)125}126127#[derive(Debug, Hash, PartialEq, Eq, Clone)]128struct State<'a> {129 opened: BTreeSet<&'a str>,130 curr: &'a str,131 elapsed: u32,132 relieved: u32,133}134135pub fn part_1(input: &str) -> u32 {136 let map = parse(input);137 let dist_map = min_distances(&map); // key: (from, to), value: move_cost138 let flowing: HashSet<_> = map139 .iter()140 .filter(|(_, valve)| valve.flow > 0)141 .map(|(&name, _)| name)142 .collect();143144 let mut max_relieved = 0;145 let mut q = VecDeque::new();146 let mut seen = HashSet::new();147148 q.push_back(State {149 curr: "AA",150 opened: BTreeSet::new(),151 elapsed: 0,152 relieved: 0,153 });154 // current position doesn't matter for seen155 seen.insert((BTreeSet::new(), 0, 0));156157 while let Some(State {158 opened,159 curr,160 elapsed,161 relieved,162 }) = q.pop_front()163 {164 // if all flowing valves are opened, wait until the end165 if opened.len() == flowing.len() || elapsed >= 30 {166 let relieved_at_end = wait_until_ending(30, elapsed, relieved, &opened, &map);167 max_relieved = max_relieved.max(relieved_at_end);168 continue;169 }170 // for every unopened valve, run simulation171 let unopened = flowing.iter().filter(|name| !opened.contains(*name));172173 for dest in unopened {174 // how long would moving to dest take? +1 to open the valve175 let cost = dist_map[&(curr, *dest)] + 1;176 let new_elapsed = elapsed + cost;177 // if opening the dest valve would exceed the time limit, wait until the end178 if new_elapsed >= 30 {179 let relieved_at_end = wait_until_ending(30, elapsed, relieved, &opened, &map);180 max_relieved = max_relieved.max(relieved_at_end);181 continue;182 }183184 // relieve pressure of opened valves while we move to dest and open it185 let relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();186 let new_relieved = relieved + (relieved_per_min * cost);187 // add opened valve to opened valves188 let mut new_opened = opened.clone();189 new_opened.insert(dest);190191 if seen.insert((new_opened.clone(), new_elapsed, new_relieved)) {192 q.push_back(State {193 opened: new_opened,194 curr: dest,195 elapsed: new_elapsed,196 relieved: new_relieved,197 });198 }199 }200 }201202 max_relieved203}204205pub fn part_2(input: &str) -> u32 {206 let map = parse(input);207 let dist_map = min_distances(&map); // key: (from, to), value: move_cost208 let flowing: HashSet<_> = map209 .iter()210 .filter(|(_, valve)| valve.flow > 0)211 .map(|(&name, _)| name)212 .collect();213214 // key: opened, val: relieved_at_end215 let mut max_relieved_states: HashMap<BTreeSet<&str>, u32> = HashMap::new();216217 let mut q = VecDeque::new();218 q.push_back(State {219 curr: "AA",220 opened: BTreeSet::new(),221 elapsed: 0,222 relieved: 0,223 });224225 while let Some(State {226 opened,227 curr,228 elapsed,229 relieved,230 }) = q.pop_front()231 {232 let relieved_at_end = wait_until_ending(26, elapsed, relieved, &opened, &map);233 // record state. only update state if it beats the `relieved_at_end` number234 max_relieved_states235 .entry(opened.clone())236 .and_modify(|val| *val = relieved_at_end.max(*val))237 .or_insert(relieved_at_end);238239 // if all flowing valves are opened or the timelimit was reached, skip240 if opened.len() == flowing.len() || elapsed >= 26 {241 continue;242 }243 // for every unopened valve, run simulation244 let unopened = flowing.iter().filter(|name| !opened.contains(*name));245246 for dest in unopened {247 // how long would moving to dest take? +1 to open the valve248 let cost = dist_map[&(curr, *dest)] + 1;249 let new_elapsed = elapsed + cost;250 // if opening the dest valve would exceed the time limit, skip251 if new_elapsed >= 26 {252 continue;253 }254255 // relieve pressure of opened valves while we move to dest and open it256 let relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();257 let new_relieved = relieved + (relieved_per_min * cost);258259 // add opened valve to opened valves260 let mut new_opened = opened.clone();261 new_opened.insert(dest);262263 q.push_back(State {264 opened: new_opened,265 curr: dest,266 elapsed: new_elapsed,267 relieved: new_relieved,268 });269 }270 }271272 max_relieved_states273 .iter()274 .tuple_combinations()275 .filter(|(human, elephant)| human.0.is_disjoint(elephant.0))276 .map(|(human, elephant)| human.1 + elephant.1)277 .max()278 .unwrap()279}
Series navigation for: Advent of Code 2022