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

namespace aoc2016 {

struct pos {
  int x;
  int y;
  int n;
  std::string* path;

  bool operator==(pos p) { return x == p.x && y == p.y; }
  friend bool operator<(pos p1, pos p2) { return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y; }
  bool isvalid() const noexcept { return x > 0 && x < 5 && y > 0 && y < 5; }
};

static pos bfs(pos p, pos target, const std::string& passcode) {
  std::deque<pos> q;
  // std::set<pos> visited;
  q.push_back(p);

  auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
  while (!q.empty()) {
    auto s = q.size();
    while (s-- > 0) {
      pos p0 = q.front();
      q.pop_front();
      if (p0 == target) {
        return p0;
      }

      pos ns[4] = {
          {p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
          {p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
          {p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
          {p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
      };

      for (size_t i = 0; i < 4; i++) {
        pos nx = ns[i];
        std::string pass{passcode};
        pass.append(*nx.path);
        char md5[33] = {0};
        memcpy(md5, md5sum((char*)pass.c_str()), 32);
        // printf("%s: %d %d %d %s\n", md5, p0.x, p0.y, p0.n, (*p0.path).c_str());
        if (nx.isvalid() && is_open(*(md5 + i))) {
          char direction[] = {'U', 'D', 'L', 'R'};
          nx.path->push_back(direction[i]);
          q.push_back(nx);
        }
      }
    }
  }

  return target;
}

static void dfs(pos p0, pos target, const std::string& passcode, int* max) {
  if (p0 == target) {
    if (*max < p0.n) {
      *max = p0.n;
    }
  } else {
    pos ns[4] = {
        {p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
        {p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
        {p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
        {p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
    };

    auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
    for (size_t i = 0; i < 4; i++) {
      pos nx = ns[i];
      std::string pass{passcode};
      pass.append(*nx.path);
      char md5[33] = {0};
      memcpy(md5, md5sum((char*)pass.c_str()), 32);
      if (nx.isvalid() && is_open(*(md5 + i))) {
        char direction[] = {'U', 'D', 'L', 'R'};
        nx.path->push_back(direction[i]);
        dfs(nx, target, passcode, max);
      }
    }
  }
}

std::pair<std::string, int64_t> day17(line_view) {
  static std::string ss[] = {"", "UNKNOWN"};
  pos b = {1, 1, 0, ss};
  pos e = {4, 4, INT32_MAX, ss + 1};

  auto p = bfs(b, e, "bwnlcvfs");
  int max{INT32_MIN};
  dfs(b, e, "bwnlcvfs", &max);

  return {*p.path, max};
}
} // namespace aoc2016