#include "aoc.h"
#include <algorithm>

namespace aoc2022 {
typedef sensor::pos pos;
typedef sensor::line line;
typedef std::vector<std::pair<int, std::vector<line>>> vecpair;

static std::vector<line> merge(const std::vector<line>& ls) {
  std::vector<line> merged;
  if (ls.empty())
    return merged;

  merged.push_back(ls[0]);
  for (size_t i = 1; i < ls.size(); i++) {
    line& last = merged[merged.size() - 1];
    if (last.p1.x + 1 >= ls[i].p0.x) {
      last.p1.x = std::max(last.p1.x, ls[i].p1.x);
    } else {
      merged.push_back(ls[i]);
    }
  }
  return merged;
}

bool is_beacon(pos p, const std::vector<sensor>& ss) {
  for (auto& s : ss) {
    if (p == s.ps[1]) {
      return true;
    }
  }
  return false;
}

static int count(const std::vector<line>& ls, const std::vector<sensor>& ss) {
  int total{0};
  for (auto& l : ls) {
    total += l.p1.x - l.p0.x + 1;
  }
  return total;
}

static bool get_line(const std::pair<int, std::vector<line>>& ls, int y, line* l) {
  auto y0 = ls.first;
  if (y >= y0 && y < y0 + (int)ls.second.size()) {
    *l = ls.second[y - y0];
    // printf("get %d: (%d-%d)\n", y, l->p0.x, l->p1.x);
    return true;
  }
  return false;
}

int no_beacon(int y, const std::vector<sensor>& ss, const vecpair& ps) {
  std::vector<line> ls;

  for (auto& p : ps) {
    line l;
    if (get_line(p, y, &l)) {
      if (is_beacon(l.p0, ss)) {
        ls.push_back({{l.p0.x + 1, l.p0.y}, l.p1});
      } else if (is_beacon(l.p1, ss)) {
        ls.push_back({l.p0, {l.p1.x - 1, l.p1.y}});
      } else
        ls.push_back(l);
    }
  }

  std::sort(ls.begin(), ls.end());
  return count(merge(ls), ss);
}

bool check_range(int y, const std::vector<line>& ls, int range, size_t* d) {
  line l{{0, y}, {range, y}};
  for (size_t i = 0; i < ls.size() - 1; i++) {
    auto l0 = ls[i];
    auto l1 = ls[i + 1];
    auto b1 = l.p0.x >= l0.p0.x && l.p0.x <= l0.p1.x;
    auto b2 = l.p1.x >= l1.p0.x && l.p1.x <= l1.p1.x;
    // printf("%d: checking (%d,%d) with (%d,%d) and (%d,%d)\n", y, 0, range, l0.p0.x, l0.p1.x, l1.p0.x, l1.p1.x);
    if (b1 && b2) {
      // printf("%d, %d\n", l0.p1.x + 1, y);
      *d = ((size_t)l0.p1.x + 1) * range + y;
      return true;
    }
  }
  return false;
}

// static void print(const char* s, int y, const std::vector<line>& ls) {
//   for (auto& l : ls) {
//     printf("%s %d: (%d-%d)\n", s, y, l.p0.x, l.p1.x);
//   }
// }

size_t one_beacon(int range, std::vector<sensor>& ss, const vecpair& ps) {
  size_t d{0};
  for (int y = 0; y <= range; y++) {
    std::vector<line> ls;
    for (auto& p : ps) {
      line l;
      if (get_line(p, y, &l)) {
        ls.push_back(l);
      }
    }
    std::sort(ls.begin(), ls.end());
    // print("after sort", y, ls);
    auto m = merge(ls);
    // print("after merge", y, m);
    if (check_range(y, m, range, &d)) {
      return d;
    }
  }
  return d;
}

std::pair<int, size_t> day15(line_view file) {
  std::vector<sensor> ss;
  per_line(file, [&ss](line_view lv) {
    ss.emplace_back(lv);
    return true;
  });
  std::sort(ss.begin(), ss.end());
  std::vector<std::pair<int, std::vector<line>>> ps;
  for (auto& s : ss) {
    ps.emplace_back(s.lines());
  }

  auto n1 = no_beacon(2000000, ss, ps);
  auto n2 = one_beacon(4000000, ss, ps);
  return {n1, n2};
}

} // namespace aoc2022