2022 day16 part2

1 files changed, 26 insertions, 7 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 94672f2..41d21ac 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -11,6 +11,7 @@ struct valve_m {
   int m;
 
   friend bool operator<(valve_m v1, valve_m v2) { return v1.m < v2.m ? true : v1.m > v2.m ? false : v1.v < v2.v; }
+  friend bool operator>(valve_m v1, valve_m v2) { return v1.m > v2.m ? true : v1.m < v2.m ? false : v1.v > v2.v; }
 };
 
 std::map<line_view, valve*> valves = {};
@@ -112,11 +113,11 @@ bool update(valve_m vs[2], valve_m n0, bool g0, bool m0, valve_m n1, bool g1, bo
   if (g0 && m0 && (!g1 || !m1)) {
     vs[0].m -= n0.m;
     vs[0].v = n0.v;
-    vs[1].m -= vs[1].m > 0 ? 1 : 0; 
+    vs[1].m -= vs[1].m > 0 ? 1 : 0;
     return true;
   }
   if ((!g0 || !m0) && g1 && m1) {
-    vs[0].m -= vs[0].m > 0 ? 1 : 0; 
+    vs[0].m -= vs[0].m > 0 ? 1 : 0;
     vs[1].m -= n1.m;
     vs[1].v = n1.v;
     return true;
@@ -124,7 +125,16 @@ bool update(valve_m vs[2], valve_m n0, bool g0, bool m0, valve_m n1, bool g1, bo
   return false;
 }
 
-void flow(valve_m vs[2], std::map<valve*, int> opened, int os, int total, int* max) {
+struct valve_mm {
+  valve_m vm1;
+  valve_m vm2;
+
+  friend bool operator<(valve_mm m1, valve_mm m2) {
+    return m1.vm1 < m2.vm1 ? true : m1.vm1 > m2.vm1 ? false : m1.vm2 < m2.vm2;
+  }
+};
+
+void flow(valve_m vs[2], std::map<valve_mm, int>& visited, std::map<valve*, int> opened, int os, int total, int* max) {
   for (auto i = 0; i < 2; i++) {
     update_total(&total, opened, vs[i].m);
   }
@@ -133,6 +143,13 @@ void flow(valve_m vs[2], std::map<valve*, int> opened, int os, int total, int* m
       *max = total;
     }
   } else {
+    auto p = visited.insert({{vs[0], vs[1]}, total});
+    if (!p.second) {
+      return;
+      // if (total <= p.first->second) {
+      //   return;
+      // }
+    }
     // for (auto i = 0; i < 2; i++) {
     //   std::cout << i << " at " << vs[i].v->name << " when " << vs[i].m << " minutes left, total is " << total
     //             << std::endl;
@@ -140,7 +157,7 @@ void flow(valve_m vs[2], std::map<valve*, int> opened, int os, int total, int* m
     if (os >= maxopened) {
       vs[0].m -= vs[0].m > 0 ? 1 : 0;
       vs[1].m -= vs[1].m > 0 ? 1 : 0;
-      flow(vs, opened, os, total, max);
+      flow(vs, visited, opened, os, total, max);
     } else {
       for (auto i = 0; i < 2; i++) {
         if (!is_open(vs[i].v, opened)) {
@@ -154,7 +171,7 @@ void flow(valve_m vs[2], std::map<valve*, int> opened, int os, int total, int* m
       if (os >= maxopened) {
         vs[0].m -= vs[0].m > 0 ? 1 : 0;
         vs[1].m -= vs[1].m > 0 ? 1 : 0;
-        flow(vs, opened, os, total, max);
+        flow(vs, visited, opened, os, total, max);
       } else {
         auto& ns0 = diagram[vs[0].v];
         auto& ns1 = diagram[vs[1].v];
@@ -170,7 +187,8 @@ void flow(valve_m vs[2], std::map<valve*, int> opened, int os, int total, int* m
               auto g1 = !is_open(n1.v, opened);
               auto m1 = vx[1].m > n1.m;
               if (update(vx, n0, g0, m0, n1, g1, m1)) {
-                flow(vx, opened, os, total, max);
+                auto v = visited;
+                flow(vx, v, opened, os, total, max);
               }
             }
           }
@@ -225,7 +243,8 @@ std::pair<int, int> day16(line_view file) {
       {get("AA"), 26},
       {get("AA"), 26},
   };
-  flow(vs, opened, 0, 0, &m2);
+  std::map<valve_mm, int> visited;
+  flow(vs, visited, opened, 0, 0, &m2);
   printf("%d %d\n", m1, m2);
 
   return {m1, 0};