1 files changed, 64 insertions, 1 deletions
diff --git a/src/2016/day13/aoc.cpp b/src/2016/day13/aoc.cpp
index ed39607..b14d03e 100644
--- a/src/2016/day13/aoc.cpp
+++ b/src/2016/day13/aoc.cpp
@@ -1,6 +1,69 @@
 #include "aoc.h"
+#include <deque>
+#include <set>
 
 namespace aoc2016 {
 
-std::pair<int64_t, int64_t> day13(line_view) { return {0, 0}; }
+struct pos {
+  int64_t x;
+  int64_t y;
+  int64_t n;
+
+  friend bool operator<(pos p1, pos p2) { return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y; }
+  bool operator==(pos p) const noexcept { return x == p.x && y == p.y; }
+};
+
+bool is_space(int64_t x, int64_t y, int64_t favorite) {
+  int64_t a = x * x + 3 * x + 2 * x * y + y + y * y + favorite;
+  int64_t c = __builtin_popcount(a);
+  return x >= 0 && y >= 0 && (c & 1) == 0;
+}
+
+int64_t bfs(pos start, pos end, int64_t favorite, std::set<pos>& visited) {
+  std::deque<pos> q;
+
+  q.push_back(start);
+  visited.insert(start);
+
+  while (!q.empty()) {
+    auto s = q.size();
+    while (s-- > 0) {
+      auto p0 = q.front();
+      q.pop_front();
+      visited.insert(p0);
+
+      if (p0 == end) {
+        return p0.n;
+      } else {
+        pos ns[4] = {
+            {p0.x - 1, p0.y, p0.n + 1},
+            {p0.x + 1, p0.y, p0.n + 1},
+            {p0.x, p0.y - 1, p0.n + 1},
+            {p0.x, p0.y + 1, p0.n + 1},
+        };
+        for (pos p : ns) {
+          if (is_space(p.x, p.y, favorite)) {
+            auto it = visited.find(p);
+            if (it == visited.end() || it->n >= p.n) {
+              q.push_back(p);
+            }
+          }
+        }
+      }
+    }
+  }
+  return INT64_MAX;
+}
+
+std::pair<int64_t, int64_t> day13(line_view) {
+  std::set<pos> visited;
+  int64_t s = bfs({1, 1, 0}, {31, 39, INT64_MAX}, 1352, visited);
+  int64_t total{0};
+  for (auto& p : visited) {
+    if (p.n <= 50) {
+      total += 1;
+    }
+  }
+  return {s, total};
+}
 } // namespace aoc2016