#include "aoc.h"
#include <deque>
#include <set>

namespace aoc2017 {

knot* make_knot(int n) {
  knot* k = new knot;
  k->val = 0;
  k->next = k;
  k->prev = k;
  knot* last = k;
  for (int i = 1; i < n; i++) {
    knot* n = new knot;
    n->val = i;
    last->next = n;
    n->prev = last;
    last = n;
    k->prev = last;
    last->next = k;
  }
  return k;
}

// static void print(knot* k) {
//   knot* n = k;
//   do {
//     printf("%d ", n->val);
//     n = n->next;
//   } while (n != k);
//   printf("\n");
// }

void forward(knot** k, int n) {
  knot* x = *k;
  while (n-- > 0) {
    x = x->next;
  }
  *k = x;
}

static void reverse(knot* left, knot* right, uint8_t d) {
  while (d-- > 0) {
    std::swap(left->val, right->val);
    left = left->next;
    right = right->prev;
  }
}

static void reverse(knot* head, uint8_t d) {
  knot* tail = head;
  uint8_t n = d;
  while (--n > 0) {
    tail = tail->next;
  }
  reverse(head, tail, d / 2);
}

static int skip = 0;
static void reverse_skip(knot** current, uint8_t d) {
  reverse(*current, d);
  forward(current, d + skip);
  skip += 1;
}

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';
    p++;
  }
  *pp = p;
  return d;
}

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) {
    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;
  }
}

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];
    }
  }
}

static void binary_grid(char hexdigit[33], char* grid) {
  const char* b09[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001"};
  const char* baf[] = {"1010", "1011", "1100", "1101", "1110", "1111"};

  for (int i = 0; i < 32; i++) {
    char c = hexdigit[i];
    memcpy(grid + 4 * i, c >= '0' && c <= '9' ? b09[c - '0'] : baf[c - 'a'], 4);
  }

  // printf("%s\n", binary);
}

int knot_hash(line_view file, int total, char* grid = nullptr) {
  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]);
  }

  if (grid != nullptr) {
    binary_grid(hexdigit, grid);
  }
  return 0;
}

std::pair<int64_t, int64_t> day10(line_view file) {
  knot_hash(file, 64);
  return {knot_hash_once(file), 0};
}

struct pos {
  int r;
  int c;

  friend bool operator==(pos p1, pos p2) { return p1.r == p2.r && p1.c == p2.c; }
  friend bool operator<(pos p1, pos p2) { return p1.r < p2.r ? true : p1.r > p2.r ? false : p1.c < p2.c; }
};

void floodfill(int x, pos p, char grid[128][128], int fill[128][128]) {
  std::deque<pos> q;
  q.push_back(p);

  auto is_valid = [](pos p) -> bool { return p.r >= 0 && p.r < 128 && p.c >= 0 && p.c < 128; };
  while (!q.empty()) {
    auto s = q.size();
    while (s-- > 0) {
      auto p0 = q.front();
      q.pop_front();

      fill[p0.r][p0.c] = x;

      pos ns[] = {{p0.r, p0.c + 1}, {p0.r, p0.c - 1}, {p0.r - 1, p0.c}, {p0.r + 1, p0.c}};
      for (auto& n : ns) {
        if (is_valid(n) && grid[n.r][n.c] == '1' && fill[n.r][n.c] == 0) {
          q.push_back(n);
        }
      }
    }
  }
}

std::pair<int64_t, int64_t> day14(line_view) {
  char buf[30];
  const char* key = "oundnydw";
  // const char* key = "flqrgnkx";
  char grid[128][128];
  for (int i = 0; i < 128; i++) {
    memset(buf, 0, 30);
    sprintf(buf, "%s-%d\n", key, i);
    knot_hash(buf, 64, grid[i]);
  }

  int t0{0};
  int fill[128][128] = {{0}};

  int t1{0};
  for (int r = 0; r < 128; r++) {
    for (int c = 0; c < 128; c++) {
      char x = grid[r][c];
      t0 += x - '0';
      if (x == '1' && fill[r][c] == 0) {
        floodfill(++t1, {r, c}, grid, fill);
      }
    }
  }

  return {t0, t1};
}
} // namespace aoc2017