From d3e37c83f8ba0df7a8240031ad5fa55a761f362c Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Sun, 29 Jan 2023 16:14:31 +0000 Subject: Puzzle 19: Add maximum-geode-building shortcut If we have enough robots to collect enough materials every turn to build a new geode robot every turn, and enough materials to build a geode robot this turn, it's trivial to calculate how many geodes it's possible to collect in the remaining time. --- 19.c | 39 +++++++++++++++++++++++++++++++++++++-- 1 file changed, 37 insertions(+), 2 deletions(-) (limited to '19.c') diff --git a/19.c b/19.c index 4ea88c2..c147555 100644 --- a/19.c +++ b/19.c @@ -180,6 +180,39 @@ inventory_build(struct inventory * i, struct blueprint const * b, enum MATERIAL } +// Check if we can build at least one geode robot per turn every turn (including this one) +// +// If we can, update inventory with max geodes/robots for remaining time, and return 1 +// If not, return 0 +int +inventory_build_max(struct inventory * i, struct blueprint const * b, int remaining) +{ + if (!remaining) + // No time to do anything, so technically, yes. + return 1; + + if (i->bsdn.robots >= b->geod_bsdn + && i->bsdn.amount >= b->geod_bsdn + && i->ore.robots >= b->geod_ore + && i->ore.amount >= b->geod_ore) + { + // Can build robots * remaining from existing robots + i->geod.amount += i->geod.robots * remaining; + + // And half the square from new robots + i->geod.amount += (remaining - 1) * remaining / 2; + + // And we'll build this many robots in that time. + i->geod.robots += remaining; + + return 1; + } + + // No, we can't. + return 0; +} + + // Most basic build algorithm. Build as many of the most important things that you // can, and then as many of the next most important, and so on. // @@ -190,6 +223,9 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema int t; for (t = 0; t < remaining; ++t) { + if (inventory_build_max(i, b, remaining - t)) + return; + while (inventory_build(i, b, GEOD) == 0) ; @@ -237,8 +273,7 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int { struct inventory best, test; - if (!remaining) - // No time to do anything! + if (inventory_build_max(i, b, remaining)) return; best = *i; -- cgit v1.2.1