2022 day19 backtrack

1 files changed, 23 insertions, 33 deletions

diff --git a/src/2022/day19/aoc.cpp b/src/2022/day19/aoc.cpp
index 4260374..923505b 100644
--- a/src/2022/day19/aoc.cpp
+++ b/src/2022/day19/aoc.cpp
@@ -52,45 +52,35 @@ bool can_build(const blueprint& b, const build_result& r, int i) {
   return d.d0 >= 0 && d.d1 >= 0;
 }
 
-std::set<int> to_build(const blueprint& b, const build_result& r) {
-  std::set<int> is;
-  for (int i = 3; i >= 0; i--) {
-    if (can_build(b, r, i)) {
-      is.insert(i);
-      break;
-    } else {
-      is.insert(INT32_MAX);
+// i = 3,2,1,0
+void build_product(int x, const blueprint& b, build_result r, std::vector<build_result>& rs) {
+  if (x < 0) {
+    build_product(r, 5);
+    rs.push_back(r);
+  } else {
+    auto r0 = r;
+    bool built{false};
+    for (int i = x; i >= 0; i--) {
+      while (can_build(b, r0, i)) {
+        built = true;
+        r0 = build_robot(i, r0, b);
+        build_product(r0, i);
+      }
     }
-  }
-  return is;
-}
-
-struct p4 {
-  int products[4] = {-1, -1, -1, -1};
-
-  p4(int ps[4]) {
-    for (int i = 0; i < 4; i++) {
-      products[i] = ps[i];
+    if (built) {
+      rs.push_back(r0);
     }
+    build_product(x - 1, b, r, rs);
   }
-  p4() {}
-
-  int at(int i) const noexcept { return products[i]; }
-};
+}
 
 void build(int m, const blueprint& b, build_result r, build_result& max) {
-  print_result(b.idx, 24 - m, r);
+  // print_result(b.idx, 24 - m, r);
   if (m > 0) {
-    auto is = to_build(b, r);
-    for (auto i : is) {
-      if (i != INT32_MAX) {
-        auto r0 = build_robot(i, r, b);
-        build_product(r0, i);
-        build(m - 1, b, r0, max);
-      } else {
-        build_product(r, 5);
-        build(m - 1, b, r, max);
-      }
+    std::vector<build_result> rs;
+    build_product(3, b, r, rs);
+    for (auto& r0 : rs) {
+      build(m - 1, b, r0, max);
     }
   } else {
     if (max < r) {