Advent of code 2022/16

Ajax Direct

global $nodes, $flows, $direct;

// Parse node relations and flow values
[$nodes, $flows] = $input->lines->reduce(function ($data, $line) {
    preg_match("/Valve ([A-Z]{2}) has flow rate=([0-9]+); tunnels? leads? to valves? ([A-Z, ]+)/", $line, $matches);
    $data[0][$matches[1]] = (array) set(explode(",", $matches[3]))->map("trim")->flip()->mapAssoc(fn ($k, $v) => [$k => 1]);
    $data[1][$matches[1]] = (int) $matches[2];
    return $data;
}, [[], []]);

// Keep only the valves that have a flow
$valves = set($flows)->filter()->keys();

// Store each shortest/direct path between usefull valves
$direct = (new Graph($nodes))->getDirectRelations(($valves->merge(["AA"])));

// ==================================================
// > PART 1
// ==================================================
$graph = (new Graph(function ($graph) use ($flows) {
    $max_flow     = max($graph->values);
    $current_flow = $graph->values[$graph->current];
    $path         = explode(";", $graph->current);
    $time         = array_shift($path);
    $valves       = $graph->valves[end($path)]->removeKeys($path);

    // Abort quickly if we can't possibly reach the max flow
    $prediction = $current_flow + $valves->map(fn ($t, $v) => max(0, ($graph->timeLimit - $time - $t)) * $flows[$v], true)->sum();
    if ($prediction < $max_flow) return [];

    // Keep only the 4 closest valves
    $valves = $valves->sort()->slice(0, 4);

    return $valves->mapAssoc(function ($valve, $dist) use ($path, $time, $graph, $flows, $current_flow) {
        // Do not visit states that we'll reach after $graph->timeLimit minutes or that are forbidden
        $state_time = ($time + $dist + 1);
        if ($state_time >= $graph->timeLimit) return [];
        if (in_array($valve, $graph->forbidden ?? [])) return [];

        $state = $state_time .";".implode(";", $path).";".$valve;
        $value = ($flows[$valve] * ($graph->timeLimit - $state_time));

        return [$state => $value];
    });
}, "highest"));

$graph->timeLimit = 30;
$graph->valves    = $direct;
$solution_1 = $graph->explore("0;AA")[1];

// ==================================================
// > PART 2 (not the "right" way, but it works for my input)
// ==================================================
$graph->timeLimit = 26;

// I explore the best possibility in 26 minutes
$me = $graph->explore("0;AA");

// The elephant expore whatever is left
$graph->forbidden = (array) set(explode(";", set($me[0])->last()))->slice(2);
$elephant = $graph->explore("0;AA");
$solution_2 = $me[1] + $elephant[1];