Puzzle 19: Don't build a robot if we could have built it earlier

Either we don't need it, or we did but it's too late.

Speeds up part 2 from 570s (9m30s) to 5.2s

1 files changed, 30 insertions, 2 deletions

diff --git a/19.c b/19.c
index c1740e2..0f13c0c 100644
--- a/19.c
+++ b/19.c
@@ -217,6 +217,31 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema
 long exhaustive_iter;
 
 
+// Exhastive(ish) build strategy
+//
+// Try all^Wmost combinations of building different robots at different times
+//
+// We actually cheat and only try building on certain conditions:
+//
+//	if (i->MATERIAL.robots < b->max_MATERIAL)
+//
+//		max_MATERIAL is the maximum amount of MATERIAL it takes to build
+//		any robot. Given that we can only build one robot per round, we
+//		can never spend more than max_MATERIAL units per round, so we
+//		never need more than max_MATERIAL robots of that type.
+//
+//	if (i->MATERIAL.amount < 2 * b->max_MATERIAL)
+//
+//		If we already have a lot of MATERIAL, we probably don't need
+//		another robot to collect that type right now.
+//
+//	if (i->MATERIAL.amount < 2 * b->ROBOT_MATERIAL)
+//
+//		If we could have built a robot of a certain type some time ago,
+//		but didn't, then either a) this is a good build combination and
+//		we don't need it, or b) this is a bad build combination and we
+//		did, but there isn't much point in going further down that
+//		rabbit hole now.
 void
 inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int remaining)
 {
@@ -257,6 +282,8 @@ 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 (i->bsdn.robots < b->max_bsdn
 			&& i->bsdn.amount < 2 * b->max_bsdn
+			&& (i->clay.amount < 2 * b->bsdn_clay
+				|| i->ore.amount < 2 * b->bsdn_ore)
 			&& inventory_build(&test, b, BSDN) == 0)
 	{
 //		fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount);
@@ -270,6 +297,7 @@ 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 (i->clay.robots < b->max_clay
 			&& i->clay.amount < 2 * b->max_clay
+			&& i->ore.amount < 2 * b->clay_ore
 			&& remaining > 5
 			&& inventory_build(&test, b, CLAY) == 0)
 	{
@@ -284,6 +312,7 @@ 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 (i->ore.robots < b->max_ore
 			&& i->ore.amount < 2 * b->max_ore
+			&& i->ore.amount < 2 * b->ore_ore
 			&& remaining > 10
 			&& inventory_build(&test, b, ORE) == 0)
 	{
@@ -309,8 +338,7 @@ main(int argc, char ** argv)
 	regex_t reblueprint;
 	char buf[BUFSIZ];
 
-	while ((i = getopt(argc, argv, "p:b:o:r:")) != -1)
-	{
+	while ((i = getopt(argc, argv, "p:b:o:r:")) != -1) {
 		switch (i) {
 		case 'p':
 			switch (atoi(optarg)) {