2017 day10

1 files changed, 60 insertions, 12 deletions

diff --git a/src/2017/day10/aoc.cpp b/src/2017/day10/aoc.cpp
index 8b652b1..b6b617f 100644
--- a/src/2017/day10/aoc.cpp
+++ b/src/2017/day10/aoc.cpp
@@ -37,7 +37,7 @@ void forward(knot** k, int n) {
   *k = x;
 }
 
-static void reverse(knot* left, knot* right, int d) {
+static void reverse(knot* left, knot* right, uint8_t d) {
   while (d-- > 0) {
     std::swap(left->val, right->val);
     left = left->next;
@@ -45,24 +45,24 @@ static void reverse(knot* left, knot* right, int d) {
   }
 }
 
-static void reverse(knot* head, int d) {
+static void reverse(knot* head, uint8_t d) {
   knot* tail = head;
-  int n = d;
+  uint8_t n = d;
   while (--n > 0) {
     tail = tail->next;
   }
   reverse(head, tail, d / 2);
 }
 
-static void reverse_skip(knot** current, int d) {
-  static int skip = 0;
+static int skip = 0;
+static void reverse_skip(knot** current, uint8_t d) {
   reverse(*current, d);
   forward(current, d + skip);
   skip += 1;
 }
 
-static int get_number(const char** pp) {
-  int d{0};
+static uint8_t get_number(const char** pp) {
+  uint8_t d{0};
   const char* p = *pp;
   while (*p >= '0' && *p <= '9') {
     d = d * 10 + *p - '0';
@@ -72,18 +72,66 @@ static int get_number(const char** pp) {
   return d;
 }
 
-std::pair<int64_t, int64_t> day10(line_view file) {
-  // knot* k = make_knot(5); // demo
+static int knot_hash_once(line_view file) {
   knot* k = make_knot(256);
-
   const char* p = file.line;
   knot* current = k;
+  skip = 0;
   while (p < file.line + file.length) {
-    int d = get_number(&p);
+    uint8_t d = get_number(&p);
     reverse_skip(&current, d);
     p++;
   }
+  return k->val * k->next->val;
+}
+
+static void cpy(uint8_t sparse[256], knot* k) {
+  int i{0};
+  while (i < 256) {
+    sparse[i++] = k->val;
+    k = k->next;
+  }
+}
 
-  return {k->val * k->next->val, 0};
+static void reduce(uint8_t dense[16], uint8_t sparse[256]) {
+  for (int i = 0; i < 256; i += 16) {
+    int x = i / 16;
+    for (int j = 0; j < 16; j++) {
+      dense[x] ^= sparse[i + j];
+    }
+  }
+}
+
+int knot_hash(line_view file, int total) {
+  const char trail[] = {17, 31, 73, 47, 23};
+  char* input = (char*)malloc(file.length - 1 + 5);
+  memcpy(input, file.line, file.length - 1);
+  memcpy(input + file.length - 1, trail, 5);
+  knot* k = make_knot(256);
+  knot* current = k;
+  skip = 0;
+  while (total-- > 0) {
+    for (int i = 0; i < (int)file.length - 1 + 5; i++) {
+      reverse_skip(&current, *(input + i));
+    }
+  }
+
+  uint8_t sparse[256] = {0};
+  uint8_t dense[16] = {0};
+  cpy(sparse, k);
+  reduce(dense, sparse);
+
+  char hexdigit[33] = {0};
+  for (int i = 0; i < 16; i++) {
+    sprintf(hexdigit + i * 2, "%02x", dense[i]);
+  }
+  // printf("%s\n", hexdigit);
+
+  return 0;
+}
+
+std::pair<int64_t, int64_t> day10(line_view file) {
+  knot_hash(file, 64);
+  return {knot_hash_once(file), 0};
 }
 } // namespace aoc2017