use IO, Set, List;

iter data() {
  var x1, y1, x2, y2 = 0;
  while readf("Sensor at x=%i, y=%i: closest beacon is at x=%i, y=%i\n", x1, y1, x2, y2) {
    yield ((x1, y1), (x2, y2), abs(x1-x2) + abs(y1-y2));
  }
}

record overlapping {
  var disjoint: list(range(int));

  proc add(arg: range(int)) {
    // Don't pollute `disjoint`.
    if arg.isEmpty() then return;

    var newRng = arg;
    do {
      var merged = false;
      for (rng, i) in zip(disjoint, 0..) {
        if newRng[rng].isEmpty() then continue;
        newRng = min(rng.lowBound, newRng.lowBound)..max(rng.highBound, newRng.highBound);
        disjoint.pop(i);
        merged = true;
        break;
      }
    } while merged;
    disjoint.append(newRng);
  }

  iter these() { for rng in disjoint do yield rng; }
  proc size { return + [rng in this] rng.size; }
  proc boundedSize(bound) { return + reduce [rng in this] rng[bound].size; }
  proc contains(x) { return || reduce [rng in this] rng.contains(x); }
}

enum axis { xAxis = 0, yAxis = 1 };
proc ((int, int)).rangeAlong(axs: axis, reach: int, theXOrY: int) {
  const dim = axs : int;
  const dist = abs(this[dim]-theXOrY);

  // Too far
  if dist > reach then return 0..<0;

  // Get the range
  const remDist = max(0, reach-dist);
  return (this[1-dim]-remDist)..(this[1-dim]+remDist);
}


config const theY = 10;
const searchSpace = 0..theY * 2;
const input = data();

// Solve part 1
var overlaps: overlapping;
var occupied: set((int, int));
for (sensor, beacon, reach) in input {
  occupied.add(sensor);
  occupied.add(beacon);
  overlaps.add(sensor.rangeAlong(axis.yAxis, reach, theY));
}
writeln(overlaps.size - (+ reduce [(x,y) in occupied] if y == theY then 1));

// Solve part 2
forall checkY in searchSpace {
  var overlaps: overlapping;
  for (sensor, _, reach) in input {
    overlaps.add(sensor.rangeAlong(axis.yAxis, reach, checkY));
  }

  if overlaps.boundedSize(searchSpace) != searchSpace.size {
    // Found the y-cordinate. Now find the x-coordinate.
    for checkX in searchSpace {
      if !overlaps.contains(checkX) {
        // x-coord isn't in the interval, so we found our answer.
        writeln("x = ", checkX, ", y = ", checkY, ", frequency = ", checkX * 4000000 + checkY);
        break;
      }
    }
  }
}