aoc2017/day7/main.php

<?php
// https://adventofcode.com/2017/day/7

function puzzle1(string $input) : string
{
    $lines = explode(PHP_EOL, $input);
    $children = [];
    $names = [];

    foreach ($lines as $line) {
        // Split away master from children data
        list($master, $child) = explode(' -> ', $line);

        // Split number from name
        list($masterName, $masterNumber) = explode(' ', $master);

        // Map up children
        if (!empty($child)) {
            $children = array_merge($children, explode(', ', $child));
        }

        $names[] = $masterName;
    }

    // Flip children for faster lookup
    $children = array_flip($children);

    foreach ($names as $name) {
        if (!isset($children[$name])) {
            return $name;
        }
    }
}

function puzzle2(string $input) : int
{
    $lines = explode(PHP_EOL, $input);
    $familyTree = [];
    $names = [];
    $grandparent = puzzle1($input);
    $parentPoints = [];

    foreach ($lines as $line) {
        // Split away master from children data
        list($master, $child) = explode(' -> ', $line);

        // Split number from name and clean up the number
        list($masterName, $masterNumber) = explode(' ', $master);
        $masterNumber = str_replace(['(', ')'], '', $masterNumber);

        // Map up children
        if (!empty($child)) {
            $familyTree[$masterName] = explode(', ', $child);
        }

        $names[$masterName] = $masterNumber;
    }

    function treePoints(array $familyTree, array $names, array &$wrongTrees, string $name) : int {
        $points = 0;

        if (isset($familyTree[$name])) {
            $subtreePoints = [];

            foreach ($familyTree[$name] as $subname) {
                $subtreePoints[$subname] = $names[$subname] + treePoints($familyTree, $names, $wrongTrees, $subname);

                $points += $names[$subname] + treePoints($familyTree, $names, $wrongTrees, $subname);
            }

            // If we have some error in this tree, put it into the list of wrongtrees
            $copy = array_unique($subtreePoints);
            if (count($copy) > 1) {
                $wrongTrees[] = $subtreePoints;
            }
        }

        return $points;
    };

    $wrongTrees = [];

    // Extract the core family
    foreach ($familyTree[$grandparent] as $name) {
        $parentPoints[$name] = $names[$name] + treePoints($familyTree, $names, $wrongTrees, $name);
    }

    // Find which subtree that contains the error
    $wrongTree = [];
    foreach ($wrongTrees as $tree) {
        foreach ($wrongTrees as $subtree) {
            if (json_encode($tree) === json_encode($subtree)) {
                $wrongTree = $tree;
                break 2;
            }
        }
    }

    // Find a value that only exists once in the wrong tree
    $errorNumber = 0;
    $notErrorNumber = 0;
    foreach (array_count_values($wrongTree) as $number => $count) {
        if ($count === 1) {
            $errorNumber = $number;
        } else {
            $notErrorNumber = $number;
        }
    }

    // Find the broken name
    $errorName = array_search($errorNumber, $wrongTree);

    // calculate diff
    $diff = $errorNumber - $notErrorNumber;

    // Find original value of the errornus name
    $errorNameOriginalValue = $names[$errorName];

    // Calucalete correct value
    return $errorNameOriginalValue - $diff;
}

echo 'First challange solution:'.PHP_EOL;
echo puzzle1(trim(file_get_contents(dirname(__FILE__).'/input.txt'))).PHP_EOL.PHP_EOL;

echo 'Second challange sample:'.PHP_EOL;
echo puzzle2(trim(file_get_contents(dirname(__FILE__).'/input.txt'))).PHP_EOL;