VP 39: Pressure (50 extra)

What You Need

Any computer with Python 3. You can also use an online Python environment, such as https://colab.research.google.com

Tunnels

You're managing a large network of pipes carrying a gas under pressure. You need to release that pressure.

It takes you one minute to open a single valve and one minute to follow any tunnel from one valve to another. What is the most pressure you could release in 30 minutes?

For example, suppose you had the following network:

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

All of the valves begin closed. You start at valve AA, but it must be damaged or jammed or something: its flow rate is 0, so there's no point in opening it. However, you could spend one minute moving to valve BB and another minute opening it; doing so would release pressure during the remaining 28 minutes at a flow rate of 13, a total eventual pressure release of 28 * 13 = 364. Then, you could spend your third minute moving to valve CC and your fourth minute opening it, providing an additional 26 minutes of eventual pressure release at a flow rate of 2, or 52 total pressure released by valve CC.

Paths

For now, ignore the flow rates. Starting at valve AA, you can go through tunnels to any of three valves, DD, II, or BB.

In other words, the possible paths using one tunnel are:

AA DD AA II AA BB

There are 16 possible paths using three tunnels:

AA DD CC DD AA DD CC BB AA DD AA DD AA DD AA II AA DD AA BB AA DD EE FF AA DD EE DD AA II AA DD AA II AA II AA II AA BB AA II JJ II AA BB CC DD AA BB CC BB AA BB AA DD AA BB AA II AA BB AA BB

VP 39.1: Ten Tunnels (10 pts extra)
For the tunnel network described above, how many paths are there passing through ten tunnels?
That number is the flag.

Shortest Paths

Now let's find ths shortest path from one valve to another.

For the network above, the shortest paths from AA to all the other valves are:

Shortest path from AA to AA uses 0 tunnels: AA Shortest path from AA to BB uses 1 tunnels: AA BB Shortest path from AA to CC uses 2 tunnels: AA DD CC Shortest path from AA to DD uses 1 tunnels: AA DD Shortest path from AA to EE uses 2 tunnels: AA DD EE Shortest path from AA to FF uses 3 tunnels: AA DD EE FF Shortest path from AA to GG uses 4 tunnels: AA DD EE FF GG Shortest path from AA to HH uses 5 tunnels: AA DD EE FF GG HH Shortest path from AA to II uses 1 tunnels: AA II Shortest path from AA to JJ uses 2 tunnels: AA II JJ

VP 39.2: Best Tour (10 pts extra)
For the network described above, find the shortest route that visits each valve in order, from AA through JJ. (You will need to visit some valves more than once.)
How many tunnels does that path pass through?
That number is the flag.

Simplifying the Graph

Your ultimate task is to find the best path through the tunnels to release as much pressure as possible.

The graph above contains ten vertices, AA, through JJ, but there's no reason to travel to ones with flow rate zero. The only reason to go to them is as part of a path to a valve with a nonzero flow rate.

So the graph can be simplified by eliminating them, and calculating the number of minutes it will take to travel to a valve with a nonzero flow rate and open it.

The simplified graph is shown below. The starting valve (fromID) is shown at the top, and the destination (toID) on the left side. The number shown is the number of minutes required to travel from the fromID to the toID, plus one minute to open that valve.

Hops: fromID toID AA BB CC DD EE HH JJ BB 2 -- 2 3 4 7 4 CC 3 2 -- 2 3 6 5 DD 2 3 2 -- 2 5 4 EE 3 4 3 2 -- 4 5 HH 6 7 6 5 4 -- 8 JJ 3 4 5 4 5 8 --

Summing all the minute values in that table produces a total of 147.

VP 39.3: Simplified Graph (10 pts extra)
Use this data:
https://samsclass.info/COMSC132/proj/VP39
Create the simplified graph, as shown above. Add up all the minute values.
That number is the flag.

Pressure Relief

Now let's consider the real problem: releasing pressure from the pipes.

Clearly, the best procedure is this:

Race to a closed valve with a nonzero flow rate, using the shortest path, and open it.
Race to another closed valve with a nonzero flow rate, using the shortest path, and open it.
Repeat until time runs out, or all the valves are open.

The only relevant decision is what order to visit the closed valves in.

Enumerate all possible orders, and evaluate the total pressure loss for each valve order.

For the example network above, there are 6 valves with nonzero flow rate and 720 possible valve orders. The best route is:

AA DD BB JJ HH EE CC

