2017 day18

4 files changed, 191 insertions, 4 deletions

diff --git a/src/2017/day18/README.md b/src/2017/day18/README.md
index 6423baa..c0573bc 100644
--- a/src/2017/day18/README.md
+++ b/src/2017/day18/README.md
@@ -36,3 +36,28 @@ At the time the recover operation is executed, the frequency of the last sound p
 
 What is the value of the recovered frequency (the value of the most recently played sound) the first time a rcv instruction is executed with a non-zero value?
 
+--- Part Two ---
+As you congratulate yourself for a job well done, you notice that the documentation has been on the back of the tablet this entire time. While you actually got most of the instructions correct, there are a few key differences. This assembly code isn't about sound at all - it's meant to be run twice at the same time.
+
+Each running copy of the program has its own set of registers and follows the code independently - in fact, the programs don't even necessarily run at the same speed. To coordinate, they use the send (snd) and receive (rcv) instructions:
+
+snd X sends the value of X to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.
+rcv X receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.
+Each program also has its own program ID (one 0 and the other 1); the register p should begin with this value.
+
+For example:
+
+snd 1
+snd 2
+snd p
+rcv a
+rcv b
+rcv c
+rcv d
+Both programs begin by sending three values to the other. Program 0 sends 1, 2, 0; program 1 sends 1, 2, 1. Then, each program receives a value (both 1) and stores it in a, receives another value (both 2) and stores it in b, and then each receives the program ID of the other program (program 0 receives 1; program 1 receives 0) and stores it in c. Each program now sees a different value in its own copy of register c.
+
+Finally, both programs try to rcv a fourth time, but no data is waiting for either of them, and they reach a deadlock. When this happens, both programs terminate.
+
+It should be noted that it would be equally valid for the programs to run at different speeds; for example, program 0 might have sent all three values and then stopped at the first rcv before program 1 executed even its first instruction.
+
+Once both of your programs have terminated (regardless of what caused them to do so), how many times did program 1 send a value?
diff --git a/src/2017/day18/aoc.cpp b/src/2017/day18/aoc.cpp
index 1308c9e..9cef4c9 100644
--- a/src/2017/day18/aoc.cpp
+++ b/src/2017/day18/aoc.cpp
@@ -1,6 +1,158 @@
 #include "aoc.h"
