Small question about 2022 Day 16 walkthrough

[hrushikeshrv]

First off, thank you so much for the walkthroughs that you publish! The walkthrough for 2022 day 16 really helped me learn a new way of approaching such a problem.

I just had a small technical question. Here you say

It's clear from the problem statement that what we are dealing with is an undirected graph

My question was that wouldn't the graph given in the problem be a directed graph? Since once we follow a tunnel leading to a new valve, we can't go back to the previous valve and choose a different tunnel? I feel like that might change the solution a little bit.

[mebeim]

@hrushikeshrv thanks for the kind words :)

wouldn't the graph given in the problem be a directed graph?

Well, technically yes, but if you notice in the input:

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

For every arc X -> Y we also have Y -> X, i.e., above AA goes to DD, and if we look at DD we see it goes to AA. Yeah, they are technically two different directed arcs, but that's the same as having a single undirected arc.

[hrushikeshrv]

Oh no, my bad. I failed to notice that each valve has a tunnel leading back to where it came from. Silly mistake 😅