4 files changed, 109 insertions, 5 deletions
diff --git a/src/2016/day16/README.md b/src/2016/day16/README.md
index e69de29..108e75c 100644
--- a/src/2016/day16/README.md
+++ b/src/2016/day16/README.md
@@ -0,0 +1,56 @@
+--- Day 16: Dragon Checksum ---
+
+You're done scanning this part of the network, but you've left traces of your presence. You need to overwrite some disks with random-looking data to cover your tracks and update the local security system with a new checksum for those disks.
+
+For the data to not be suspicious, it needs to have certain properties; purely random data will be detected as tampering. To generate appropriate random data, you'll need to use a modified dragon curve.
+
+Start with an appropriate initial state (your puzzle input). Then, so long as you don't have enough data yet to fill the disk, repeat the following steps:
+
+    Call the data you have at this point "a".
+    Make a copy of "a"; call this copy "b".
+    Reverse the order of the characters in "b".
+    In "b", replace all instances of 0 with 1 and all 1s with 0.
+    The resulting data is "a", then a single 0, then "b".
+
+For example, after a single step of this process,
+
+    1 becomes 100.
+    0 becomes 001.
+    11111 becomes 11111000000.
+    111100001010 becomes 1111000010100101011110000.
+
+Repeat these steps until you have enough data to fill the desired disk.
+
+Once the data has been generated, you also need to create a checksum of that data. Calculate the checksum only for the data that fits on the disk, even if you generated more data than that in the previous step.
+
+The checksum for some given data is created by considering each non-overlapping pair of characters in the input data. If the two characters match (00 or 11), the next checksum character is a 1. If the characters do not match (01 or 10), the next checksum character is a 0. This should produce a new string which is exactly half as long as the original. If the length of the checksum is even, repeat the process until you end up with a checksum with an odd length.
+
+For example, suppose we want to fill a disk of length 12, and when we finally generate a string of at least length 12, the first 12 characters are 110010110100. To generate its checksum:
+
+    Consider each pair: 11, 00, 10, 11, 01, 00.
+    These are same, same, different, same, different, same, producing 110101.
+    The resulting string has length 6, which is even, so we repeat the process.
+    The pairs are 11 (same), 01 (different), 01 (different).
+    This produces the checksum 100, which has an odd length, so we stop.
+
+Therefore, the checksum for 110010110100 is 100.
+
+Combining all of these steps together, suppose you want to fill a disk of length 20 using an initial state of 10000:
+
+    Because 10000 is too short, we first use the modified dragon curve to make it longer.
+    After one round, it becomes 10000011110 (11 characters), still too short.
+    After two rounds, it becomes 10000011110010000111110 (23 characters), which is enough.
+    Since we only need 20, but we have 23, we get rid of all but the first 20 characters: 10000011110010000111.
+    Next, we start calculating the checksum; after one round, we have 0111110101, which 10 characters long (even), so we continue.
+    After two rounds, we have 01100, which is 5 characters long (odd), so we are done.
+
+In this example, the correct checksum would therefore be 01100.
+
+The first disk you have to fill has length 272. Using the initial state in your puzzle input, what is the correct checksum?
+
+Your puzzle input is 11110010111001001.
+
+--- Part Two ---
+
+The second disk you have to fill has length 35651584. Again using the initial state in your puzzle input, what is the correct checksum for this disk?
+
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
diff --git a/src/2016/day16/aoc.h b/src/2016/day16/aoc.h
index af6267b..605eb88 100644
--- a/src/2016/day16/aoc.h
+++ b/src/2016/day16/aoc.h
@@ -3,5 +3,5 @@
 #include <vector>
 
 namespace aoc2016 {
-std::pair<int64_t, int64_t> day16(line_view);
+std::pair<std::string, std::string> day16(line_view);
 }
diff --git a/test/test_2016.cpp b/test/test_2016.cpp
index 658acce..97c6fc0 100644
--- a/test/test_2016.cpp
+++ b/test/test_2016.cpp
@@ -146,11 +146,11 @@ TEST_CASE("Timing is Everything", "[2016]") {
 }
 
 
-TEST_CASE("", "[2016]") {
+TEST_CASE("Dragon Checksum", "[2016]") {
   line_view lv = load_file("../src/2016/day16/input");
   auto p = aoc2016::day16(lv);
-  REQUIRE(0 == p.first);
-  REQUIRE(0 == p.second);
+  REQUIRE("01110011101111011" == p.first);
+  REQUIRE("11001111011000111" == p.second);
 }