2022 day16 part1

2 files changed, 117 insertions, 39 deletions

diff --git a/src/2022/day16/README.md b/src/2022/day16/README.md
index eb70272..ae3cbff 100644
--- a/src/2022/day16/README.md
+++ b/src/2022/day16/README.md
@@ -145,4 +145,83 @@ This approach lets you release the most pressure possible in 30 minutes with thi
 
 Work out the steps to release the most pressure in 30 minutes. What is the most pressure you can release?
 
+--- Part Two ---
+
+You're worried that even with an optimal approach, the pressure released won't be enough. What if you got one of the elephants to help you?
+
+It would take you 4 minutes to teach an elephant how to open the right valves in the right order, leaving you with only 26 minutes to actually execute your plan. Would having two of you working together be better, even if it means having less time? (Assume that you teach the elephant before opening any valves yourself, giving you both the same full 26 minutes.)
+
+In the example above, you could teach the elephant to help you as follows:
+
+== Minute 1 ==
+No valves are open.
+You move to valve II.
+The elephant moves to valve DD.
+
+== Minute 2 ==
+No valves are open.
+You move to valve JJ.
+The elephant opens valve DD.
+
+== Minute 3 ==
+Valve DD is open, releasing 20 pressure.
+You open valve JJ.
+The elephant moves to valve EE.
+
+== Minute 4 ==
+Valves DD and JJ are open, releasing 41 pressure.
+You move to valve II.
+The elephant moves to valve FF.
+
+== Minute 5 ==
+Valves DD and JJ are open, releasing 41 pressure.
+You move to valve AA.
+The elephant moves to valve GG.
+
+== Minute 6 ==
+Valves DD and JJ are open, releasing 41 pressure.
+You move to valve BB.
+The elephant moves to valve HH.
+
+== Minute 7 ==
+Valves DD and JJ are open, releasing 41 pressure.
+You open valve BB.
+The elephant opens valve HH.
+
+== Minute 8 ==
+Valves BB, DD, HH, and JJ are open, releasing 76 pressure.
+You move to valve CC.
+The elephant moves to valve GG.
+
+== Minute 9 ==
+Valves BB, DD, HH, and JJ are open, releasing 76 pressure.
+You open valve CC.
+The elephant moves to valve FF.
+
+== Minute 10 ==
+Valves BB, CC, DD, HH, and JJ are open, releasing 78 pressure.
+The elephant moves to valve EE.
+
+== Minute 11 ==
+Valves BB, CC, DD, HH, and JJ are open, releasing 78 pressure.
+The elephant opens valve EE.
+
+(At this point, all valves are open.)
+
+== Minute 12 ==
+Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure.
+
+...
+
+== Minute 20 ==
+Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure.
+
+...
+
+== Minute 26 ==
+Valves BB, CC, DD, EE, HH, and JJ are open, releasing 81 pressure.
+
+With the elephant helping, after 26 minutes, the best you could do would release a total of 1707 pressure.
+
+With you and an elephant working together for 26 minutes, what is the most pressure you could release?
 
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