AOC 2022 Day 15

/// Sensors can see closest beacons, which means others may be out there.
/// 1) find 'clear' points on a given line.
/// 2) find only 'unclear' point in a given area.
///Sensor at x=2, y=18: closest beacon is at x=-2, y=15
import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

class Cover {
  int start, end;
  Cover(this.start, this.end);
  bool contains(int i) => i >= start && i <= end;
}

var sensorRanges = <Point<int>, int>{};
var beacons = <Point<int>>{};
int dist(Point<int> p1, Point<int> p2) =>
    (p1.x - p2.x).abs() + (p1.y - p2.y).abs();

addLines(List<String> lines) {
  sensorRanges = <Point<int>, int>{};
  beacons = <Point<int>>{};

  var re = RegExp(r'(-?\d+)');
  lines
      .map((e) => re.allMatches(e).map((m) => int.parse(m.group(1)!)).toList())
      .forEach((e) {
    var ps = Point(e[0], e[1]), pb = Point(e[2], e[3]);
    sensorRanges[ps] = dist(ps, pb);
    beacons.add(pb);
  });
}

clearCovered() {
  for (var s in sensorRanges.entries) {
    for (var t in sensorRanges.entries) {
      if (s.key == t.key) continue;
      if (t.value <= s.value - dist(s.key, t.key)) {
        sensorRanges.remove(t);
      }
    }
  }
}

var covers = <Cover>{};
addCover(Cover c) {
  for (var t in covers.toList()) {
    if (c.end < t.start - 1 || c.start > t.end + 1) continue;
    covers.remove(t);
    c = Cover(min(c.start, t.start), max(c.end, t.end));
  }
  covers.add(c);
}

void buildCovers(int y) {
  covers = <Cover>{};
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]!;
    var halfWidth = d - (s.y - y).abs();
    if (halfWidth < 0) continue;
    var r = Cover(s.x - halfWidth, s.x + halfWidth);
    addCover(r);
  }
}

part1(int y, List<String> lines) {
  addLines(lines);
  clearCovered();

  buildCovers(y);
  var seen = 0;
  var bs = beacons.where((e) => e.y == y);
  for (var c in covers) {
    seen += c.end - c.start + 1;
    for (var b in bs) {
      if (c.contains(b.x)) seen -= 1;
    }
  }
  return seen;
}

int part2(int size, List<String> lines) {
  addLines(lines);
  clearCovered();

  for (var y in 0.to(size + 1)) {
    buildCovers(y);
    if (covers.length == 1) continue;
    return covers.map((e) => e.end + 1).min * 4000000 + y;
  }
  return 0; // never!
}

var os = [Point(1, 0), Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0)];
// Find the edges just out of reach of each beacon, for jsut one cell to be
// not covered, it must be at the intersection of some of these lines.
int part2Edges(int size, List<String> lines) {
  addLines(lines);
  var edges = <List<int>>{};
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]! + 1;
    for (var off in os.window(2)) {
      var p1 = s + off.first * d;
      var p2 = s + off.last * d;
      var grad = (p2.x - p1.x) ~/ (p2.y - p1.y); // 1 or -1
      var org = p1.y - p1.x * grad;
      edges.add([grad, org]);
    }
  }

  // Build intersections.
  var intersections = <Point<int>>{};
  for (var l in edges.where((e) => e.first == 1)) {
    for (var r in edges.where((e) => e.first == -1)) {
      int x = (r.last - l.last) ~/ 2;
      int y = x * l.first + l.last;
      if (x >= 0 && x <= size && y >= 0 && y <= size) {
        intersections.add(Point(x, y));
      }
    }
  }
  // Remove any within range of a beacon.
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]!;
    for (var i in intersections.toSet()) {
      if (dist(s, i) <= d) intersections.remove(i);
    }
  }
  if (intersections.length != 1) return -1;
  return intersections.map((e) => e.x * 4000000 + e.y).first;
}