== Minute 1 == No valves are open. You move to valve DD. == Minute 2 == No valves are open. You open valve DD. == Minute 3 == Valve DD is open, releasing 20 pressure. You move to valve CC. == Minute 4 == Valve DD is open, releasing 20 pressure. You move to valve BB. == Minute 5 == Valve DD is open, releasing 20 pressure. You open valve BB. == Minute 6 == Valves BB and DD are open, releasing 33 pressure. You move to valve AA. == Minute 7 == Valves BB and DD are open, releasing 33 pressure. You move to valve II. == Minute 8 == Valves BB and DD are open, releasing 33 pressure. You move to valve JJ. == Minute 9 == Valves BB and DD are open, releasing 33 pressure. You open valve JJ. == Minute 10 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve II. == Minute 11 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve AA. == Minute 12 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve DD. == Minute 13 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve EE. == Minute 14 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve FF. == Minute 15 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve GG. == Minute 16 == Valves BB, DD, and JJ are open, releasing 54 pressure. You move to valve HH. == Minute 17 == Valves BB, DD, and JJ are open, releasing 54 pressure. You open valve HH. == Minute 18 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You move to valve GG. == Minute 19 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You move to valve FF. == Minute 20 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You move to valve EE. == Minute 21 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You open valve EE. == Minute 22 == Valves BB, DD, EE, HH, and JJ are open, releasing 79 pressure. You move to valve DD. == Minute 23 == Valves BB, DD, EE, HH, and JJ are open, releasing 79 pressure. You move to valve CC. == Minute 24 == Valves BB, DD, EE, HH, and JJ are open, releasing 79 pressure. You open valve CC. == Minute 25 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. == Minute 26 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. == Minute 27 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. == Minute 28 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. == Minute 29 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. == Minute 30 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure.

This approach lets you release the most pressure possible in 30 minutes with this valve layout, 1651.

VP 39.4: Pressure Relief (10 pts extra)
Use this data:
https://samsclass.info/COMSC132/proj/VP39
Work out the steps to release the most pressure in 30 minutes. What is the most pressure you can release?
That number is the flag.
Hint: terminate each path when it has used up the 30 minutes. That prevents the number of possible paths from growing too large. When I did it, I only tested 129,402 paths.

Assistance

Would it be better to get an assistant to help you?

It would take you 4 minutes to teach your assistant how to open the right valves in the right order, leaving you with only 26 minutes to actually execute your plan. Would having two of you working together be better, even if it means having less time? (Assume that you teach the assistant before opening any valves yourself, giving you both the same full 26 minutes.)

In the example above, you could teach the assistant to help you as follows:

You : AA JJ BB CC Assistant: AA DD HH EE == Minute 1 == No valves are open. You move to valve II. The assistant moves to valve DD. == Minute 2 == No valves are open. You move to valve JJ. The assistant opens valve DD. == Minute 3 == Valve DD is open, releasing 20 pressure. You open valve JJ. The assistant moves to valve EE. == Minute 4 == Valves DD and JJ are open, releasing 41 pressure. You move to valve II. The assistant moves to valve FF. == Minute 5 == Valves DD and JJ are open, releasing 41 pressure. You move to valve AA. The assistant moves to valve GG. == Minute 6 == Valves DD and JJ are open, releasing 41 pressure. You move to valve BB. The assistant moves to valve HH. == Minute 7 == Valves DD and JJ are open, releasing 41 pressure. You open valve BB. The assistant opens valve HH. == Minute 8 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You move to valve CC. The assistant moves to valve GG. == Minute 9 == Valves BB, DD, HH, and JJ are open, releasing 76 pressure. You open valve CC. The assistant moves to valve FF. == Minute 10 == Valves BB, CC, DD, HH, and JJ are open, releasing 78 pressure. The assistant moves to valve EE. == Minute 11 == Valves BB, CC, DD, HH, and JJ are open, releasing 78 pressure. The assistant opens valve EE. (At this point, all valves are open.) == Minute 12 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. ... == Minute 20 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure. ... == Minute 26 == Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure.

With the assistant helping, after 26 minutes, the best you could do would release a total of 1707 pressure.

VP 39.5: Assistance (10 pts extra)
Use this data:
https://samsclass.info/COMSC132/proj/VP39
With you and an assistant working together for 26 minutes, what is the most pressure you could release?
That number is the flag.

Source

Adapted from the Advent of Code.

Posted 11-8-24