2022 day16 part1

2 files changed, 52 insertions, 47 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 2e40902..68213e8 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -1,8 +1,7 @@
 #include "aoc.h"
-#include <vector>
-#include <iostream>
-#include <set>
 #include <algorithm>
+#include <iostream>
+#include <vector>
 
 namespace aoc2022 {
 std::map<line_view, valve*> valves = {};
@@ -13,48 +12,53 @@ static valve* get(line_view lv) {
   return p.first->second;
 }
 
-
-int get_opened(std::set<line_view>& os) {
+std::pair<int, size_t> get_opened() {
   int total{0};
-  for(auto& v: os) {
-    total += get(v)->rate;
-  }
-  return total;
-}
-
-std::set<line_view> get_closed(std::set<line_view>& opened) {
-  std::set<line_view> closed;
-  for (auto&kv : valves) {
-    if (opened.find(kv.first) == opened.end()) {
-      closed.insert(kv.first);
+  size_t n{0};
+  for (auto& kv : valves) {
+    if (kv.second->open) {
+      total += kv.second->rate;
+      n += 1;
     }
   }
-  return closed;
+  return {total, n};
 }
 
-bool not_open(valve* v, std::set<line_view>& opened) {
-  return opened.find(v->name) == opened.end();
+static char* indent(int s) {
+  static char space[100] = {0};
+  memset(space, 0, 100);
+  for (int i = 0; i < s; i++) {
+    space[i] = ' ';
+  }
+  return space;
 }
 
-void flow(int minute, valve* v, std::set<line_view>& opened, int total, int* maxtotal) {
-  total += get_opened(opened);
-  if (minute == 30) {
-    if (total > *maxtotal){
+void flow(int minute, valve* v, int total, int* maxtotal) {
+  auto p = get_opened();
+  total += p.first;
+  std::cout << indent(minute) << v->name;
+  printf(": %d %zu %d\n", p.first, p.second, total);
+  if (minute >= 30) {
+    if (total > *maxtotal) {
       *maxtotal = total;
     }
-  }
-  else  {
-    if (opened.size() == maxopened) {
-      flow(minute + 1, v, opened, total, maxtotal);
-    }
-    else {
-      if (v->rate > 0 && not_open(v, opened)) {
-          opened.insert(v->name);
-          flow(minute + 1, v, opened, total, maxtotal);
-      }
-      else {
-        for(auto&o : v->others) {
-          flow(minute + 1, get(o), opened, total, maxtotal);
+  } else {
+    if (p.second == maxopened) {
+      flow(minute + 1, v, total, maxtotal);
+    } else {
+      if (v->rate == 0 || v->open) {
+        for (auto& o : v->others) {
+          flow(minute + 1, get(o), total, maxtotal);
+        }
+      } else { // v-rate > 0 && v->open == false
+        auto others = v->others;
+        others.push_back(v->name);
+        for (auto& o : others) {
+          if (o == v->name) { // choose open
+            get(o)->open = true;
+            minute += 1;
+          }
+          flow(minute + 1, get(o), total, maxtotal);
         }
       }
     }
@@ -62,7 +66,7 @@ void flow(int minute, valve* v, std::set<line_view>& opened, int total, int* max
 }
 
 std::pair<int, int> day16(line_view file) {
-  per_line(file, [](line_view lv){
+  per_line(file, [](line_view lv) {
     valve* v = new valve{lv};
     valves[v->name] = v;
 
@@ -81,24 +85,24 @@ std::pair<int, int> day16(line_view file) {
   struct vmax {
     valve* v;
     int max = 0;
-    vmax(valve* p, int m): v(p), max(m) {}
+    vmax(valve* p, int m) : v(p), max(m) {}
   };
 
   std::vector<vmax> vs;
-  for(auto& kv: valves) {
+  for (auto& kv : valves) {
     vs.push_back({kv.second, 0});
   }
 
-  for (auto& vm: vs) {
-    std::set<line_view> opened;
-    flow(1, vm.v, opened, 0, &vm.max);
+  int max{0};
+  flow(1, get("AA"), 0, &max);
+
+  for (auto& vm : vs) {
+    flow(1, vm.v, 0, &vm.max);
   }
 
-  std::sort(vs.begin(), vs.end(), [](vmax v1, vmax v2){
-      return v1.max > v2.max;
-  });
+  std::sort(vs.begin(), vs.end(), [](vmax v1, vmax v2) { return v1.max > v2.max; });
 
-  return {vs[0].max,0};
+  return {max, 0};
 }
 
-}
+} // namespace aoc2022
diff --git a/src/2022/day16/aoc.h b/src/2022/day16/aoc.h
index 7678742..be71624 100644
--- a/src/2022/day16/aoc.h
+++ b/src/2022/day16/aoc.h
@@ -7,6 +7,7 @@ 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) {