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

namespace aoc2022 {
typedef sensor::pos pos;
typedef sensor::line line;

int sensor::minx;
int sensor::maxx;
std::set<pos> sensor::beacons;

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

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

int no_beacon(int y, std::vector<sensor>& ss) {
  std::vector<line> ls;
  int x = sensor::minx;
  while (x <= sensor::maxx) {
    pos p{x, y};
    for (size_t i = 0; i < ss.size(); i++) {
      auto& s = ss[i];
      auto d1 = sensor::mdistance(s.ps[0], s.ps[1]);
      auto d2 = sensor::mdistance(s.ps[0], p);
      if (d2 <= d1) {
        auto dy = s.ps[0].y - y;
        auto x0 = s.ps[0].x + d2 - std::abs(dy);
        if (p == s.ps[1]) {
          ls.push_back({{x + 1, y}, {x0, y}});
        } else if (pos{x0, y} == s.ps[1]) {
          ls.push_back({{x, y}, {x0 - 1, y}});
        } else {
          ls.push_back({{x, y}, {x0, y}});
        }
        x = x0;
        break;
      }
    }
    x++;
  }

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

bool get_line(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;
}

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) {
  std::vector<std::pair<int, std::vector<line>>> ps;
  for (auto& s : ss) {
    ps.emplace_back(s.lines());
  }
  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());
  auto n1 = no_beacon(2000000, ss);
  auto n2 = one_beacon(4000000, ss);
  return {n1, n2};
}

} // namespace aoc2022