+#include <deque>
 
 namespace aoc2017 {
+static int64_t& get(char x, int64_t rs[26]) { return rs[x - 'a']; }
+static void get_number(const char** pp, int64_t* d) {
+  const char* p = *pp;
+  int sign = 1;
+  if (*p == '-') {
+    sign = -1;
+    p++;
+  }
+  while (*p >= '0' && *p <= '9') {
+    *d = *d * 10 + *p - '0';
+    p++;
+  }
+  *d *= sign;
+  *pp = p;
+}
 
-std::pair<int64_t, int64_t> day18(line_view) { return {0, 0}; }
+static int64_t get_number(const char* p, int64_t rs[26]) {
+  int64_t d{0};
+  if (*p == '-' || (*p >= '0' && (*p <= '9'))) {
+    get_number(&p, &d);
+  } else {
+    d = get(*p, rs);
+  }
+  return d;
+}
+
+typedef void (*f18)(size_t*, const char*, const char*, int64_t rs[26], std::deque<int64_t>* qs[2]);
+
+static void snd(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  qs[0]->push_back(get(*p1, rs));
+  *i += 1;
+}
+
+static void rcv0(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  auto d = get_number(p1, rs);
+  if (d != 0) {
+    // printf("%ld\n", sounds.back());
+    *i = INT64_MAX - 1;
+  }
+  *i += 1;
+}
+
+static void rcv1(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  if (!qs[1]->empty()) {
+    auto x = qs[1]->front();
+    qs[1]->pop_front();
+    get(*p1, rs) = x;
+    *i += 1;
+  }
+}
+
+static void set(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  get(*p1, rs) = get_number(p2, rs);
+  *i += 1;
+}
+
+static void add(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  get(*p1, rs) += get_number(p2, rs);
+  *i += 1;
+}
+
+static void mul(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  get(*p1, rs) *= get_number(p2, rs);
+  *i += 1;
+}
+
+static void mod(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  get(*p1, rs) %= get_number(p2, rs);
+  *i += 1;
+}
+
+static void jgz(size_t* i, const char* p1, const char* p2, int64_t rs[26], std::deque<int64_t>* qs[2]) {
+  auto d0 = get_number(p1, rs);
+  auto d1 = get_number(p2, rs);
+  *i += d0 > 0 ? d1 : 1;
+}
+
+// static void print() {
+//   char as[] = {'i', 'a', 'p', 'f', 'b'};
+//   for (auto& a: as) {
+//     printf("[%c: %ld] ", a, get(a));
+//   }
+//   printf("\n");
+// }
+
+static size_t exec(size_t index, const std::vector<line_view>& todos, int64_t rs[26], std::deque<int64_t>* qs[2],
+                   f18 rcv) {
+  if (index < todos.size()) {
+    f18 fs[] = {snd, set, add, mul, mod, jgz, rcv};
+    const char* cs[] = {"snd", "set", "add", "mul", "mod", "jgz", "rcv"};
+    auto& todo = todos[index];
+    const char* p = todo.line;
+    auto match = [](const char* p, const char* p0) -> bool {
+      for (int i = 0; i < 3; i++) {
+        if (*(p + i) != *(p0 + i)) {
+          return false;
+        }
+      }
+      return true;
+    };
+
+    for (size_t i = 0; i < 7; i++) {
+      if (match(p, cs[i])) {
+        fs[i](&index, p + 4, p + 6, rs, qs);
+        break;
+      }
+    }
+  }
+  return index;
+}
+
+static int64_t part1(const std::vector<line_view>& todos) {
+  size_t index{0};
+  int64_t rs[26] = {0};
+  std::deque<int64_t> q;
+  std::deque<int64_t>* qs[2] = {&q, &q};
+
+  while (index < todos.size()) {
+    index = exec(index, todos, rs, qs, rcv0);
+  }
+  return q.back();
+}
+
+static void part2(const std::vector<line_view>& todos) {
+  size_t i0{0};
+  size_t i1{0};
+
+  int64_t rs0[26] = {0};
+  get('p', rs0) = 0;
+  int64_t rs1[26] = {0};
+  get('p', rs1) = 1;
+
+  std::deque<int64_t> q0;
+  std::deque<int64_t> q1;
+  std::deque<int64_t>* qs0[2] = {&q1, &q0};
+  std::deque<int64_t>* qs1[2] = {&q0, &q1};
+
+  while (i0 < todos.size() && i1 < todos.size()) {
+    i0 = exec(i0, todos, rs0, qs0, rcv1);
+    i1 = exec(i1, todos, rs1, qs1, rcv1);
+  }
+}
+
+std::pair<int64_t, int64_t> day18(line_view file) {
+  std::vector<line_view> todos;
+  per_line(file, [&todos](line_view lv) {
+    todos.push_back(lv);
+    return true;
+  });
+
+  auto t0 = part1(todos);
+  return {t0, 0};
+}
 } // namespace aoc2017
diff --git a/src/2017/day18/input0 b/src/2017/day18/input0
index e69de29..4e62dbd 100644
--- a/src/2017/day18/input0
+++ b/src/2017/day18/input0
@@ -0,0 +1,10 @@
+set a 1
+add a 2
+mul a a
+mod a 5
+snd a
+set a 0
+rcv a
+jgz a -1
+set a 1
+jgz a -2
diff --git a/test/test_2017.cpp b/test/test_2017.cpp
index 6181679..5b3a58e 100644
--- a/test/test_2017.cpp
+++ b/test/test_2017.cpp
@@ -173,15 +173,15 @@ TEST_CASE("Permutation Promenade", "[2017]") {
 TEST_CASE("Spinlock", "[2017]") {
   line_view lv = load_file("../src/2017/day17/input");
   auto p = aoc2017::day17(lv);
-  // REQUIRE(808 == p.first);
+  REQUIRE(808 == p.first);
   REQUIRE(0 == p.second);
 }
 
 
-TEST_CASE("", "[2017]") {
+TEST_CASE("Duet", "[2017]") {
   line_view lv = load_file("../src/2017/day18/input");
   auto p = aoc2017::day18(lv);
-  REQUIRE(0 == p.first);
+  REQUIRE(3423 == p.first);
   REQUIRE(0 == p.second);
 }