2016 day16

1 files changed, 49 insertions, 1 deletions

diff --git a/src/2016/day16/aoc.cpp b/src/2016/day16/aoc.cpp
index 75bc430..5bcc6e9 100644
--- a/src/2016/day16/aoc.cpp
+++ b/src/2016/day16/aoc.cpp
@@ -2,5 +2,53 @@
 
 namespace aoc2016 {
 
-std::pair<int64_t, int64_t> day16(line_view) { return {0, 0}; }
+static void reverse(std::string& s) {
+  size_t b = 0;
+  size_t e = s.size() - 1;
+  while (b < e) {
+    std::swap(s.at(b), s.at(e));
+    b++;
+    e--;
+  }
+}
+
+static void replace(std::string& s) {
+  char s2[] = {'1', '0'};
+  for (size_t i = 0; i < s.size(); i++) {
+    s.at(i) = s2[(int)s.at(i) - '0'];
+  }
+}
+
+static std::string take(const std::string& s, size_t n) { return n < s.size() ? std::string{s.data(), n} : s; }
+
+static std::string checksum(const std::string& s) {
+  std::string x;
+  char s2[] = {'0', '1'};
+  for (size_t i = 0; i < s.size() - 1; i += 2) {
+    x.push_back(s2[(int)s.at(i) == s.at(i + 1)]);
+  }
+  return x;
+}
+
+std::string checksum(std::string s, size_t max) {
+  while (s.length() < max) {
+    std::string a{s};
+    reverse(a);
+    replace(a);
+    s.push_back('0');
+    s.append(a);
+  }
+  s = take(s, max);
+
+  auto chk = checksum(s);
+  while ((chk.size() & 1) == 0) {
+    chk = checksum(chk);
+  }
+  return chk;
+}
+
+std::pair<std::string, std::string> day16(line_view) {
+  std::string init{"11110010111001001"};
+  return {checksum(init, 272), checksum(init, 35651584)};
+}
 } // namespace aoc2016