NickyMeulemanNime
Metadata
  • Date

  • Last update

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 15

  • Newer post

    Advent of Code 2022 Day 17

Table of contents
  1. Day 16: Proboscidea Volcanium
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Final code
  5. Final code

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:

input.txt
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve 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>:

day_16.rs
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.

  1. figuring out the shortest path in minutes from any flowing valve (and the start) to an other flowing valve
  2. 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.

  1. A bunch of shortest path problems (Hello Dijkstra my old friend)
  2. A travelling salesman-ish problem
pseudocode.rs
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 go
max_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 valve
fn 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 first
let mut pq = BinaryHeap::new();
// prevent backtracking by keeping track of valve rooms we already saw
let 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 valve
if 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 other
fn 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 name1
acc.entry(("AA", name1))
.or_insert_with(|| min_cost("AA", name1, map));
// from AA to name2
acc.entry(("AA", name2))
.or_insert_with(|| min_cost("AA", name2, map));
let dist = min_cost(name1, name2, map);
// from name1 to name2
acc.insert((name1, name2), dist);
// from name2 to name1
acc.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 end
if 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

day_16.rs
pub fn part_1(input: &str) -> u32 {
let map = parse(input);
let dist_map = min_distances(&map); // key: (from, to), value: move_cost
let 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 seen
seen.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 end
if 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 simulation
let unopened = flowing.iter().filter(|name| !opened.contains(*name));
for dest in unopened {
// how long would moving to dest take? +1 to open the valve
let cost = dist_map[&(curr, *dest)] + 1;
let new_elapsed = elapsed + cost;
// if opening the dest valve would exceed the time limit, wait until the end
if 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 it
let 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 valves
let 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_end
let 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 valves
max_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

day_16.rs
pub fn part_2(input: &str) -> u32 {
let map = parse(input);
let dist_map = min_distances(&map); // key: (from, to), value: move_cost
let flowing: HashSet<_> = map
.iter()
.filter(|(_, valve)| valve.flow > 0)
.map(|(&name, _)| name)
.collect();
// key: opened, val: relieved_at_end
let 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` number
max_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, skip
if opened.len() == flowing.len() || elapsed >= 26 {
continue;
}
// for every unopened valve, run simulation
let unopened = flowing.iter().filter(|name| !opened.contains(*name));
for dest in unopened {
// how long would moving to dest take? +1 to open the valve
let cost = dist_map[&(curr, *dest)] + 1;
let new_elapsed = elapsed + cost;
// if opening the dest valve would exceed the time limit, skip
if new_elapsed >= 26 {
continue;
}
// relieve pressure of opened valves while we move to dest and open it
let 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 valves
let 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

day_16.rs
1use std::{
2 cmp::Ordering,
3 collections::{BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque},
4};
5
6use itertools::Itertools;
7
8#[derive(Debug)]
9struct Valve<'a> {
10 flow: u32,
11 neighbours: HashSet<&'a str>,
12}
13
14fn parse(input: &str) -> HashMap<&str, Valve> {
15 input
16 .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 = neighbours
23 .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();
27
28 (name, Valve { flow, neighbours })
29 })
30 .collect()
31}
32
33#[derive(PartialEq, Eq)]
34struct Node<'a> {
35 cost: u32,
36 curr: &'a str,
37}
38
39impl<'a> Ord for Node<'a> {
40 fn cmp(&self, other: &Self) -> Ordering {
41 other.cost.cmp(&self.cost)
42 }
43}
44
45impl<'a> PartialOrd for Node<'a> {
46 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
47 Some(self.cmp(other))
48 }
49}
50
51/// return lowest cost to move from a valve to an other valve
52fn min_cost(from: &str, to: &str, map: &HashMap<&str, Valve>) -> u32 {
53 // shortest path:
54 // Dijkstra's algorithm
55 // nodes in the priority queue are sorted so the lowest cost gets popped first
56 let mut pq = BinaryHeap::new();
57 // prevent backtracking by keeping track of valve rooms we already saw
58 let mut seen = HashSet::new();
59
60 pq.push(Node {
61 cost: 0,
62 curr: from,
63 });
64 seen.insert(from);
65
66 while let Some(Node { cost, curr }) = pq.pop() {
67 if curr == to {
68 return cost;
69 }
70
71 for neighbour in map[curr].neighbours.iter() {
72 // only insert into the pq if we did not already see the neighbour valve
73 if seen.insert(neighbour) {
74 pq.push(Node {
75 cost: cost + 1,
76 curr: neighbour,
77 });
78 }
79 }
80 }
81
82 u32::MAX
83}
84
85/// map shortest distance from "AA" to any flowing valve
86/// map shortest distance from any flowing valve to an other
87fn min_distances<'a>(map: &'a HashMap<&str, Valve>) -> HashMap<(&'a str, &'a str), u32> {
88 map.iter()
89 // only keep flowing valves
90 .filter(|(_, valve)| valve.flow > 0)
91 // get the name of flowing valves
92 .map(|(&name, _)| name)
93 // iterate over every combination of 2 flowing valves
94 .tuple_combinations()
95 // record shortest distance between those 2
96 // (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 name1
99 acc.entry(("AA", name1))
100 .or_insert_with(|| min_cost("AA", name1, map));
101 // from AA to name2
102 acc.entry(("AA", name2))
103 .or_insert_with(|| min_cost("AA", name2, map));
104
105 let dist = min_cost(name1, name2, map);
106 // from name1 to name2
107 acc.insert((name1, name2), dist);
108 // from name2 to name1
109 acc.insert((name2, name1), dist);
110
111 acc
112 })
113}
114
115fn 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}
126
127#[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}
134
135pub fn part_1(input: &str) -> u32 {
136 let map = parse(input);
137 let dist_map = min_distances(&map); // key: (from, to), value: move_cost
138 let flowing: HashSet<_> = map
139 .iter()
140 .filter(|(_, valve)| valve.flow > 0)
141 .map(|(&name, _)| name)
142 .collect();
143
144 let mut max_relieved = 0;
145 let mut q = VecDeque::new();
146 let mut seen = HashSet::new();
147
148 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 seen
155 seen.insert((BTreeSet::new(), 0, 0));
156
157 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 end
165 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 simulation
171 let unopened = flowing.iter().filter(|name| !opened.contains(*name));
172
173 for dest in unopened {
174 // how long would moving to dest take? +1 to open the valve
175 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 end
178 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 }
183
184 // relieve pressure of opened valves while we move to dest and open it
185 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 valves
188 let mut new_opened = opened.clone();
189 new_opened.insert(dest);
190
191 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 }
201
202 max_relieved
203}
204
205pub fn part_2(input: &str) -> u32 {
206 let map = parse(input);
207 let dist_map = min_distances(&map); // key: (from, to), value: move_cost
208 let flowing: HashSet<_> = map
209 .iter()
210 .filter(|(_, valve)| valve.flow > 0)
211 .map(|(&name, _)| name)
212 .collect();
213
214 // key: opened, val: relieved_at_end
215 let mut max_relieved_states: HashMap<BTreeSet<&str>, u32> = HashMap::new();
216
217 let mut q = VecDeque::new();
218 q.push_back(State {
219 curr: "AA",
220 opened: BTreeSet::new(),
221 elapsed: 0,
222 relieved: 0,
223 });
224
225 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` number
234 max_relieved_states
235 .entry(opened.clone())
236 .and_modify(|val| *val = relieved_at_end.max(*val))
237 .or_insert(relieved_at_end);
238
239 // if all flowing valves are opened or the timelimit was reached, skip
240 if opened.len() == flowing.len() || elapsed >= 26 {
241 continue;
242 }
243 // for every unopened valve, run simulation
244 let unopened = flowing.iter().filter(|name| !opened.contains(*name));
245
246 for dest in unopened {
247 // how long would moving to dest take? +1 to open the valve
248 let cost = dist_map[&(curr, *dest)] + 1;
249 let new_elapsed = elapsed + cost;
250 // if opening the dest valve would exceed the time limit, skip
251 if new_elapsed >= 26 {
252 continue;
253 }
254
255 // relieve pressure of opened valves while we move to dest and open it
256 let relieved_per_min: u32 = opened.iter().map(|name| &map[name].flow).sum();
257 let new_relieved = relieved + (relieved_per_min * cost);
258
259 // add opened valve to opened valves
260 let mut new_opened = opened.clone();
261 new_opened.insert(dest);
262
263 q.push_back(State {
264 opened: new_opened,
265 curr: dest,
266 elapsed: new_elapsed,
267 relieved: new_relieved,
268 });
269 }
270 }
271
272 max_relieved_states
273 .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

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.