Advent of code 2016/11

Ajax Direct

function solve($floors, $chips)
{
    $couples = array_map("join", $chips);

    // At each step, define the next states to explore
    $graph = new Graph(function ($graph) use ($chips, $couples) {
        [$elevator, $floors] = get_state($graph->current);
        $states = set();

        // For each combinations of max 2 objects on the current floor, explore bringing them up and down
        foreach (set($floors[$elevator])->combinations(1, 2) as $comb) {
            foreach ([-1, 1] as $move) {
                if ($elevator + $move < 0 || $elevator + $move > count($floors) - 1) continue;

                $next_floors = $floors;
                $next_floors[$elevator] = array_diff($next_floors[$elevator], $comb);
                $next_floors[$elevator + $move] = array_merge($next_floors[$elevator + $move], $comb);
                if (will_explode($next_floors[$elevator], $couples) || will_explode($next_floors[$elevator + $move], $couples)) continue;

                $states[make_state($elevator + $move, $next_floors)] = [$move, $comb, $next_floors];
            }
        }

        return $states;
    });

    // Prune potential states to avoid useless exploration (158210 states)
    $graph->visited = [];
    $graph->addPruning(function ($states, $graph) use ($couples) {
        [$elevator, $floors] = get_state($graph->current);

        // 1 - Never go below the lowest non-empty floor (150379 states)
        $lowest_floor = array_keys(array_filter($floors))[0];
        $states = $states->filter(fn ($state) => $elevator + $state[0] >= $lowest_floor);

        // 2 - Don't bring one item up when you can bring two / Don't bring two items down when you can bring one (43679 states)
        [$min_down, $max_up] = $states->reduce(function ($carry, $state) {
            if ($state[0] == -1 && count($state[1]) < $carry[0]) $carry[0] = count($state[1]);
            if ($state[0] == 1  && count($state[1]) > $carry[1]) $carry[1] = count($state[1]);
            return $carry;
        }, [PHP_INT_MAX, 0]);

        $states = $states->filter(function ($state) use ($min_down, $max_up) {
            if ($state[0] == -1 && count($state[1]) > $min_down) return false;
            if ($state[0] == 1  && count($state[1]) < $max_up) return false;
            return true;
        });

        // 4 - Don't explore states that could have been interchanged with an already visited one (16866 states)
        $signatures = [];
        foreach ($states as $state=>$rel) {
            $signature = str_replace($couples, "#", $state);
            if (isset($graph->visited[$signature])) {
                unset($states[$state]);
            } else {
                $graph->visited[$signature] = true;
            }
        }

        return $states;
    });

    // Use number of steps as node values
    $graph->defineNewValue(fn ($r, $s, $g) => $g->values[$g->current] + 1);

    // A* : add weight to each floor content to go toward the top floor
    $graph->definePriority(function ($graph, $state, $steps, $relation) {
        return $steps * 3
            + count($relation[2][3]) * -10
            + count($relation[2][2]) * -1
            + count($relation[2][1]) * 15
            + count($relation[2][0]) * 25
        ;
    });

    // Explore from start to end (when all objects are on the last floor)
    return $graph->explore(
        make_state(0, $floors),
        (count($floors) - 1) . "||||" . set($chips)->merge()->join()
    )[1];
}

function make_state($elevator, $floors = false)
{
    return $elevator . "|" . set($floors)->callEach()->sort()->callEach()->join()->join("|");
}

function get_state($key) {
    $parts    = explode("|", $key);
    $elevator = array_shift($parts);
    return [(int) $elevator, array_map(fn ($f) => array_filter($f, "strlen"), array_map("str_split", $parts))];
}

function will_explode($floor, $couples) {
    sort($floor); $floor = join($floor);

    // Remove chips (odd values) -> nothing left = NO BOOM
    if (str_replace(range("B", "Z", 2), "", $floor) == "") return false;

    // Remove couples and generator -> if something left, it's an alone chips = BOOM, else NO BOOM
    $w = $floor;
    $floor = str_replace($couples, "", $floor);
    $floor = str_replace(range("A", "Z", 2), "", $floor);
    return $floor;
}

// ==================================================
// > PART 1
// ==================================================
$chips  = [];
$floors = ["first" => [], "second" => [], "third" => [], "fourth" => []];

foreach ($input->lines as $line) {
    preg_match("/The (\w+) floor/", $line, $floor);
    preg_match_all("/(\w+)(-compatible microchip| generator)/", $line, $matches);
    foreach ($matches[1] as $key => $material) {
        $chips[$material] ??= [chr(count($chips) * 2 + 65), chr(count($chips) * 2 + 66)];
        $floors[$floor[1]][] = $matches[2][$key] == " generator" ? $chips[$material][0] : $chips[$material][1];
    }
}

$solution_1 = solve($floors, $chips);

// ==================================================
// > PART 2
// ==================================================
$chips[] = $elerium = [chr(count($chips) * 2 + 65), chr(count($chips) * 2 + 66)];
$chips[] = $dilithium = [chr(count($chips) * 2 + 65), chr(count($chips) * 2 + 66)];
$floors["first"] = array_merge($floors["first"], $elerium, $dilithium);
$couples = array_map("join", $chips);
$solution_2 = solve($floors, $chips, array_map("join", $chips));