2022 day16 part1

1 files changed, 57 insertions, 71 deletions

diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 870ab9e..5d8c049 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -1,11 +1,19 @@
 #include "aoc.h"
 #include <algorithm>
+#include <deque>
 #include <iostream>
 #include <set>
 #include <vector>
 
 namespace aoc2022 {
+struct valve_m {
+  valve* v;
+  int m;
+};
+
 std::map<line_view, valve*> valves = {};
+std::map<valve*, std::vector<valve_m>> diagram;
+
 size_t maxopened = 0;
 
 static valve* get(line_view lv) {
@@ -13,55 +21,30 @@ static valve* get(line_view lv) {
   return p.first->second;
 }
 
-std::pair<int, size_t> get_opened(std::set<valve*>& opened) {
-  int total{0};
-  size_t n{0};
-  for (auto& v : opened) {
-    total += v->rate;
-    n += 1;
-  }
-  return {total, n};
-}
-
-// 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;
-// }
+// bfs Dijkstra’s algorithm
+// You estimate it will take you one minute to open a single valve
+// and one minute to follow any tunnel from one valve to another.
+void rank_neighbours(valve* v, std::map<valve*, int>& visited) {
+  std::deque<valve*> q;
+  q.push_back(v);
+  visited.insert({v, 0});
 
-void flow(int minute, valve* v, std::set<valve*> opened, int total, int* maxtotal) {
-  auto p = get_opened(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 (p.second == maxopened) {
-      flow(minute + 1, v, opened, total, maxtotal);
-    } else {
-      if (v->rate == 0 || v->open) {
-        for (auto& o : v->others) {
-          if (get(o)->rate == 0 || !get(o)->open) {
-            flow(minute + 1, get(o), opened, 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;
-            opened.insert(v);
-            flow(minute + 2, get(o), opened, total, maxtotal);
-          }
-          else {
-            flow(minute + 1, get(o), opened, total, maxtotal);
+  while (!q.empty()) {
+    auto s = q.size();
+    while (s-- > 0) {
+      valve* vx = q.front();
+      q.pop_front();
+      for (auto& lv : vx->others) {
+        valve* vn = get(lv);
+        auto it = visited.find(vn);
+        int m = visited[vx] + 1;
+        if (it == visited.end()) {
+          visited.insert({vn, m});
+          q.push_back(vn);
+        } else {
+          if (m < it->second) {
+            it->second = m;
+            q.push_back(vn);
           }
         }
       }
@@ -69,6 +52,11 @@ void flow(int minute, valve* v, std::set<valve*> opened, int total, int* maxtota
   }
 }
 
+// m minutes left at v
+void flow(int m, valve* v, int total, int* max) {
+
+}
+
 std::pair<int, int> day16(line_view file) {
   per_line(file, [](line_view lv) {
     valve* v = new valve{lv};
@@ -77,38 +65,36 @@ std::pair<int, int> day16(line_view file) {
     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});
+    valve* v = kv.second;
+    std::map<valve*, int> visited;
+    rank_neighbours(v, visited);
+    std::vector<valve_m> vs;
+    for (auto& kv : visited) {
+      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; });
+    diagram.insert({v, vs});
   }
 
-  int max{0};
-  std::set<valve*> opened;
-  flow(1, get("AA"), opened, 0, &max);
-
-  for (auto& vm : vs) {
-    std::set<valve*> os;
-    flow(1, vm.v, os, 0, &vm.max);
+  for (auto& kv : diagram) {
+    valve* v = kv.first;
+    std::cout << v->name << ": ";
+    for (auto& n : kv.second) {
+      std::cout << n.v->name << "(" << n.m << ") ";
+    }
+    std::cout << std::endl;
   }
 
-  std::sort(vs.begin(), vs.end(), [](vmax v1, vmax v2) { return v1.max > v2.max; });
+  int max{0};
+  flow(0, get("AA"), 0, &max);
 
-  return {max, 0};
+  return {0, 0};
 }
 
 } // namespace aoc2022