2016 day24

5 files changed, 117 insertions, 10 deletions

diff --git a/src/2016/day24/README.md b/src/2016/day24/README.md
index f6e4d96..579acf3 100644
--- a/src/2016/day24/README.md
+++ b/src/2016/day24/README.md
@@ -27,3 +27,7 @@ Since the robot isn't very fast, you need to find it the shortest route. This pa
 
 Given your actual map, and starting from location 0, what is the fewest number of steps required to visit every non-0 number marked on the map at least once?
 
+--- Part Two ---
+Of course, if you leave the cleaning robot somewhere weird, someone is bound to notice.
+
+What is the fewest number of steps required to start at 0, visit every non-0 number marked on the map at least once, and then return to 0?
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
diff --git a/src/2016/day25/README.md b/src/2016/day25/README.md
index e69de29..12c9103 100644
--- a/src/2016/day25/README.md
+++ b/src/2016/day25/README.md
@@ -0,0 +1,26 @@
+--- Day 25: Clock Signal ---
+You open the door and find yourself on the roof. The city sprawls away from you for miles and miles.
+
+There's not much time now - it's already Christmas, but you're nowhere near the North Pole, much too far to deliver these stars to the sleigh in time.
+
+However, maybe the huge antenna up here can offer a solution. After all, the sleigh doesn't need the stars, exactly; it needs the timing data they provide, and you happen to have a massive signal generator right here.
+
+You connect the stars you have to your prototype computer, connect that to the antenna, and begin the transmission.
+
+Nothing happens.
+
+You call the service number printed on the side of the antenna and quickly explain the situation. "I'm not sure what kind of equipment you have connected over there," he says, "but you need a clock signal." You try to explain that this is a signal for a clock.
+
+"No, no, a clock signal - timing information so the antenna computer knows how to read the data you're sending it. An endless, alternating pattern of 0, 1, 0, 1, 0, 1, 0, 1, 0, 1...." He trails off.
+
+You ask if the antenna can handle a clock signal at the frequency you would need to use for the data from the stars. "There's no way it can! The only antenna we've installed capable of that is on top of a top-secret Easter Bunny installation, and you're definitely not-" You hang up the phone.
+
+You've extracted the antenna's clock signal generation assembunny code (your puzzle input); it looks mostly compatible with code you worked on just recently.
+
+This antenna code, being a signal generator, uses one extra instruction:
+
+out x transmits x (either an integer or the value of a register) as the next value for the clock signal.
+The code takes a value (via register a) that describes the signal to generate, but you're not sure how it's used. You'll have to find the input to produce the right signal through experimentation.
+
+What is the lowest positive integer that can be used to initialize register a and cause the code to output a clock signal of 0, 1, 0, 1... repeating forever?
+
diff --git a/src/2016/day25/input b/src/2016/day25/input
index e69de29..3907038 100644
--- a/src/2016/day25/input
+++ b/src/2016/day25/input
@@ -0,0 +1,30 @@
+cpy a d
+cpy 11 c
+cpy 231 b
+inc d
+dec b
+jnz b -2
+dec c
+jnz c -5
+cpy d a
+jnz 0 0
+cpy a b
+cpy 0 a
+cpy 2 c
+jnz b 2
+jnz 1 6
+dec b
+dec c
+jnz c -4
+inc a
+jnz 1 -7
+cpy 2 b
+jnz c 2
+jnz 1 4
+dec b
+dec c
+jnz 1 -4
+jnz 0 0
+out b
+jnz a -19
+jnz 1 -21
diff --git a/test/test_2016.cpp b/test/test_2016.cpp
index 040f96c..31320d6 100644
--- a/test/test_2016.cpp
+++ b/test/test_2016.cpp
@@ -213,14 +213,14 @@ TEST_CASE("Safe Cracking", "[2016]") {
 
 
 TEST_CASE("Air Duct Spelunking", "[2016]") {
-  line_view lv = load_file("../src/2016/day24/input0");
+  line_view lv = load_file("../src/2016/day24/input");
   auto p = aoc2016::day24(lv);
-  REQUIRE(0 == p.first);
-  REQUIRE(0 == p.second);
+  REQUIRE(490 == p.first);
+  REQUIRE(744 == p.second);
 }
 
 
-TEST_CASE("", "[2016]") {
+TEST_CASE("Clock Signal", "[2016]") {
   line_view lv = load_file("../src/2016/day25/input");
   auto p = aoc2016::day25(lv);
   REQUIRE(0 == p.first);