Advent of code 2015/9

Ajax Direct

$nodes = [];
foreach ($input->lines as $line) {
    preg_match('/^([a-zA-Z]+) to ([a-zA-Z]+) = ([0-9]+)$/', $line, $matches);
    $nodes[$matches[1]][$matches[2]] = (int) $matches[3];
    $nodes[$matches[2]][$matches[1]] = (int) $matches[3];
}

$nodes["start"] = array_fill_keys(array_keys($nodes), 0);

// ==================================================
// > PART 1
// ==================================================
// Make each unvisited city available as a next state to explore
$graph = new Graph(function ($graph) use ($nodes) {
    $path    = explode(">", $graph->current);
    $current = end($path);
    $left    = set($nodes[$current])->removeKeys($path);

    return $left->mapAssoc(function ($city, $dist) use ($graph) {
        return [$graph->current . ">" . $city => $dist];
    });
});

// Stop when all cities have been visited
$graph->defineEnd(function ($graph) use ($nodes) {
    return count(explode(">", $graph->current)) == count(array_keys($nodes));
});

$solution_1 = $graph->explore("start")[1];

// ==================================================
// > PART 2
// ==================================================
// Prune states that have no chance to be the best
$graph->setTarget("highest")->addPruning(function ($states, $graph) use ($nodes) {
    if (!empty($graph->values) && max($graph->values) > $graph->values[$graph->current] + $states->count() * 149) {
        return set([]);
    }
    return $states;
});
$solution_2 = $graph->explore("start")[1];