2022 day16 part2

1 files changed, 79 insertions, 8 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index fad148c..94672f2 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -62,6 +62,8 @@ void update_total(int* total, std::map<valve*, int>& opened, int m) {
   *total = t;
 }
 
+bool is_open(valve* v, std::map<valve*, int>& opened) { return opened.find(v) != opened.end(); }
+
 // m minutes left at v
 void flow(int m, valve* v, std::map<valve*, int> opened, int os, int total, int* max) {
   update_total(&total, opened, m);
@@ -70,11 +72,10 @@ void flow(int m, valve* v, std::map<valve*, int> opened, int os, int total, int*
       *max = total;
     }
   } else {
-    // std::cout << "at " << v->name << " when " << m << " minutes left, total is " << total << std::endl;
     if (os >= maxopened) {
       flow(m - 1, v, opened, os, total, max);
     } else {
-      if (opened.find(v) == opened.end()) {
+      if (!is_open(v, opened)) {
         if (v->rate > 0) {
           os += 1;
           m -= 1;
@@ -87,7 +88,7 @@ void flow(int m, valve* v, std::map<valve*, int> opened, int os, int total, int*
         // choose next
         auto f{false};
         for (auto& n : diagram[v]) {
-          if (m >= n.m && opened.find(n.v) == opened.end()) {
+          if (m >= n.m && !is_open(n.v, opened)) {
             f = true;
             flow(m - n.m, n.v, opened, os, total, max);
           }
@@ -100,16 +101,81 @@ void flow(int m, valve* v, std::map<valve*, int> opened, int os, int total, int*
   }
 }
 
-void flow(int m, valve* v1, valve* v2, std::map<valve*, int> opened, int os, int total, int* max) {
-  update_total(&total, opened, m);
-  if (m == 0) {
+bool update(valve_m vs[2], valve_m n0, bool g0, bool m0, valve_m n1, bool g1, bool m1) {
+  if (g0 && m0 && g1 && m1) {
+    vs[0].m -= n0.m;
+    vs[0].v = n0.v;
+    vs[1].m -= n1.m;
+    vs[1].v = n1.v;
+    return true;
+  }
+  if (g0 && m0 && (!g1 || !m1)) {
+    vs[0].m -= n0.m;
+    vs[0].v = n0.v;
+    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[1].m -= n1.m;
+    vs[1].v = n1.v;
+    return true;
+  }
+  return false;
+}
+
+void flow(valve_m vs[2], 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);
+  }
+  if (vs[0].m == 0 && vs[1].m == 0) {
     if (*max < total) {
       *max = total;
     }
   } else {
+    // 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;
+    // }
     if (os >= maxopened) {
-      flow(m - 1, v1, v2, opened, os, total, max);
+      vs[0].m -= vs[0].m > 0 ? 1 : 0;
+      vs[1].m -= vs[1].m > 0 ? 1 : 0;
+      flow(vs, opened, os, total, max);
     } else {
+      for (auto i = 0; i < 2; i++) {
+        if (!is_open(vs[i].v, opened)) {
+          if (vs[i].v->rate > 0) {
+            os += 1;
+            vs[i].m -= 1;
+          }
+          opened.insert({vs[i].v, vs[i].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);
+      } else {
+        auto& ns0 = diagram[vs[0].v];
+        auto& ns1 = diagram[vs[1].v];
+        for (auto& n0 : ns0) {
+          for (auto& n1 : ns1) {
+            if (n0.v != n1.v) {
+              valve_m vx[2];
+              vx[0] = vs[0];
+              vx[1] = vs[1];
+
+              auto g0 = !is_open(n0.v, opened);
+              auto m0 = vx[0].m > n0.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);
+              }
+            }
+          }
+        }
+      }
     }
   }
 }
@@ -155,7 +221,12 @@ std::pair<int, int> day16(line_view file) {
 
   opened.clear();
   int m2{INT32_MIN};
-  flow(26, get("AA"), get("AA"), opened, 0, 0, &m2);
+  valve_m vs[2] = {
+      {get("AA"), 26},
+      {get("AA"), 26},
+  };
+  flow(vs, opened, 0, 0, &m2);
+  printf("%d %d\n", m1, m2);
 
   return {m1, 0};
 }