2022 day16 part1

1 files changed, 98 insertions, 2 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index edcf106..2e40902 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -1,8 +1,104 @@
 #include "aoc.h"
 #include <vector>
+#include <iostream>
+#include <set>
+#include <algorithm>
 
 namespace aoc2022 {
-std::pair<int, int> day16(line_view) {
-  return {0,0};
+std::map<line_view, valve*> valves = {};
+size_t maxopened = 0;
+
+static valve* get(line_view lv) {
+  auto p = valves.insert({lv, nullptr});
+  return p.first->second;
+}
+
+
+int get_opened(std::set<line_view>& os) {
+  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);
+    }
+  }
+  return closed;
+}
+
+bool not_open(valve* v, std::set<line_view>& opened) {
+  return opened.find(v->name) == opened.end();
+}
+
+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){
+      *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);
+        }
+      }
+    }
+  }
 }
+
+std::pair<int, int> day16(line_view file) {
+  per_line(file, [](line_view lv){
+    valve* v = new valve{lv};
+    valves[v->name] = v;
+
+    if (v->rate > 0) {
+      maxopened += 1;
+    }
+
+    // std::cout << v->name << ":" << v->rate << " ";
+    // for (auto& o : v->others) {
+    //   std::cout << o << " ";
+    // }
+    // printf("\n");
+    return true;
+  });
+
+  struct vmax {
+    valve* v;
+    int max = 0;
+    vmax(valve* p, int m): v(p), max(m) {}
+  };
+
+  std::vector<vmax> vs;
+  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);
+  }
+
+  std::sort(vs.begin(), vs.end(), [](vmax v1, vmax v2){
+      return v1.max > v2.max;
+  });
+
+  return {vs[0].max,0};
+}
+
 }