#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 = 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));
}

size_t one_beacon(int range, std::vector<sensor>& ss) {
  for (int y = 0; y <= range; y++) {
    if (y % 10000 == 0) {
      printf("%d\n", y);
    }
    std::vector<line> ls;
    int x = 0;
    while (x <= range) {
      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());
    auto m = merge(ls);
    if (m.size() > 1) {
      pos p{m[0].p1.x+1, y};
      if (sensor::beacons.find(p) == sensor::beacons.end()) {
          printf("%d %d\n", m[0].p1.x+1, y);
          return ((size_t) m[0].p1.x+1) * range + y;
      }
    }
  }
  return 0;
}

std::pair<int, int> 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