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.

1 files changed, 37 insertions, 2 deletions

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;