2016 day17

1 files changed, 96 insertions, 1 deletions

diff --git a/src/2016/day17/aoc.cpp b/src/2016/day17/aoc.cpp
index 8696528..dee844c 100644
--- a/src/2016/day17/aoc.cpp
+++ b/src/2016/day17/aoc.cpp
@@ -1,6 +1,101 @@
 #include "aoc.h"
+#include "md5.h"
+#include <deque>
+#include <map>
+#include <set>
 
 namespace aoc2016 {
 
-std::pair<int64_t, int64_t> day17(line_view) { return {0, 0}; }
+struct pos {
+  int x;
+  int y;
+  int n;
+  std::string* path;
+
+  bool operator==(pos p) { return x == p.x && y == p.y; }
+  friend bool operator<(pos p1, pos p2) { return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y; }
+  bool isvalid() const noexcept { return x > 0 && x < 5 && y > 0 && y < 5; }
+};
+
+static pos bfs(pos p, pos target, const std::string& passcode) {
+  std::deque<pos> q;
+  // std::set<pos> visited;
+  q.push_back(p);
+
+  auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
+  while (!q.empty()) {
+    auto s = q.size();
+    while (s-- > 0) {
+      pos p0 = q.front();
+      q.pop_front();
+      if (p0 == target) {
+        return p0;
+      }
+
+      pos ns[4] = {
+          {p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
+          {p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
+          {p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
+          {p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
+      };
+
+      for (size_t i = 0; i < 4; i++) {
+        pos nx = ns[i];
+        std::string pass{passcode};
+        pass.append(*nx.path);
+        char md5[33] = {0};
+        memcpy(md5, md5sum((char*)pass.c_str()), 32);
+        // printf("%s: %d %d %d %s\n", md5, p0.x, p0.y, p0.n, (*p0.path).c_str());
+        if (nx.isvalid() && is_open(*(md5 + i))) {
+          char direction[] = {'U', 'D', 'L', 'R'};
+          nx.path->push_back(direction[i]);
+          q.push_back(nx);
+        }
+      }
+    }
+  }
+
+  return target;
+}
+
+static void dfs(pos p0, pos target, const std::string& passcode, int* max) {
+  if (p0 == target) {
+    if (*max < p0.n) {
+      *max = p0.n;
+    }
+  } else {
+    pos ns[4] = {
+        {p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
+        {p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
+        {p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
+        {p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
+    };
+
+    auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
+    for (size_t i = 0; i < 4; i++) {
+      pos nx = ns[i];
+      std::string pass{passcode};
+      pass.append(*nx.path);
+      char md5[33] = {0};
+      memcpy(md5, md5sum((char*)pass.c_str()), 32);
+      if (nx.isvalid() && is_open(*(md5 + i))) {
+        char direction[] = {'U', 'D', 'L', 'R'};
+        nx.path->push_back(direction[i]);
+        dfs(nx, target, passcode, max);
+      }
+    }
+  }
+}
+
+std::pair<std::string, int64_t> day17(line_view) {
+  static std::string ss[] = {"", "UNKNOWN"};
+  pos b = {1, 1, 0, ss};
+  pos e = {4, 4, INT32_MAX, ss + 1};
+
+  auto p = bfs(b, e, "bwnlcvfs");
+  int max{INT32_MIN};
+  dfs(b, e, "bwnlcvfs", &max);
+
+  return {*p.path, max};
+}
 } // namespace aoc2016