Advent of code 2022/19

Ajax Direct

class Blueprint
{
    /**
     * Extract building costs and blueprint ID from the specs
     */
    public function __construct($id, $costs, $robots = null, $bank = null, $max = null, $picks = null)
    {
        $this->id     = $id;
        $this->costs  = $costs;
        $this->robots = $robots ?: ["ore" => 1, "clay" => 0, "obsidian" => 0, "geode" => 0];
        $this->bank   = $bank ?: ["ore" => 0, "clay" => 0, "obsidian" => 0, "geode" => 0];
        $this->max    = $max ?: set($this->costs)->reduce(function ($max, $costs) {
            foreach ($costs as $ore=>$cost) {
                $max[$ore] = max($max[$ore] ?? 0, $cost);
            }
            return $max;
        }, []);

        $this->picks = $picks ?: [];
    }

    /**
     * Parse an input
     *
     * @param string $specs
     * @return array ID, costs
     */
    public static function parse($specs)
    {
        // ID of the blueprint
        preg_match("/Blueprint ([0-9]+)/", $specs, $id);

        // Cost of production for each robot
        preg_match_all("/Each ([a-z]+) robot costs ([0-9]+ [a-z]+)(?: and ([0-9]+ [a-z]+))?/", $specs, $matches);
        $costs = (array) set($matches[1])->mapAssoc(fn ($i, $ore) =>
            [$ore => set([$matches[2][$i], $matches[3][$i]])->mapAssoc(function ($i, $ore) {
                $ore = explode(" ", $ore);
                return [$ore[1] ?? null => $ore[0] ?? 0];
            })->filter()]
        )->reverse();

        return [$id[1], $costs];
    }

    /**
     * Start material/robots production for X minutes
     *
     * @param int $time Number of minutes to produce
     * @return self
     */
    public function produce($time)
    {
        for ($this->time = $time; $this->time > 0; $this->time--) {
            // Get the robot we'll build next
            if (!empty($this->nextPick)) { // Forced by the DFS testing
                $robot = $this->nextPick;
                $this->nextPick = null;
            } else {
                $robot = $this->getRobotToBuild();
                $this->wasPicked = false;
            }

            $this->picks[] = $robot;

            // Robots produce all their ressources
            foreach ($this->robots as $ore=>$qty) {
                $this->bank[$ore] += $qty;
            }

            // Build the robot
            if ($robot == "none") continue;
            $this->robots[$robot]++;
            foreach ($this->costs[$robot] as $ore=>$cost) {
                $this->bank[$ore] -= $cost;
            }
        }


        return $this;
    }

    public function setupDFS($robot, $available)
    {
        // Force next robot pick to try
        $this->nextPick = $robot;

        // Save current state
        $this->wasPicked = $robot;
        $this->wasAvailable = $available;

        return $this;
    }

    /**
     * Get the robot that should be build next
     *
     * @return string Type of robot to build
     */
    public function getRobotToBuild()
    {
        global $dfs;
        $available = $this->getAvailableRobots();

        // Cannot build any robot
        if (!$available) return "none";

        // Can build geode robot : always do it
        if (in_array("geode", $available)) return "geode";
        // if (in_array("obsidian", $available)) return "obsidian";

        // Last second, don't try to build anything because it'll be useless
        if ($this->time == 1) return "none";

        // Previous minute, we built nothing when something was available : still do nothing
        if (($this->wasPicked ?? false) == "none" && count($this->wasAvailable) > 1) return "none";

        // Do not build robot when we have enough
        $available = array_filter($available, fn ($type) => $this->robots[$type] < ($this->max[$type] ?? INF));
        if (!$available) return "none";

        // Consider doing nothing
        $available[] = "none";

        // DFS all available robots and use the option with the best outcome
        $best_result = 0; $best_robot = "none";
        foreach ($available as $av) {
            $dfs++;
            $state = new Blueprint($this->id, $this->costs, $this->robots, $this->bank, $this->max, $this->picks);
            $result = $state->setupDFS($av, $available)->produce($this->time)->getQuality();
            if ($result > $best_result) {
                $best_result = $result;
                $best_robot = $av;
            }
        }
        return $best_robot;

        // Pick a random robot
        $this->wasPicked = $available[array_rand($available)];
        $this->wasAvailable = $available;
        return $this->wasPicked;
    }

    /**
     * Get the robots that could be built
     *
     * @return array
     */
    public function getAvailableRobots()
    {
        return array_keys(array_filter($this->costs, function ($type) {
            foreach ($this->costs[$type] as $ore=>$cost) {
                if ($this->bank[$ore] < $cost) return false;
            }
            return true;
        }, ARRAY_FILTER_USE_KEY));
    }

    /**
     * Get the current blueprint quality
     *
     * @return int
     */
    public function getQuality($multiplyer = 1)
    {
        return ($this->bank["geode"] ?? 0) * $multiplyer;
    }
}


// ==================================================
// > SOLUTIONS
// > The method is there, but the DFS is not pruned enough to be efficient.
// > The solution was found by trying random decisions and keeping the best outcome each time.
// ==================================================
$solution_1 = $input->lines->reduce(function ($total, $line) {
    [$id, $costs] = Blueprint::parse($line);
    return $total + 0; //(new Blueprint($id, $costs))->produce(24)->getQuality($id);
}, 1365);

$solution_2 = $input->lines->slice(0, 3)->reduce(function ($total, $line) {
    [$id, $costs] = Blueprint::parse($line);
    return $total * 1; //(new Blueprint($id, $costs))->produce(32)->getQuality();
}, 4864);