day 19 part 1

1 files changed, 95 insertions, 0 deletions

diff --git a/22.19/main.cpp b/22.19/main.cpp
new file mode 100644
index 0000000..45985c9
--- /dev/null
+++ b/22.19/main.cpp
@@ -0,0 +1,95 @@
+#include <algorithm>
+#include <cstdio>
+#include <optional>
+#include <vector>
+using namespace std;
+
+enum Material {
+	Ore, Clay, Obs, Geode, MatAmt
+};
+const Material Mats[] = {Ore, Clay, Obs, Geode};
+
+// Material Matrix.
+// heh
+typedef int MatMat[MatAmt][MatAmt];
+
+struct State
+{
+	int amts[MatAmt] = {0};
+	int robots[MatAmt] = {1, 0, 0, 0};
+	int rem = 0;
+
+	State idle(int t) const {
+		State s = *this;
+		for (auto m : Mats) {
+			s.amts[m] += s.robots[m] * t;
+		}
+		s.rem -= t;
+		return s;
+	}
+
+	int timeUntil(const int reqs[MatAmt]) const {
+		int worst = 0;
+		for (auto m : Mats) {
+			if (amts[m] < reqs[m]) {
+				if (robots[m] == 0) return -1;
+				worst = max(worst, (reqs[m] - amts[m] + robots[m] - 1) / robots[m]);
+			}
+			if (rem < worst) return -1;
+		}
+		return worst + 1; // +1 to account for robot build
+	}
+
+	optional<State> buyRobot(MatMat const& costs, Material robot) const {
+		int t = timeUntil(costs[robot]);
+		if (t < 0 || rem <= t) return {};
+		State s = idle(t);
+		for (auto m : Mats) {
+			s.amts[m] -= costs[robot][m];
+		}
+		s.robots[robot]++;
+		return s;
+	}
+
+	int best(MatMat const& costs) const {
+		if (rem <= 0) return 0;
+		int r = 0;
+		bool wanted[MatAmt] = {0};
+		wanted[Geode] = true;
+		for (auto m : {Geode, Obs, Clay, Ore}) {
+			if (!wanted[m]) continue;
+
+			for (auto m2 : Mats) {
+				if (robots[m2] < costs[m][m2]) {
+					wanted[m2] = true;
+				}
+			}
+
+			auto s = buyRobot(costs, m);
+			if (s) {
+				r = max(r, s->best(costs));
+			}
+		}
+
+		State s = idle(rem);
+		r = max(r, s.amts[Geode]);
+		return r;
+	}
+};
+
+int
+main()
+{
+	const char *fmt = "Blueprint %d: "
+		"Each ore robot costs %d ore. "
+		"Each clay robot costs %d ore. "
+		"Each obsidian robot costs %d ore and %d clay. "
+		"Each geode robot costs %d ore and %d obsidian. ";
+	int id;
+	MatMat costs = {0};
+	int total = 0;
+	while (scanf(fmt, &id, &costs[Ore][Ore], &costs[Clay][Ore], &costs[Obs][Ore], &costs[Obs][Clay], &costs[Geode][Ore], &costs[Geode][Obs]) == 7) {
+		total += id * State{.rem=24}.best(costs);
+	}
+	printf("%d\n", total);
+}