// > 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]);