2022 day19 part2 cache

1 files changed, 61 insertions, 8 deletions

diff --git a/src/2022/day19/aoc.cpp b/src/2022/day19/aoc.cpp
index d1b2455..f3e0ee3 100644
--- a/src/2022/day19/aoc.cpp
+++ b/src/2022/day19/aoc.cpp
@@ -4,10 +4,33 @@
 
 namespace aoc2022 {
 
+static const int total = 24;
+
 struct build_result {
   int products[4] = {0, 0, 0, 0}; // ore,clay,obsi,geod
   int robots[4] = {1, 0, 0, 0};   // ore,clay,obsi,geod
-  friend bool operator<(build_result r1, build_result r2) { return r1.products[3] < r2.products[3]; }
+  friend bool less(build_result r1, build_result r2) { return r1.products[3] < r2.products[3]; }
+  friend bool operator<(build_result r1, build_result r2) {
+    bool b1 = r1.robots[3] < r2.robots[3];
+    bool b2 = r1.robots[3] > r2.robots[3];
+    bool b3 = r1.robots[2] < r2.robots[2];
+    bool b4 = r1.robots[2] > r2.robots[2];
+    bool b5 = r1.robots[1] < r2.robots[1];
+    bool b6 = r1.robots[1] > r2.robots[1];
+    bool b7 = r1.robots[0] < r2.robots[0];
+    // bool b8 = r1.robots[0] > r2.robots[0];
+
+    // bool c1 = r1.products[3] < r2.products[3];
+    // bool c2 = r1.products[3] > r2.products[3];
+    // bool c3 = r1.products[2] < r2.products[2];
+    // bool c4 = r1.products[2] > r2.products[2];
+    // bool c5 = r1.products[1] < r2.products[1];
+    // bool c6 = r1.products[1] > r2.products[1];
+    // bool c7 = r1.products[0] < r2.products[0];
+
+    // bool x2 = c1 ? true : c2 ? false : c3 ? true : c4 ? false : c5 ? true : c6 ? false : c7;
+    return b1 ? true : b2 ? false : b3 ? true : b4 ? false : b5 ? true : b6 ? false : b7; // ? true : b8 ? false : x2;
+  }
 };
 
 void print_result(int i, int m, const build_result& r) {
@@ -103,16 +126,41 @@ void build_product(const blueprint& b, build_result r, std::vector<build_result>
   }
 }
 
-void build(int m, const blueprint& b, build_result r, build_result& max) {
-  // print_result(b.idx, 24 - m, r);
+struct build_cache {
+  std::map<build_result, int> cache;
+
+  int get(const build_result& r) const noexcept {
+    auto it = cache.find(r);
+    return it == cache.end() ? INT32_MIN : it->second;
+  }
+
+  void set(const build_result& r, int m) {
+    auto p = cache.insert({r, m});
+    if (!p.second) {
+      p.first->second = m;
+    }
+  }
+};
+
+void build(int m, std::vector<build_cache>& cache, const blueprint& b, build_result r, build_result& max, int* mx) {
+  // print_result(b.idx, total - m, r);
+
   if (m > 0) {
+    auto& c = cache[total - m];
+    // auto cm = c.get(r);
+    // if (cm != INT32_MIN && r.products[3] <= cm) {
+    //   return;
+    // }
+
     std::vector<build_result> rs;
     build_product(b, r, rs);
     for (auto& r0 : rs) {
-      build(m - 1, b, r0, max);
+      build(m - 1, cache, b, r0, max, mx);
+      c.set(r0, *mx);
     }
   } else {
-    if (max < r) {
+    *mx = max.products[3];
+    if (less(max, r)) {
       max = r;
     }
   }
@@ -126,18 +174,23 @@ std::pair<int, int> day19(line_view file) {
   });
 
   std::vector<build_result> rs;
+  std::vector<build_cache> cs{total};
   for (auto& b : bs) {
     build_result r;
     build_result m;
     // b.print();
-    build(32, b, r, m);
-    print_result(b.idx, 32, m);
+    for (int i = 0; i < total; i++) {
+      cs[i].cache.clear();
+    }
+    int x{INT32_MIN};
+    build(total, cs, b, r, m, &x);
+    print_result(b.idx, total, m);
     rs.push_back(m);
   }
 
   int quality{0};
   for (size_t i = 0; i < rs.size(); i++) {
-    quality += (i+1) * rs[i].products[3];
+    quality += (i + 1) * rs[i].products[3];
   }
 
   printf("%d\n", quality);