Advent of code 2019/18

Ajax Direct

/**
 * Simplify the grid into direct relations between keys
 * with their shortest distance and the doors in between
 */
function simplify($grid) {
    // Find all the keys and their positions
    $keys = $grid->reduce(function ($carry, $cell, $xy) {
        if ($cell >= "a" && $cell <= "z" || $cell == "@")
            $carry["$xy[0];$xy[1]"] = $cell;
        return $carry;
    }, set());

    // Define graph : go to neighbors, but not walls
    $graph = new Graph(function ($graph) use ($grid) {
        return $grid->getNeighbors(explode(";",  $graph->current))->remove("#", true)->map(fn () => 1);
    });

    // Compute direct relation, with path tracing
    $direct = $graph->getDirectRelations($keys->keys(), true);

    // Transform all positions into keys/doors
    return $direct
        ->mapKeysRecursive(fn ($k) => (string) $keys[$k])
        ->callEach()->map(fn ($v) => [ // [path[], distance]
            set($v[0])->map(fn ($k) => $grid->get(explode(";", $k)))
                ->filter(fn ($e) => $e >= "A" && $e <= "Z")
                ->values(),
            $v[1]]);
}

function reachable_keys($want, $have) {
    return $want->removeKeys($have->map("strtolower"))->map(fn($v) =>
        $v[0]->remove($have)->count() ? 0 : $v[1]
    )->filter();
}

$keys = simplify(grid($input));


// ==================================================
// > PART 1 : Takes ~ 2sec
// > Solve using Dijkstra, going from keys to keys.
// ==================================================
[$path, $solution_1] = (new Graph(function ($graph) use ($keys) {
    return reachable_keys($keys[$graph->pos], $graph->keys)->mapAssoc(fn ($key, $distance) =>
        [$key . "|" . $graph->keys->merge([strtoupper($key)])->sort()->join("") => $distance]
    );
}))
// Stop when evey key has been found
->defineEnd(function ($graph) use ($keys) {
    [$graph->pos, $graph->keys] = explode("|", $graph->current);
    $graph->keys = set(str_split($graph->keys));
    return count($graph->keys) >= count($keys);
})
// Start from @ with no key found
->explore("@|@");


// ==================================================
// > PART 2 : Takes ~8sec
// > Greedier approch would be to make all outside keys available from the start.
// > It works on some inputs and is way way faster, but does not work on mine.
// ==================================================

// Prepare the 4 subgrids and compute their simplified versions
$grid = grid($input);
[$s, $w, $h] = [$grid->search("@"), $grid->width(), $grid->height()];
$grid->set($s, "#");
foreach ($grid->getNeighbors($s)->keys() as $xy) $grid->set(explode(";", $xy), "#");
$robots = set([
    simplify($grid->set([$s[0] - 1, $s[1] - 1], "@")->sub([0, 0], [$s[0] + 1, $s[1] + 1])),
    simplify($grid->set([$s[0] + 1, $s[1] - 1], "@")->sub([$s[0], 0], [$w, $s[1] + 1])),
    simplify($grid->set([$s[0] - 1, $s[1] + 1], "@")->sub([0, $s[1]], [$s[0] + 1, $h])),
    simplify($grid->set([$s[0] + 1, $s[1] + 1], "@")->sub([$s[0], $s[1]], [$w, $h])),
]);

// Explore with 4 robots at a time, considering moving one of them each step
[$path, $solution_2] = (new Graph(function ($graph) use($robots) {
    $next = [];
    foreach ($graph->pos as $r=>$pos) {
        foreach (reachable_keys($robots[$r][$pos], $graph->keys) as $key=>$dist) {
            $pos = $graph->pos;
            $pos[$r] = $key;
            $next[implode("", $pos) . "|" . $graph->keys->merge([strtoupper($key)])->sort()->join("")] = $dist;
        }
    }
    return $next;
}))
->defineEnd(function ($graph) use ($keys) {
    [$graph->pos, $graph->keys] = explode("|", $graph->current);
    $graph->pos = str_split($graph->pos);
    $graph->keys = set(str_split($graph->keys));
    return count($graph->keys) >= count($keys);
})
->explore("@@@@|@");