Advent of code 2023/23

Ajax Direct

function get_intersections_links($input, $slopes = []) {
    $grid = (array) $input->lines->map("str_split");
    [$w, $h] = [count($grid[0]), count($grid)];
    [$start, $end] = ["1;0", ($w - 2) . ";" . ($h - 1)];

    // Find all intersections
    $intersections = [$start, $end];
    foreach ($grid as $y=>$row) foreach ($row as $x=>$c) {
        if ($c == "#") continue;
        $paths = 0;
        foreach (neighbors([$x, $y]) as [$nx, $ny]) if (($grid[$ny][$nx]??"#") != "#") $paths++;
        if ($paths >= 3) $intersections[] = "$x;$y";
    }

    // DFS from each intersections to have direct longest links
    $links = [$start => [], $end => []];
    foreach ($intersections as $int) {
        $queue = [$int];
        while ($queue) {
            $current = array_pop($queue);
            $path    = explode("|", $current);
            [$x, $y] = explode(";", $path[count($path) - 1]);

            if ("$x;$y" != $int && in_array("$x;$y", $intersections)) {
                $links[$int]["$x;$y"] = max($links[$int]["$x;$y"]??0, count($path) - 1);
                continue;
            }

            foreach (neighbors([$x, $y]) as $dir=>[$nx, $ny]) {
                if (($grid[$ny][$nx]??"#") == "#") continue;
                if (in_array("$nx;$ny", $path)) continue;
                if (isset($slopes[$grid[$y][$x]]) && $slopes[$grid[$y][$x]] != $dir) continue;
                $queue[] = $current . "|$nx;$ny";
            }
        }
    }
    return $links;
}

function solve($links) {
    [$start, $end] = array_keys($links); // Always the first 2 keys

    // Optimization : move end to the intersection that is just before it
    $offset = $links[$end] ? array_values($links[$end])[0] : 0;
    $end = $links[$end] ? array_keys($links[$end])[0] : $end;

    $queue = [[$start, 0]];
    $max = 0;
    while ($queue) {
        [$state, $distance] = array_pop($queue);
        $path = explode("|", $state);
        $visited = array_fill_keys($path, 1);
        $pos = $path[count($path) - 1];

        if ($pos == $end) {
            $max = max($max, $distance);
            continue;
        }

        foreach (array_diff_key($links[$pos], $visited) as $n=>$d) {
            $queue[] = [$state . "|$n", $distance + $d];
        }
    }

    return $max + $offset;
}

$solution_1 = solve(get_intersections_links($input, [">" => "right", "<" => "left", "^" => "up", "v" => "down"]));
$solution_2 = solve(get_intersections_links($input)); // Takes ~20s on my machine, probably twice that online