Advent of code 2017/7

Ajax Direct

// > BUILD THE TREE
$weights = [];
$parents = [];
foreach ($input->lines as $line) {
    preg_match('/^(\w+) \((\d+)\)(?: -> (.*))?/', $line, $matches);
    $parents[$matches[1]] = $parents[$matches[1]] ?? "__ROOT__";
    $weights[$matches[1]] = $matches[2];

    if (isset($matches[3])) {
        $parents = array_merge($parents, array_fill_keys(explode(", ", $matches[3]), $matches[1]));
    }
}

$children = (array) set($parents)->flip(true);
$tree     = [];
function add_children(&$tree, $node, $children) {
    foreach ($children[$node] ?? [] as $child) {
        $subtree = [];
        add_children($subtree, $child, $children);
        $tree[$child] = $subtree;
    }
}
add_children($tree, "__ROOT__", $children);

// > COMPUTE WEIGHTS
$total_weights = $weights;
foreach ($weights as $item => $weight) {
    while (($parent = $parents[$item] ?? false) && $parent != "__ROOT__") {
        $total_weights[$parent] += $weight;
        $item = $parent;
    }
}

// ==================================================
// > PART 1
// ==================================================
$solution_1 = array_keys($tree)[0];

// ==================================================
// > PART 2
// ==================================================
$odd = $solution_1;

while (true) {
    if (empty($tree[$odd])) break;

    // Keep track of previous level so that we can backtrack
    $previous_weighted = $weight_tree ?? [];

    // Explore next level to find the odd one
    $tree        = set($tree[$odd]);
    $weight_tree = $tree->keys()->mapAssoc(fn ($i, $k) => [$k => $total_weights[$k]]);
    $weight_tree = $weight_tree->sort();
    $control     = $weight_tree->values()[1];

    // First sorted subitem is different than control
    if ($weight_tree->values()[0] != $control) {
        $odd = $weight_tree->keys()[0];
    // Last sorted subitem is different than control
    } elseif ($weight_tree->values()->last() != $control) {
        $odd = $weight_tree->keys()->last();
    // All item are the same : current item is the odd one
    } else {
        break;
    }
}

// Find difference between current weight and control weight and remove it from the base current weight
$solution_2 = $weights[$odd] - ($previous_weighted[$odd] - $previous_weighted->values()[1]);