2022 day16 part1

1 files changed, 38 insertions, 39 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 05e1d47..5ef909f 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -54,46 +54,46 @@ void rank_neighbours(valve* v, std::map<valve*, int>& visited) {
   }
 }
 
-void update_total(int* total, std::set<valve*>& opened) {
-  for (valve* v : opened) {
-    *total += v->rate;
+void update_total(int* total, std::map<valve*, int>& opened, int m) {
+  int t{0};
+  for (auto& kv : opened) {
+    t += kv.first->rate * (kv.second - m);
   }
+  *total = t;
 }
 
 // m minutes left at v
-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);
+void flow(int m, valve* v, std::map<valve*, int> opened, int os, int total, int* max) {
+  update_total(&total, opened, m);
   if (m == 0) {
     if (*max < total) {
       *max = total;
     }
   } else {
-    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;
+    // std::cout << "at " << v->name << " when " << m << " minutes left, total is " << total << std::endl;
     if (os >= maxopened) {
-      flow(m - 1, v, visited, opened, os, total, max);
+      flow(m - 1, v, opened, os, total, max);
     } else {
       if (opened.find(v) == opened.end()) {
         if (v->rate > 0) {
           os += 1;
           m -= 1;
         }
-        opened.insert(v);
+        opened.insert({v, m});
       }
-
-      // choose next
-      for (auto& n : diagram[v]) {
-        if (m >= n.m) {
-          auto v = visited;
-          flow(m - n.m, n.v, visited, opened, os, total, max);
-          visited = v;
+      if (os >= maxopened) {
+        flow(m - 1, v, opened, os, total, max);
+      } else {
+        // choose next
+        auto f{false};
+        for (auto& n : diagram[v]) {
+          if (m >= n.m && opened.find(n.v) == opened.end()) {
+            f = true;
+            flow(m - n.m, n.v, opened, os, total, max);
+          }
+        }
+        if (!f && m > 0) {
+          flow(m - 1, v, opened, os, total, max);
         }
       }
     }
@@ -117,30 +117,29 @@ 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) {
+      if (kv.first != v && kv.first->rate > 0) {
         vs.emplace_back(valve_m{kv.first, kv.second});
       }
     }
-    std::sort(vs.begin(), vs.end(), [](valve_m v1, valve_m v2) { return v1.m < v2.m; });
+    std::sort(vs.begin(), vs.end(), [](valve_m v1, valve_m v2) {
+      return v1.m < v2.m ? true : v1.m > v2.m ? false : v1.v->rate > v2.v->rate;
+    });
     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;
-  std::map<valve_m, int> visited;
-  flow(30, get("AA"), visited, opened, 0, 0, &max);
+  // for (auto& kv : diagram) {
+  //   std::cout << kv.first->name << ": ";
+  //   for (auto& m : kv.second) {
+  //     std::cout << m.v->name << "(" << m.m << "," << m.v->rate << ") ";
+  //   }
+  //   std::cout << std::endl;
+  // }
 
-  printf("%d\n", max);
+  int m1{INT32_MIN};
+  std::map<valve*, int> opened;
+  flow(30, get("AA"), opened, 0, 0, &m1);
 
-  return {0, 0};
+  return {m1, 0};
 }
 
 } // namespace aoc2022