First attempt at puzzle 19 part 1 (buggy)

It produces *a* result for each blueprint, but not the best result.

I feel like that's a hard problem. The number of decisions about what to
build when over 24 iterations explodes so much that you can't
brute-force the optimal geode count.

Either there's a way of pruning possibilities that I've not thought of,
or there's a pretty good heuristic you can get from the blueprint about
the proportions of how many of each type of material you want to be
producing, that you can pick what to build and get a geode count that
doesn't deviate from optimal in only 24 iterations.

One other possibility is transforming this puzzle into a SAT format and
letting a SAT solver attack it, with its ability to prune decision trees
effectively. But I don't have any actual experience with those, and I'm
not sure I have time to figure that out for AoC.

https://en.wikipedia.org/wiki/SAT_solver

2 files changed, 224 insertions, 0 deletions

diff --git a/19.c b/19.c
new file mode 100644
index 0000000..3fe6b4a
--- /dev/null
+++ b/19.c
@@ -0,0 +1,223 @@
+
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+#define arrlen(x) (sizeof(x)/sizeof((x)[0]))
+
+
+enum MATERIAL {
+	ORE,
+	CLAY,
+	BSDN,
+	GEOD,
+};
+
+
+struct blueprint {
+	int ore_ore;
+	int clay_ore;
+	int bsdn_ore;
+	int bsdn_clay;
+	int geod_ore;
+	int geod_bsdn;
+};
+
+
+void
+blueprint_ctor(struct blueprint * b, int ore_ore, int clay_ore,
+		int bsdn_ore, int bsdn_clay, int geod_ore, int geod_bsdn)
+{
+	b->ore_ore = ore_ore;
+	b->clay_ore = clay_ore;
+	b->bsdn_ore = bsdn_ore;
+	b->bsdn_clay = bsdn_clay;
+	b->geod_ore = geod_ore;
+	b->geod_bsdn = geod_bsdn;
+}
+
+
+struct material {
+	long amount;
+	long robots;
+	long pending;
+};
+
+
+void
+material_ctor(struct material * m, long amount, long robots)
+{
+	m->amount = amount;
+	m->robots = robots;
+	m->pending = 0;
+}
+
+
+// Tick a material.
+//
+// Amount increases by the number of robots
+// Number of robots increases by number of pending robots
+void
+material_tick(struct material * m)
+{
+	m->amount += m->robots;
+	m->robots += m->pending;
+	m->pending = 0;
+}
+
+
+struct inventory {
+	struct material ore;
+	struct material clay;
+	struct material bsdn;
+	struct material geod;
+};
+
+
+void
+inventory_init(struct inventory * i)
+{
+	material_ctor(&i->ore, 0, 1);
+	material_ctor(&i->clay, 0, 0);
+	material_ctor(&i->bsdn, 0, 0);
+	material_ctor(&i->geod, 0, 0);
+}
+
+
+void
+inventory_tick(struct inventory * i)
+{
+	material_tick(&i->ore);
+	material_tick(&i->clay);
+	material_tick(&i->bsdn);
+	material_tick(&i->geod);
+}
+
+
+// Try to build a robot out of material #m
+int
+inventory_build(struct inventory * i, struct blueprint const * b, enum MATERIAL m)
+{
+	switch (m) {
+	case ORE:
+		if (i->ore.amount < b->ore_ore)
+			return -1;
+		i->ore.amount -= b->ore_ore;
+		i->ore.pending += 1;
+		break;
+
+	case CLAY:
+		if (i->ore.amount < b->clay_ore)
+			return -1;
+		i->ore.amount -= b->clay_ore;
+		i->clay.pending += 1;
+		break;
+
+	case BSDN:
+		if (i->ore.amount < b->bsdn_ore
+				|| i->clay.amount < b->bsdn_clay)
+			return -1;
+		i->ore.amount -= b->bsdn_ore;
+		i->clay.amount -= b->bsdn_clay;
+		i->bsdn.pending += 1;
+		break;
+
+	case GEOD:
+		if (i->ore.amount < b->geod_ore
+				|| i->bsdn.amount < b->geod_bsdn)
+			return -1;
+		i->ore.amount -= b->geod_ore;
+		i->bsdn.amount -= b->geod_bsdn;
+		i->geod.pending += 1;
+		break;
+
+	default:
+		return -1;
+	}
+
+	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.
+//
+// Not optimal. But it helps get the structure of the program working.
+void
+inventory_build_basic(struct inventory * i, struct blueprint const * b, int remaining)
+{
+	(void) remaining;
+
+	while (inventory_build(i, b, GEOD) == 0)
+		;
+
+	while (inventory_build(i, b, BSDN) == 0)
+		;
+
+	while (inventory_build(i, b, CLAY) == 0)
+		;
+
+	while (inventory_build(i, b, ORE) == 0)
+		;
+}
+
+
+int
+main()
+{
+	regex_t reblueprint;
+	char buf[BUFSIZ];
+
+	if (regcomp(&reblueprint, "Blueprint ([[:digit:]]+):"
+				" Each ore robot costs ([[:digit:]]+) ore."
+				" Each clay robot costs ([[:digit:]]+) ore."
+				" Each obsidian robot costs ([[:digit:]]+) ore and ([[:digit:]]+) clay."
+				" Each geode robot costs ([[:digit:]]+) ore and ([[:digit:]]+) obsidian.",
+				REG_EXTENDED) != 0)
+	{
+		fprintf(stderr, "Bad regex\n");
+		return -1;
+	}
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		regmatch_t rematch[8];
+		int bid, t;
+		struct blueprint b;
+		struct inventory i;
+
+		if (regexec(&reblueprint, buf, arrlen(rematch), rematch, 0) != 0) {
+			fprintf(stderr, "Unexpected blueprint in %s\n", buf);
+			continue;
+		}
+
+		bid = atoi(buf + rematch[1].rm_so);
+		blueprint_ctor(&b, atoi(buf + rematch[2].rm_so),
+				atoi(buf + rematch[3].rm_so),
+				atoi(buf + rematch[4].rm_so),
+				atoi(buf + rematch[5].rm_so),
+				atoi(buf + rematch[6].rm_so),
+				atoi(buf + rematch[7].rm_so));
+
+		inventory_init(&i);
+		for (t = 0; t < 24; ++t) {
+			inventory_build_basic(&i, &b, 24 - t);
+
+			inventory_tick(&i);
+
+			fprintf(stderr, "Blueprint %d tick %d, ore: %ld/%ld, clay %ld/%ld, bsdn %ld/%ld, geod %ld/%ld\n",
+					bid, t + 1,
+					i.ore.amount, i.ore.robots,
+					i.clay.amount, i.clay.robots,
+					i.bsdn.amount, i.bsdn.robots,
+					i.bsdn.amount, i.bsdn.robots);
+		}
+
+		printf("Blueprint %d geodes = %ld\n", bid, i.geod.amount);
+	}
+
+	regfree(&reblueprint);
+
+	return 0;
+}
+
diff --git a/makefile b/makefile
index 2a45609..5b108f6 100644
--- a/makefile
+++ b/makefile
@@ -20,6 +20,7 @@ all: bin \
 	bin/16 \
 	bin/17 \
 	bin/18 \
+	bin/19 \
 
 bin:
 	mkdir -p $@