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

namespace aoc2022 {
typedef elf (*elf_move)(elf);
typedef bool (*elf_predicate)(elf, const std::set<elf>&);

static elf nomove(elf e) { return e; }
static elf north(elf e) { return elf{e.x, e.y - 1}; }
static elf south(elf e) { return elf{e.x, e.y + 1}; }
static elf west(elf e) { return elf{e.x - 1, e.y}; }
static elf east(elf e) { return elf{e.x + 1, e.y}; }

bool eight(elf e, const std::set<elf>& elves) {
  elf es[8] = {
      {e.x - 1, e.y - 1}, {e.x, e.y - 1},     {e.x + 1, e.y - 1}, {e.x - 1, e.y},
      {e.x + 1, e.y},     {e.x - 1, e.y + 1}, {e.x, e.y + 1},     {e.x + 1, e.y + 1},
  };
  for (auto& e : es) {
    if (elves.find(e) != elves.end()) {
      return false;
    }
  }
  return true;
}

bool north_three(elf e, const std::set<elf>& elves) {
  elf es[3] = {
      {e.x - 1, e.y - 1},
      {e.x, e.y - 1},
      {e.x + 1, e.y - 1},
  };
  for (auto& e : es) {
    if (elves.find(e) != elves.end()) {
      return false;
    }
  }
  return true;
}

bool south_three(elf e, const std::set<elf>& elves) {
  elf es[3] = {
      {e.x - 1, e.y + 1},
      {e.x, e.y + 1},
      {e.x + 1, e.y + 1},
  };
  for (auto& e : es) {
    if (elves.find(e) != elves.end()) {
      return false;
    }
  }
  return true;
}

bool west_three(elf e, const std::set<elf>& elves) {
  elf es[3] = {
      {e.x - 1, e.y - 1},
      {e.x - 1, e.y},
      {e.x - 1, e.y + 1},
  };
  for (auto& e : es) {
    if (elves.find(e) != elves.end()) {
      return false;
    }
  }
  return true;
}

bool east_three(elf e, const std::set<elf>& elves) {
  elf es[3] = {
      {e.x + 1, e.y - 1},
      {e.x + 1, e.y},
      {e.x + 1, e.y + 1},
  };
  for (auto& e : es) {
    if (elves.find(e) != elves.end()) {
      return false;
    }
  }
  return true;
}

static struct elf_test {
  elf_predicate p;
  elf_move m;
} moves[5] = {{eight, nomove}, {north_three, north}, {south_three, south}, {west_three, west}, {east_three, east}};

bool duplicate(elf e, const std::map<elf, int>& dups) {
  auto it = dups.find(e);
  return it != dups.end() && it->second > 1;
}

std::vector<elf> round(int i, const std::vector<elf>& elfs, const std::set<elf>& elves, size_t* n) {
  std::vector<elf> next;
  *n = 0;

  for (auto& e : elfs) {
    if (moves[0].p(e, elves)) {
      next.emplace_back(moves[0].m(e));
      *n += 1;
    } else {
      bool can_move{false};
      for (int x = 0; x < 4; x++) {
        int index = (i + x) % 4 + 1;
        if (moves[index].p(e, elves)) {
          next.emplace_back(moves[index].m(e));
          can_move = true;
          break;
        }
      }
      if (!can_move) {
        next.emplace_back(e);
      }
    }
  }

  std::map<elf, int> dups;
  for (auto& e : next) {
    auto kv = dups.insert({e, 1});
    if (!kv.second) {
      kv.first->second += 1;
    }
  }

  // check duplicate of next
  for(size_t i = 0; i < next.size(); i++) {
    if (duplicate(next[i], dups)) {
      next[i] = elfs[i]; // stay put
    }
  }
  return next;
}

int count(const std::vector<elf>& elfs, const std::set<elf>& elvs) {
  int minx{INT32_MAX}, miny{INT32_MAX};
  int maxx{INT32_MIN}, maxy{INT32_MIN};

  for (auto& e: elfs) {
    minx = std::min(e.x, minx);
    miny = std::min(e.y, miny);
    maxx = std::max(e.x, maxx);
    maxy = std::max(e.y, maxy);
  }

  int n{0};
  for (int y = miny; y <= maxy; y++) {
    for (int x = minx; x <= maxx; x++) {
      if (elvs.find(elf{x, y}) == elvs.end()) n++;
    }
  }
  return n;
}

std::pair<int, int> day23(line_view file) {
  int height{0};
  std::vector<elf> elfs;

  per_line(file, [&height, &elfs](line_view lv) {
    for (size_t i = 0; i < lv.length; i++) {
      if (*(lv.line + i) == '#') {
        elfs.emplace_back(elf{(int)i, height});
      }
    }
    height++;
    return true;
  });

  std::set<elf> elves{elfs.begin(), elfs.end()};

  size_t n{0};
  int r{0};
  while (r < 10 /*true*/) {
    elfs = round(r++, elfs, elves, &n);
    if (n == elfs.size()) break;
    elves.clear();
    elves = std::set<elf>{elfs.begin(), elfs.end()};
  }

  int n1 = count(elfs, elves);
  return {n1, r};
}
} // namespace aoc2022