2022 day16 part1

5 files changed, 148 insertions, 5 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};
+}
+
 }
diff --git a/src/2022/day16/aoc.h b/src/2022/day16/aoc.h
index 82e0895..7678742 100644
--- a/src/2022/day16/aoc.h
+++ b/src/2022/day16/aoc.h
@@ -1,5 +1,54 @@
 #include "common.h"
+#include <vector>
+#include <map>
 
 namespace aoc2022 {
+
+struct valve {
+  line_view name;
+  int rate = 0;
+  std::vector<line_view> others;
+
+  friend bool operator<(const valve& v1, const valve& v2) {
+    return v1.rate > v2.rate;
+  }
+
+  void get_number(const char** pp, int* d) {
+    const char* p = *pp;
+    while(*p >= '0' && *p <= '9') {
+      *d = *d * 10 + *p - '0';
+      p++;
+    }
+    *pp = p;
+  }
+
+  bool isAZ(const char* p) {
+    return *p >= 'A' && *p <= 'Z';
+  }
+
+  bool is09(const char* p) {
+    return *p >= '0' && *p <= '9';
+  }
+
+  valve(line_view lv) {
+    const char *p = lv.line;
+    while (p < lv.line + lv.length) {
+      if (is09(p)) {
+        get_number(&p, &rate);
+      }
+      if (isAZ(p) && isAZ(p+1)) {
+          if (*(p+3) == 'h') {
+              name = line_view{p, 2};
+          }
+          else {
+              others.push_back({p, 2});
+          }
+      }
+      p++;
+    }
+  }
+};
+
+
 std::pair<int, int> day16(line_view);
 }
diff --git a/src/2022/day16/input b/src/2022/day16/input
index bfd1474..300042b 100644
--- a/src/2022/day16/input
+++ b/src/2022/day16/input
@@ -61,4 +61,3 @@ Valve SG has flow rate=15; tunnels lead to valves WU, YQ
 Valve FN has flow rate=25; tunnel leads to valve PH
 Valve KL has flow rate=0; tunnels lead to valves TN, OQ
 Valve ZX has flow rate=5; tunnels lead to valves JS, HP, VL, NQ, TS
-
diff --git a/src/2022/day16/input0 b/src/2022/day16/input0
index acf5495..9f30acc 100644
--- a/src/2022/day16/input0
+++ b/src/2022/day16/input0
@@ -8,4 +8,3 @@ Valve GG has flow rate=0; tunnels lead to valves FF, HH
 Valve HH has flow rate=22; tunnel leads to valve GG
 Valve II has flow rate=0; tunnels lead to valves AA, JJ
 Valve JJ has flow rate=21; tunnel leads to valve II
-
diff --git a/test/test_2022.cpp b/test/test_2022.cpp
index 9f14b5f..04be125 100644
--- a/test/test_2022.cpp
+++ b/test/test_2022.cpp
@@ -126,7 +126,7 @@ TEST_CASE("Beacon Exclusion Zone", "[2022]") {
 }
 
 TEST_CASE("Proboscidea Volcanium", "[2022]") {
-  line_view lv = load_file("../src/2022/day16/input");
+  line_view lv = load_file("../src/2022/day16/input0");
   auto p = aoc2022::day16(lv);
   REQUIRE(0 == p.first);
   REQUIRE(0 == p.second);