2022 day16 part1

1 files changed, 35 insertions, 11 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 460b29a..05e1d47 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -9,12 +9,14 @@ namespace aoc2022 {
 struct valve_m {
   valve* v;
   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; }
 };
 
 std::map<line_view, valve*> valves = {};
 std::map<valve*, std::vector<valve_m>> diagram;
 
-size_t maxopened = 0;
+int maxopened = 0;
 
 static valve* get(line_view lv) {
   auto p = valves.insert({lv, nullptr});
@@ -59,26 +61,39 @@ void update_total(int* total, std::set<valve*>& opened) {
 }
 
 // m minutes left at v
-void flow(int m, valve* v, std::set<valve*> opened, int total, int* max) {
+void flow(int m, valve* v, std::map<valve_m, int>& visited, std::set<valve*> opened, int os, int total, int* max) {
+  update_total(&total, opened);
   if (m == 0) {
     if (*max < total) {
       *max = total;
     }
   } else {
-    update_total(&total, opened);
+    auto p = visited.insert({{v, m}, total});
+    if (!p.second) {
+      if (total <= p.first->second) {
+        return;
+      } else {
+        p.first->second = total;
+      }
+    }
     std::cout << "at " << v->name << " when " << m << " minutes left, total is " << total << std::endl;
-    if (opened.size() >= maxopened) {
-      flow(m - 1, v, opened, total, max);
+    if (os >= maxopened) {
+      flow(m - 1, v, visited, opened, os, total, max);
     } else {
-      if (v->rate > 0 && opened.find(v) == opened.end()) {
-        m -= 1;
+      if (opened.find(v) == opened.end()) {
+        if (v->rate > 0) {
+          os += 1;
+          m -= 1;
+        }
         opened.insert(v);
       }
 
       // choose next
       for (auto& n : diagram[v]) {
-        if (m >= n.m && opened.find(n.v) == opened.end()) {
-          flow(m - n.m, n.v, opened, total, max);
+        if (m >= n.m) {
+          auto v = visited;
+          flow(m - n.m, n.v, visited, opened, os, total, max);
+          visited = v;
         }
       }
     }
@@ -102,7 +117,7 @@ std::pair<int, int> day16(line_view file) {
     rank_neighbours(v, visited);
     std::vector<valve_m> vs;
     for (auto& kv : visited) {
-      if (kv.first != v && kv.first->rate > 0) {
+      if (kv.first != v) {
         vs.emplace_back(valve_m{kv.first, kv.second});
       }
     }
@@ -110,9 +125,18 @@ std::pair<int, int> day16(line_view file) {
     diagram.insert({v, vs});
   }
 
+  for (auto& kv : diagram) {
+    std::cout << kv.first->name << ": ";
+    for (auto& m : kv.second) {
+      std::cout << m.v->name << "(" << m.m << ") ";
+    }
+    std::cout << std::endl;
+  }
+
   int max{INT32_MIN};
   std::set<valve*> opened;
-  flow(29, get("BB"), opened, 0, &max);
+  std::map<valve_m, int> visited;
+  flow(30, get("AA"), visited, opened, 0, 0, &max);
 
   printf("%d\n", max);