2022 day16 part1

2 files changed, 71 insertions, 13 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 5d8c049..b19eae5 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -52,9 +52,65 @@ void rank_neighbours(valve* v, std::map<valve*, int>& visited) {
   }
 }
 
-// m minutes left at v
-void flow(int m, valve* v, int total, int* max) {
+void update_total(int m, int* total, std::map<int, std::set<valve*>>& opened) {
+  for (auto& kv : opened) {
+    if (m > kv.first) {
+      for (valve* v : kv.second) {
+        *total += (m - kv.first) * v->rate;
+      }
+    }
+  }
+}
+
+bool is_opened(valve* v, int m, std::map<int, std::set<valve*>> opened) {
+  for (auto& kv : opened) {
+    if (kv.first < m) {
+      if (kv.second.find(v) != kv.second.end()) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
 
+// m minutes left at v
+void flow(int m, valve* v, std::map<int, std::set<valve*>> opened, int total, int* max) {
+  if (m == 0) {
+    if (*max < total) {
+      *max = total;
+    }
+  } else {
+    update_total(m, &total, opened);
+    auto p = opened.insert({m, {}});
+    auto& os = p.first->second; // std::set<valve*>
+    if (os.size() >= maxopened) {
+      flow(m - 1, v, opened, total, max);
+    } else {
+      if (!p.second) {
+        if (os.find(v) == os.end()) {
+          if (v->rate > 0) {
+            m -= 1;
+            os.insert(v);
+          }
+        } else {
+          // already done this
+          return;
+        }
+      } else {
+        if (v->rate > 0) {
+          m -= 1;
+          os.insert(v);
+        }
+      }
+      // choose next
+      auto& ns = diagram[v];
+      for (auto& n : ns) {
+        if (m > n.m && !is_opened(n.v, m, opened)) {
+          flow(m - n.m, n.v, opened, total, max);
+        }
+      }
+    }
+  }
 }
 
 std::pair<int, int> day16(line_view file) {
@@ -82,17 +138,20 @@ std::pair<int, int> day16(line_view file) {
     diagram.insert({v, vs});
   }
 
-  for (auto& kv : diagram) {
-    valve* v = kv.first;
-    std::cout << v->name << ": ";
-    for (auto& n : kv.second) {
-      std::cout << n.v->name << "(" << n.m << ") ";
-    }
-    std::cout << std::endl;
-  }
+  // for (auto& kv : diagram) {
+  //   valve* v = kv.first;
+  //   std::cout << v->name << ": ";
+  //   for (auto& n : kv.second) {
+  //     std::cout << n.v->name << "(" << n.m << ") ";
+  //   }
+  //   std::cout << std::endl;
+  // }
+
+  int max{INT32_MIN};
+  std::map<int, std::set<valve*>> opened;
+  flow(30, get("AA"), opened, 0, &max);
 
-  int max{0};
-  flow(0, get("AA"), 0, &max);
+  printf("%d\n", max);
 
   return {0, 0};
 }
diff --git a/src/2022/day16/aoc.h b/src/2022/day16/aoc.h
index be71624..7678742 100644
--- a/src/2022/day16/aoc.h
+++ b/src/2022/day16/aoc.h
@@ -7,7 +7,6 @@ namespace aoc2022 {
 struct valve {
   line_view name;
   int rate = 0;
-  bool open = false;
   std::vector<line_view> others;
 
   friend bool operator<(const valve& v1, const valve& v2) {