AOC2022 day15

readme.md

AOC2022 day15

Created with <3 with dartpad.dev.

main.dart

/// 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.
/// https://dartpad.dev/?id=e7a65ba0de0eaf3af0e5047993a1db07
import 'dart:math';

// import 'package:more/more.dart';
extension IntegerRangeExtension on int {
  List<int> to(int end, {int step = 1}) =>
      List.generate((end - this + (step - 1)) ~/ step, (i) => i * step + this);
}

extension MathNumberExtension on num {
  bool between(num min, num max) => min <= this && this <= max;
}

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 = <List<int>>{};
addCover(List<int> c) {
  // Consolidate any overlapping covers.
  for (var t in covers.toList()) {
    if (c.last < t.first - 1 || c.first > t.last + 1) continue;
    covers.remove(t);
    c = [min(c.first, t.first), max(c.last, t.last)];
  }
  covers.add(c);
}

/// Identify which ranges are covered on the given line (y=??),
/// consolidating any overlaps.
void buildCovers(int y) {
  covers = <List<int>>{};
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]!;
    var halfWidth = d - (s.y - y).abs();
    if (halfWidth < 0) continue;
    var r = [s.x - halfWidth, s.x + halfWidth];
    addCover(r);
  }
}

/// For the given line, build up a map of coverages
/// of each sensor. Remove any known beacons,
/// what's left is the places a beacon cannot be.
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.last - c.first + 1;
    // Remove any known beacons.
    for (var b in bs) {
      if (b.x.between(c.first, c.last - 1)) seen -= 1;
    }
  }
  return seen;
}

const 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 just *one* cell to
// be not covered, it must be at the intersection of a pair of these lines.
int part2(int size, List<String> lines) {
  addLines(lines);
  var edges = <List<int>>{};
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]! + 1;
    for (var offi in 0.to(os.length - 2)) {
      var off = os.sublist(offi, offi + 2);
      var p1 = s + off.first * d;
      var p2 = s + off.last * d;
      // Lines are at +/-45°, so defined by y = (+/-1)x + b
      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));
      }
    }
  }
  // We only want those out of range of all beacons.
  for (var s in sensorRanges.keys) {
    var d = sensorRanges[s]!;
    intersections = intersections.where((e) => dist(s, e) > d).toSet();
  }
  if (intersections.length != 1) return -1;
  return intersections.map((e) => e.x * 4000000 + e.y).first;
}

var testdata = r"""Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3"""
    .split('\n');

void main(List<String> args) {
  var dt = DateTime.now();
  assert(part1(10, testdata) == 26);
  assert(part2(20, testdata) == 56000011);
  var rt = DateTime.now().difference(dt).inMilliseconds;
  print('tests succeeded in $rt ms');
}