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

namespace aoc2016 {

void bfs(maze::pos p, maze& m, std::map<maze::pos, int>& ds) {
  ds.insert({p, 0});
  std::deque<maze::pos> q;
  q.push_back(p);

  while (!q.empty()) {
    auto s = q.size();
    while (s-- > 0) {
      maze::pos p0 = q.front();
      q.pop_front();

      maze::pos ns[4] = {
          {p0.x - 1, p0.y},
          {p0.x + 1, p0.y},
          {p0.x, p0.y - 1},
          {p0.x, p0.y + 1},
      };
      auto& d = ds[p0];
      for (auto& n : ns) {
        if (m.get(n.x, n.y) != '#') {
          auto px = ds.insert({n, d + 1});
          if (px.second) {
            q.push_back(n);
          }
          if (!px.second && px.first->second > d + 1) {
            px.first->second = d + 1;
            q.push_back(n);
          }
        }
      }
    }
  }

  auto& ns = m.numbers;
  for (auto it = ds.begin(); it != ds.end();) {
    if (ns.find(it->first) == ns.end()) {
      it = ds.erase(it);
    } else {
      it++;
    }
  }
}

int to0(int i, maze& mz, const std::vector<std::map<maze::pos, int>>& vds) {
  auto& m = vds[i];
  for (auto& kv : m) {
    if (mz.get(kv.first.x, kv.first.y) == '0') {
      return kv.second;
    }
  }
  return INT32_MAX;
}

struct mdistance {
  int d0 = INT32_MAX;
  int d1 = INT32_MAX;
};

void shortest_route(int i, int total, std::set<int> selected, size_t max, maze& mz,
                    const std::vector<std::map<maze::pos, int>>& vds, mdistance* shortest) {
  selected.insert(i);
  if (selected.size() == max) {
    if (shortest->d0 > total) {
      shortest->d0 = total;
    }
    int t0 = to0(i, mz, vds);
    if (shortest->d1 > total + t0) {
      shortest->d1 = total + t0;
    }
  } else {
    for (auto& kv : vds[i]) {
      int n = mz.get(kv.first.x, kv.first.y) - '0';
      if (selected.find(n) == selected.end()) {
        shortest_route(n, total + kv.second, selected, max, mz, vds, shortest);
      }
    }
  }
}

std::pair<int64_t, int64_t> day24(line_view file) {
  maze mz{179, 43}; // input
  // maze mz{11, 5}; // demo
  int r{0};
  per_line(file, [&r, &mz](line_view lv) {
    mz.load(r++, lv);
    return true;
  });

  std::vector<std::map<maze::pos, int>> vds;
  constexpr int max = 8; // input
  // constexpr int max = 5; // demo
  vds.resize(max);
  for (auto& n : mz.numbers) {
    int i = mz.get(n.x, n.y) - '0';
    auto& ds = vds[i];
    bfs(n, mz, ds);
  }

  mdistance shortest[max];
  for (size_t i = 0; i < vds.size(); i++) {
    std::set<int> selected;
    shortest_route(i, 0, selected, max, mz, vds, &shortest[i]);
  }

  // for (auto s : shortest) {
  //   printf("%d %d\n", s.d0, s.d1);
  // }

  // for (auto& ds : vds) {
  //   for (auto& kv : ds) {
  //     printf("(%c: %d) ", mz.get(kv.first.x, kv.first.y), kv.second);
  //   }
  //   printf("\n");
  // }

  // mz.print();
  // for (auto& p : mz.numbers) {
  //   printf("%c: (%d, %d)\n", mz.get(p.x, p.y), p.x, p.y);
  // }
  return {shortest[0].d0, shortest[0].d1};
}
} // namespace aoc2016