2016 day14 part1

3 files changed, 99 insertions, 2 deletions

diff --git a/src/2016/day13/aoc.cpp b/src/2016/day13/aoc.cpp
index b14d03e..994bb83 100644
--- a/src/2016/day13/aoc.cpp
+++ b/src/2016/day13/aoc.cpp
@@ -44,7 +44,7 @@ int64_t bfs(pos start, pos end, int64_t favorite, std::set<pos>& visited) {
         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) {
+            if (it == visited.end() || it->n > p.n) {
               q.push_back(p);
             }
           }
diff --git a/src/2016/day14/README.md b/src/2016/day14/README.md
index e69de29..b9a680c 100644
--- a/src/2016/day14/README.md
+++ b/src/2016/day14/README.md
@@ -0,0 +1,25 @@
+--- Day 14: One-Time Pad ---
+
+In order to communicate securely with Santa while you're on this mission, you've been using a one-time pad that you generate using a pre-agreed algorithm. Unfortunately, you've run out of keys in your one-time pad, and so you need to generate some more.
+
+To generate keys, you first get a stream of random data by taking the MD5 of a pre-arranged salt (your puzzle input) and an increasing integer index (starting with 0, and represented in decimal); the resulting MD5 hash should be represented as a string of lowercase hexadecimal digits.
+
+However, not all of these MD5 hashes are keys, and you need 64 new keys for your one-time pad. A hash is a key only if:
+
+    It contains three of the same character in a row, like 777. Only consider the first such triplet in a hash.
+    One of the next 1000 hashes in the stream contains that same character five times in a row, like 77777.
+
+Considering future hashes for five-of-a-kind sequences does not cause those hashes to be skipped; instead, regardless of whether the current hash is a key, always resume testing for keys starting with the very next hash.
+
+For example, if the pre-arranged salt is abc:
+
+    The first index which produces a triple is 18, because the MD5 hash of abc18 contains ...cc38887a5.... However, index 18 does not count as a key for your one-time pad, because none of the next thousand hashes (index 19 through index 1018) contain 88888.
+    The next index which produces a triple is 39; the hash of abc39 contains eee. It is also the first key: one of the next thousand hashes (the one at index 816) contains eeeee.
+    None of the next six triples are keys, but the one after that, at index 92, is: it contains 999 and index 200 contains 99999.
+    Eventually, index 22728 meets all of the criteria to generate the 64th key.
+
+So, using our example salt of abc, index 22728 produces the 64th key.
+
+Given the actual salt in your puzzle input, what index produces your 64th one-time pad key?
+
+Your puzzle input is jlmsuwbz.
diff --git a/src/2016/day14/aoc.cpp b/src/2016/day14/aoc.cpp
index c46c374..dc49f69 100644
--- a/src/2016/day14/aoc.cpp
+++ b/src/2016/day14/aoc.cpp
@@ -1,6 +1,78 @@
 #include "aoc.h"
+#include "md5.h"
+#include <map>
+#include <set>
 
 namespace aoc2016 {
 
-std::pair<int64_t, int64_t> day14(line_view) { return {0, 0}; }
+static std::map<char, std::set<size_t>> has3s;
+static std::map<char, std::set<size_t>> has5s;
+
+static bool is_equal(const char* p0, const char* p1) {
+  while (p0 < p1) {
+    if (*p0 != *p1) {
+      return false;
+    }
+    p0++;
+  }
+  return true;
+}
+
+const char* has(const char* md5, int n) {
+  const char* p = md5;
+  while (p < md5 + 32 - n + 1) {
+    if (is_equal(p, p + n - 1)) {
+      return p;
+    }
+    p++;
+  }
+  return nullptr;
+}
+
+struct md5_property {
+  std::string md5;
+  char c3 = 0;
+  char c5 = 0;
+};
+
+static void insert(char c, size_t index, std::map<char, std::set<size_t>>& hs) {
+  auto p = hs.insert({c, {index}});
+  if (!p.second) {
+    p.first->second.insert(index);
+  }
+}
+
+md5_property md5(const char* secret, size_t index) {
+  static std::vector<md5_property> md5s;
+  if (index >= md5s.size()) {
+    char buf[128] = {0};
+    int l = strlen(secret);
+    memcpy(buf, secret, l);
+    auto s = md5s.size();
+    md5s.resize(index + 1);
+    for (size_t i = s; i < md5s.size(); i++) {
+      sprintf(buf + l, "%zu", index);
+      md5s[i].md5 = std::string(md5sum(buf), 32);
+      auto pc3 = has(md5s[i].md5.c_str(), 3);
+      if (pc3 != nullptr) {
+        md5s[i].c3 = *pc3;
+        insert(*pc3, index, has3s);
+      }
+      auto pc5 = has(md5s[i].md5.c_str(), 5);
+      if (pc5 != nullptr) {
+        md5s[i].c5 = *pc5;
+        insert(*pc5, index, has5s);
+      }
+    }
+  }
+  return md5s[index];
+}
+
+void find_key(const char* secret, size_t index, int* count) {}
+
+std::pair<int64_t, int64_t> day14(line_view) {
+  // md5("abc", 30000);
+  md5("jlmsuwbz", 30000);
+  return {0, 0};
+}
 } // namespace aoc2016