NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2022 Day 15

Advent of Code 2022 Day 17

1. Day 16: Proboscidea Volcanium
2. Parsing
3. Part 1
4. Part 2
1. Final code
5. Final code

# Advent of Code 2022 Day 16

## Day 16: Proboscidea Volcanium

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, 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>:

day_16.rs
use std::collections::{HashMap, HashSet};.css-13aqjzy{display:inline-block;}
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 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 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 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 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 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

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_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

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
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}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    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();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 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();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 valve73            if seen.insert(neighbour) {74                pq.push(Node {75                    cost: cost + 1,76                    curr: neighbour,77                });78            }79        }80    }81
82    u32::MAX83}84
85/// 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));104
105            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);110
111            acc112        })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_cost138    let flowing: HashSet<_> = map139        .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 seen155    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 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));172
173        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            }183
184            // 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);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_relieved203}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_cost208    let flowing: HashSet<_> = map209        .iter()210        .filter(|(_, valve)| valve.flow > 0)211        .map(|(&name, _)| name)212        .collect();213
214    // key: opened, val: relieved_at_end215    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 number234        max_relieved_states235            .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, 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));245
246        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            }254
255            // 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);258
259            // add opened valve to opened valves260            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_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}