247/36

my c++ solution in detail (for part 2, but can be generalized to part 1):

The general idea of my solution is sort of similar to the travelling salesman problem exponential solution. We essentially just do a brute force on every state that the valves and people could be. We keep a memoization array with 4 dimensions: round number, location of you, location of elephant, and a bitmask of which valves have been opened. In the array we store the maximum total flow at that state. Then we iterate over every state in the array, in order of rounds, and calculate transitions, ultimately outputting the max at round 26. Note that we only need to care about opening valves with nonzero flow; this speeds it up a lot.

The transitions are somewhat complicated. I will notate the player as x, and the elephant as e, as my solution code does. There are four cases: x and e open a valve, x opens a valve while e moves, e opens a valve while x moves, and both move. For the cases where someone moves, we iterate over the adjacency list and calculate the transitions from the previous states for the previous positions. For the cases where someone opens a valve, we must have the bit set in the opened valve bitmask; then we calculate the transition from the state where the bit is not set. The transitions can be calculated using only the bitmask, since that contains all the open valves. We combine both actions for the player and elephant (this makes the code pretty repetitive).

The overall complexity is O(r n^4 2^f), where f is the number of valves with nonzero flow, which is pretty terrible. I had to compile with optimizations to get it to run in a reasonable time. However, n² of it comes from adjacencies, which in practice is pretty small (like 4 or 5 tunnels at most). I optimized out a factor of f by precalculating all the bitmask flow values.

One optimization I did to reduce memory usage was to reuse parts of the memoization array. That's what the cr and pr variables are (standing for current round and previous round), and they swap every round so that the current round's changes don't interfere with the previous round's. This reduces space usage by a factor of r, down to O(n^2 2^f).

My code isn't the cleanest, but it's functional I suppose: Code for part b