const PODS = [
"A" => [0, 2, 1],
"B" => [1, 4, 10],
"C" => [2, 6, 100],
"D" => [3, 8, 1000],
];
const NOSTOP = [2 => true, 4 => true, 6 => true, 8 => true];
function solve($start, $space) {
return (new Graph(function ($graph) use ($space) {
[$corr, $rooms] = explode("|", $graph->current);
[$corr, $rooms] = [str_split($corr), str_split($rooms)];
$next = [];
// Consider rooms->corridor
foreach ($rooms as $i=>$r) {
if ($r == ".") continue;
if ($i >= 4 && $rooms[$i - 4] != ".") continue;
for ($j = $i; $j < $space*4; $j += 4) {
if ($graph->end[12 + $j] != $rooms[$j]) break;
if ($j >= ($space - 1) * 4) continue 2;
}
$c = ($i % 4) * 2 + 2;
foreach ([[1, 11], [-1, -1]] as [$incr, $bound]) {
for ($j = $c; $j != $bound; $j += $incr) {
if ($corr[$j] != ".") break;
if (isset(NOSTOP[$j])) continue;
$state = $graph->current;
$state[$j] = $r;
$state[$i + 12] = ".";
$next[$state] = ((floor($i/4)+1) + abs($c - $j)) * PODS[$r][2];
}
}
}
// Consider corridor->room
foreach ($corr as $i=>$c) {
if ($c == ".") continue;
if ($rooms[PODS[$c][0]] != ".") continue;
for ($f = $space - 1; $f >= 0; $f--) {
$t = PODS[$c][0] + $f*4;
if ($rooms[$t] == ".") break;
if ($rooms[$t] != $c) continue 2;
if (!$f) continue 2;
}
foreach (range($i, PODS[$c][1]) as $p) {
if ($i == $p) continue;
if ($corr[$p] != ".") continue 2;
}
$state = $graph->current;
$state[$i] = ".";
$state[PODS[$c][0] + (4*$f) + 12] = $c;
$next[$state] = (abs($i-PODS[$c][1]) + 1 + $f) * PODS[$c][2];
}
return $next;
}))
->explore(
"...........|".$start,
"...........|".str_repeat("ABCD", $space),
)[1];
}
// ==================================================
// > SOLVE
// ==================================================
$letters = implode("", $input->matchAll("/[A-D]/")[0]);
$solution_1 = solve($letters, 2);
$solution_2 = solve(substr($letters, 0, 4) . "DCBADBAC" . substr($letters, 4, 4), 4);