Oh! It's not a pyramid, it's a volcano! That makes a lot more sense.

This seems like an interesting version of a weighted graph traversal. Open valves to release pressure, with a multiplier based on number of remaining moves, starting at 30. Each move either moves to an adjacent tunnel, or opens a valve.

Starting at AA, it seems pretty reasonable to just try a breadth-first search. The number of moves may multiply greatly, but I think it'll still be reasonable. I can think of a few ways to make it more efficient, but I'll stick with a more naieve approach until I need to change.

while (!queue.empty())
{
    ActionStep curStep = queue.front(); queue.pop();
    if (states.find(curStep.toString()) != states.end()) continue;
    states.insert(curStep.toString());

    Valve v = maze[curStep.curNode];
    cout << "queue: " << queue.size() << endl;

    if (curStep.timeRemaining <= 0 || curStep.opened.size() == openable)
    {
        cout << "Finished Pressure: " << curStep.pressureReleased << endl;
        continue;
    }

    // If valve has a flowrate and hasn't been opened, open it
    if (v.flowRate > 0 && curStep.opened.find(v.name) == curStep.opened.end())
    {
        ActionStep newStep;
        newStep.curNode = curStep.curNode;
        newStep.timeRemaining = curStep.timeRemaining-1;
        newStep.pressureReleased = curStep.pressureReleased + (v.flowRate * newStep.timeRemaining);
        newStep.opened = set<string>(curStep.opened);
        newStep.opened.insert(v.name);
        queue.push(newStep);
    }

    // Visit all neighboring valves
    for (string neighbor: v.neighbors)
    {
        ActionStep newStep;
        newStep.curNode = neighbor;
        newStep.timeRemaining = curStep.timeRemaining-1;
        newStep.pressureReleased = curStep.pressureReleased;
        newStep.opened = set<string>(curStep.opened);
        queue.push(newStep);
    }
}

This seems to work... but it gets out of hand very quickly. I need a different approach.

New idea: instead of visiting neighbors directly, try to go directly to every currently unopened node, open it, then enqueue the next steps from there.....

while (!searchQueue.empty())
{
    ActionStep curStep = searchQueue.front(); searchQueue.pop();

    // Visit all unopened valves
    for (pair<string, Valve> tPair: maze)
    {
        Valve target = tPair.second;
        if (target.name == curStep.curNode) continue;
        if (target.flowRate > 0 && curStep.opened.find(target.name) == curStep.opened.end())
        {
            int dist = getDist(curStep.curNode, target.name);
            if (dist >= curStep.timeRemaining) continue;

            ActionStep newStep;
            newStep.curNode = target.name;
            newStep.timeRemaining = curStep.timeRemaining - (dist + 1);
            newStep.pressureReleased = curStep.pressureReleased + (target.flowRate * newStep.timeRemaining);
            newStep.opened = set<string>(curStep.opened);
            newStep.opened.insert(target.name);
            searchQueue.push(newStep);

            maxFlow = max(maxFlow, newStep.pressureReleased);
        }
    }
}

Much better!

(Also, word of advice - look out for hidden plurals. Some lines had a tunnel, and some had tunnels, and it took me a while to realize it. My parsing code was bugged!)

Ooooooh this is going to be awful. Simulating two valve openings simeltaneiously is going to be a... pain. My code is not up to snuff for this.

...

A quick bathroom and whiskey break, and I realized a good way to salvage this: I'm likely already solving this in a good way. I'm just not taking notes! I need to memoize all of the valve-opening possabilities. For part one, I can just take the top from this, and for part two, I need to find the combination of two of these paths that 1) Don't have any shared valves, and 2) have the highest combined value.

A little more work to add memoization, then use the result of that. Not too bad.

This ends up with 1956 steps for the sample data, and 257,797 for my full input. Yeesh. Doing a 2D iteration of that would take waaay too long. Ugh. New plan. From scratch.

I ended up going down a long path trying combinations and permutations, and I just realized that... it was all too much. It was way too complex, it was confusing, and worst of all, it ran SO. SLOW.

I have the solution running now, which is simply this:

• Record the max pressure released for any given valid set of valves
• Pair every valid set with every other valid set
• If the sets have no intersection, record!

Take the max value from the last set, and that's that!

    int maxRelease = 0;
    for (auto l: recordedSteps)
    for (auto r: recordedSteps)
    {
        vector<string> intersect(targets.size());
        vector<string> lSet = splitN(l.first, 2);
        vector<string> rSet = splitN(r.first, 2);
        auto it = set_intersection(lSet.begin(), lSet.end(), rSet.begin(), rSet.end(), intersect.begin());
        intersect.resize(it-intersect.begin());

        if (intersect.size() == 0) {
            maxRelease = max(maxRelease, l.second + r.second);
        }
    }