2016 day13

3 files changed, 70 insertions, 4 deletions

diff --git a/src/2016/day13/README.md b/src/2016/day13/README.md
index 577401b..01cb3f9 100644
--- a/src/2016/day13/README.md
+++ b/src/2016/day13/README.md
@@ -39,3 +39,6 @@ Thus, reaching 7,4 would take a minimum of 11 steps (starting from your current
 What is the fewest number of steps required for you to reach 31,39?
 
 Your puzzle input is 1352.
+
+--- Part Two ---
+How many locations (distinct x,y coordinates, including your starting location) can you reach in at most 50 steps?
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
diff --git a/test/test_2016.cpp b/test/test_2016.cpp
index b253f94..82d272a 100644
--- a/test/test_2016.cpp
+++ b/test/test_2016.cpp
@@ -122,11 +122,11 @@ TEST_CASE("Leonardo's Monorail", "[2016]") {
 }
 
 
-TEST_CASE("", "[2016]") {
+TEST_CASE("A Maze of Twisty Little Cubicles", "[2016]") {
   line_view lv = load_file("../src/2016/day13/input");
   auto p = aoc2016::day13(lv);
-  REQUIRE(0 == p.first);
-  REQUIRE(0 == p.second);
+  REQUIRE(90 == p.first);
+  REQUIRE(135 == p.second);
 }