From 6e18fd3683259528c97dbbde5753f339b4a83bcc Mon Sep 17 00:00:00 2001
From: Adam Spragg <adam@spra.gg>
Date: Fri, 30 Dec 2022 13:16:18 +0000
Subject: Puzzle 19: Add an "exhaustive" build strategy.

As expected, the explosion in permutations makes this prohibitive.

With this stragegy, on Blueprint 2 of the test input, for:
  10 rounds it takes   0.018s/59,979 iterations
  11 rounds it takes   0.070s/1,257,483 iterations
  12 rounds it takes   1.292s/59,156,010 iterations
  13 rounds it takes 3m2.770s/8,395,942,157 iterations

Getting to 24 rounds just isn't feasible with that growth.

And I can't figure out how to cull unwanted permutations easily.

Going to have to try something else.
---
 19.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 93 insertions(+)

(limited to '19.c')

diff --git a/19.c b/19.c
index 5e9e485..a53f3d3 100644
--- a/19.c
+++ b/19.c
@@ -89,6 +89,27 @@ inventory_init(struct inventory * i)
 }
 
 
+int
+inventory_cmp(struct inventory const * a, struct inventory const * b)
+{
+	if (a->geod.amount != b->geod.amount)
+		return a->geod.amount - b->geod.amount;
+	if (a->geod.robots != b->geod.robots)
+		return a->geod.robots - b->geod.robots;
+	if (a->bsdn.amount != b->bsdn.amount)
+		return a->bsdn.amount - b->bsdn.amount;
+	if (a->bsdn.robots != b->bsdn.robots)
+		return a->bsdn.robots - b->bsdn.robots;
+	if (a->clay.amount != b->clay.amount)
+		return a->clay.amount - b->clay.amount;
+	if (a->clay.robots != b->clay.robots)
+		return a->clay.robots - b->clay.robots;
+	if (a->ore.amount != b->ore.amount)
+		return a->ore.amount - b->ore.amount;
+	return a->ore.robots - b->ore.robots;
+}
+
+
 void
 inventory_tick(struct inventory * i)
 {
@@ -178,6 +199,68 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema
 }
 
 
+long exhaustive_iter;
+
+
+void
+inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int remaining)
+{
+	struct inventory best, test;
+
+	if (!remaining)
+		// No time to do anything!
+		return;
+
+	++exhaustive_iter;
+
+	// Try doing nothing else this round.
+	best = *i;
+	inventory_tick(&best);
+//	fprintf(stderr, "%d: doing nothing\n", remaining);
+	inventory_build_exhaustive(&best, b, remaining - 1);
+
+	test = *i;
+
+	// Try building a geode robot, and check if that's better than doing nothing.
+	if (inventory_build(&test, b, GEOD) == 0) {
+//		fprintf(stderr, "%d: building a geod robot (%ld)\n", remaining, test.geod.amount);
+		inventory_build_exhaustive(&test, b, remaining);
+		if (inventory_cmp(&test, &best) > 0)
+			best = test;
+		test = *i;
+	}
+
+	// Try building a obsidian robot, and checking if that's better than anything else
+	if (inventory_build(&test, b, BSDN) == 0) {
+//		fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount);
+		inventory_build_exhaustive(&test, b, remaining);
+		if (inventory_cmp(&test, &best) > 0)
+			best = test;
+		test = *i;
+	}
+
+	// Try building a clay robot, and checking if that's better than anything else
+	if (inventory_build(&test, b, CLAY) == 0) {
+//		fprintf(stderr, "%d: building a clay robot (%ld)\n", remaining, test.clay.amount);
+		inventory_build_exhaustive(&test, b, remaining);
+		if (inventory_cmp(&test, &best) > 0)
+			best = test;
+		test = *i;
+	}
+
+	// Try building a ore robot, and checking if that's better than anything else
+	if (inventory_build(&test, b, ORE) == 0) {
+//		fprintf(stderr, "%d: building a ore robot (%ld)\n", remaining, test.ore.amount);
+		inventory_build_exhaustive(&test, b, remaining);
+		if (inventory_cmp(&test, &best) > 0)
+			best = test;
+		test = *i;
+	}
+
+	*i = best;
+}
+
+
 int
 main(int argc, char ** argv)
 {
@@ -238,6 +321,16 @@ main(int argc, char ** argv)
 		if (strcmp(build, "basic") == 0) {
 			inventory_build_basic(&i, &b, rounds);
 		}
+		else if (strcmp(build, "exhaustive") == 0) {
+			exhaustive_iter = 0;
+			inventory_build_exhaustive(&i, &b, rounds);
+			fprintf(stdout, "Blueprint %d, iterations %ld, ore %ld/%ld, clay %ld/%ld, bsdn %ld/%ld, geod %ld/%ld\n",
+				b.id, exhaustive_iter,
+				i.ore.amount, i.ore.robots,
+				i.clay.amount, i.clay.robots,
+				i.bsdn.amount, i.bsdn.robots,
+				i.geod.amount, i.geod.robots);
+		}
 		else {
 			fprintf(stderr, "Unknown build strategy: %s\n", build);
 			regfree(&reblueprint);
-- 
cgit v1.2.1