1 files changed, 53 insertions, 6 deletions

diff --git a/src/2016/day24/aoc.cpp b/src/2016/day24/aoc.cpp
index f3d7912..5cd74a3 100644
--- a/src/2016/day24/aoc.cpp
+++ b/src/2016/day24/aoc.cpp
@@ -47,9 +47,45 @@ void bfs(maze::pos p, maze& m, std::map<maze::pos, int>& ds) {
   }
 }
 
+int to0(int i, maze& mz, const std::vector<std::map<maze::pos, int>>& vds) {
+  auto& m = vds[i];
+  for (auto& kv : m) {
+    if (mz.get(kv.first.x, kv.first.y) == '0') {
+      return kv.second;
+    }
+  }
+  return INT32_MAX;
+}
+
+struct mdistance {
+  int d0 = INT32_MAX;
+  int d1 = INT32_MAX;
+};
+
+void shortest_route(int i, int total, std::set<int> selected, size_t max, maze& mz,
+                    const std::vector<std::map<maze::pos, int>>& vds, mdistance* shortest) {
+  selected.insert(i);
+  if (selected.size() == max) {
+    if (shortest->d0 > total) {
+      shortest->d0 = total;
+    }
+    int t0 = to0(i, mz, vds);
+    if (shortest->d1 > total + t0) {
+      shortest->d1 = total + t0;
+    }
+  } else {
+    for (auto& kv : vds[i]) {
+      int n = mz.get(kv.first.x, kv.first.y) - '0';
+      if (selected.find(n) == selected.end()) {
+        shortest_route(n, total + kv.second, selected, max, mz, vds, shortest);
+      }
+    }
+  }
+}
+
 std::pair<int64_t, int64_t> day24(line_view file) {
-  // maze mz{179, 43}; // input
-  maze mz{11, 5}; // demo
+  maze mz{179, 43}; // input
+  // maze mz{11, 5}; // demo
   int r{0};
   per_line(file, [&r, &mz](line_view lv) {
     mz.load(r++, lv);
@@ -57,14 +93,25 @@ std::pair<int64_t, int64_t> day24(line_view file) {
   });
 
   std::vector<std::map<maze::pos, int>> vds;
-  // vds.resize(8); // input
-  vds.resize(5); // demo
-  for (auto &n: mz.numbers) {
+  constexpr int max = 8; // input
+  // constexpr int max = 5; // demo
+  vds.resize(max);
+  for (auto& n : mz.numbers) {
     int i = mz.get(n.x, n.y) - '0';
     auto& ds = vds[i];
     bfs(n, mz, ds);
   }
 
+  mdistance shortest[max];
+  for (size_t i = 0; i < vds.size(); i++) {
+    std::set<int> selected;
+    shortest_route(i, 0, selected, max, mz, vds, &shortest[i]);
+  }
+
+  // for (auto s : shortest) {
+  //   printf("%d %d\n", s.d0, s.d1);
+  // }
+
   // for (auto& ds : vds) {
   //   for (auto& kv : ds) {
   //     printf("(%c: %d) ", mz.get(kv.first.x, kv.first.y), kv.second);
@@ -76,6 +123,6 @@ std::pair<int64_t, int64_t> day24(line_view file) {
   // for (auto& p : mz.numbers) {
   //   printf("%c: (%d, %d)\n", mz.get(p.x, p.y), p.x, p.y);
   // }
-  return {0, 0};
+  return {shortest[0].d0, shortest[0].d1};
 }
 } // namespace aoc2016