Puzzle 19: Never build more robots than needed

Because we can only build one robot at a time, if the most expensive
robot in terms of ore takes 4 ore to build, we'll never need more than 4
ore robots. Because they can always collect enough ore to build one
robot of any type per turn.

Drops time by 90% on 20-round test data (5.4s -> 0.5s)

1 files changed, 19 insertions, 3 deletions

diff --git a/19.c b/19.c
index 4e1cfb3..a534090 100644
--- a/19.c
+++ b/19.c
@@ -8,6 +8,8 @@
 
 #define arrlen(x) (sizeof(x)/sizeof((x)[0]))
 
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
 
 enum MATERIAL {
 	ORE,
@@ -25,6 +27,10 @@ struct blueprint {
 	int bsdn_clay;
 	int geod_ore;
 	int geod_bsdn;
+
+	int max_ore;
+	int max_clay;
+	int max_bsdn;
 };
 
 
@@ -39,6 +45,10 @@ blueprint_ctor(struct blueprint * b, int id, int ore_ore, int clay_ore,
 	b->bsdn_clay = bsdn_clay;
 	b->geod_ore = geod_ore;
 	b->geod_bsdn = geod_bsdn;
+
+	b->max_ore = max(max(b->ore_ore, b->clay_ore), max(b->bsdn_ore, b->geod_ore));
+	b->max_clay = b->bsdn_clay;
+	b->max_bsdn = b->geod_bsdn;
 }
 
 
@@ -237,7 +247,9 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int
 	}
 
 	// Try building a obsidian robot, and checking if that's better than anything else
-	if (inventory_build(&test, b, BSDN) == 0) {
+	if (i->bsdn.robots < b->max_bsdn
+			&& inventory_build(&test, b, BSDN) == 0)
+	{
 //		fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount);
 		inventory_tick(&test);
 		inventory_build_exhaustive(&test, b, remaining - 1);
@@ -247,7 +259,9 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int
 	}
 
 	// Try building a clay robot, and checking if that's better than anything else
-	if (inventory_build(&test, b, CLAY) == 0) {
+	if (i->clay.robots < b->max_clay
+			&& inventory_build(&test, b, CLAY) == 0)
+	{
 //		fprintf(stderr, "%d: building a clay robot (%ld)\n", remaining, test.clay.amount);
 		inventory_tick(&test);
 		inventory_build_exhaustive(&test, b, remaining - 1);
@@ -257,7 +271,9 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int
 	}
 
 	// Try building a ore robot, and checking if that's better than anything else
-	if (inventory_build(&test, b, ORE) == 0) {
+	if (i->ore.robots < b->max_ore
+			&& inventory_build(&test, b, ORE) == 0)
+	{
 //		fprintf(stderr, "%d: building a ore robot (%ld)\n", remaining, test.ore.amount);
 		inventory_tick(&test);
 		inventory_build_exhaustive(&test, b, remaining - 1);