AOC2021 Day22

/// Turn 3x3x3 blocks of light on and off as instructed.
/// First limited to -50 to 50 in each direction.
/// Then it most definitely isn't :-(
import 'dart:io';
import 'package:vector_math/vector_math.dart';
import 'package:collection/collection.dart';

var mind = -50, maxd = 50;

var nre = RegExp(r'[^0-9-]+');

/// Obsolete semi-naive approach for part 1.
// runLine1(String s, Set<Vector3> grid) {
//   //on x=10..12,y=10..12,z=10..12
//   var c = s.split(nre).skip(1).map(double.parse).toList();
//   var on = s[1] == 'n';
//   for (var x in c[0].to(c[1] + 1)) {
//     if (x < mind || x > maxd) continue;
//     for (var y in c[2].to(c[3] + 1)) {
//       if (y < mind || y > maxd) continue;
//       for (var z in c[4].to(c[5] + 1)) {
//         if (z < mind || z > maxd) continue;
//         var v = Vector3(x, y, z);
//         //if (!safe(v)) continue;
//         if (on) {
//           grid.add(v);
//         } else {
//           grid.remove(v);
//         }
//       }
//     }
//   }
// }

/// A Cuboid is defined by its lower left front corner and its
/// upper right back corner. If it intersects with another cuboid
/// we can cleave it along each of the planes of that intersection.
class Cuboid {
  late Vector3 lo;
  late Vector3 hi;
  late bool on;
  var overlaps = <Cuboid>[];
  Cuboid(this.lo, this.hi, this.on);
  @override
  toString() => '[$lo $hi]';

  @override
  get hashCode => Object.hash(lo, hi);

  @override
  bool operator ==(Object other) =>
      other is Cuboid && other.lo == lo && other.hi == hi;

  bool overlapsWith(Cuboid other) =>
      (other.hi.x >= lo.x && other.lo.x <= hi.x) &&
      (other.hi.y >= lo.y && other.lo.y <= hi.y) &&
      (other.hi.z >= lo.z && other.lo.z <= hi.z);

  bool isIn(p0, p1, p2) => p0 >= p1 && p0 <= p2;

  bool get isEmpty => lo.x > hi.x || lo.y > hi.y || lo.z > hi.z;

  Cuboid? cleaveOnLeftAt(double x) {
    if (!isIn(x, lo.x, hi.x)) return null;
    Cuboid n = Cuboid(Vector3(lo.x, lo.y, lo.z), Vector3(x, hi.y, hi.z), true);
    lo.x = x + 1;
    return n;
  }

  Cuboid? cleaveOnRightAt(double x) {
    if (!isIn(x, lo.x, hi.x)) return null;
    Cuboid n = Cuboid(Vector3(x, lo.y, lo.z), Vector3(hi.x, hi.y, hi.z), true);
    hi.x = x - 1;
    return n;
  }

  Cuboid? cleaveOnBottomAt(double y) {
    if (!isIn(y, lo.y, hi.y)) return null;
    Cuboid n = Cuboid(Vector3(lo.x, lo.y, lo.z), Vector3(hi.x, y, hi.z), true);
    lo.y = y + 1;
    return n;
  }

  Cuboid? cleaveOnTopAt(double y) {
    if (!isIn(y, lo.y, hi.y)) return null;
    Cuboid n = Cuboid(Vector3(lo.x, y, lo.z), Vector3(hi.x, hi.y, hi.z), true);
    hi.y = y - 1;
    return n;
  }

  Cuboid? cleaveOnFrontAt(double z) {
    if (!isIn(z, lo.z, hi.z)) return null;
    Cuboid n = Cuboid(Vector3(lo.x, lo.y, lo.z), Vector3(hi.x, hi.y, z), true);
    lo.z = z + 1;
    return n;
  }

  Cuboid? cleaveOnBackAt(double z) {
    if (!isIn(z, lo.z, hi.z)) return null;
    Cuboid n = Cuboid(Vector3(lo.x, lo.y, z), Vector3(hi.x, hi.y, hi.z), true);
    hi.z = z - 1;
    return n;
  }

  List<Cuboid> gatherShards(Cuboid other) {
    var rs = <Cuboid>[];
    Cuboid? t = cleaveOnLeftAt(other.lo.x - 1);
    if (t != null) rs.add(t);
    if (isEmpty) return rs;

    t = cleaveOnRightAt(other.hi.x + 1);
    if (t != null) rs.add(t);
    if (isEmpty) return rs;

    t = cleaveOnBottomAt(other.lo.y - 1);
    if (t != null) rs.add(t);
    if (isEmpty) return rs;

    t = cleaveOnTopAt(other.hi.y + 1);
    if (t != null) rs.add(t);
    if (isEmpty) return rs;

    t = cleaveOnFrontAt(other.lo.z - 1);
    if (t != null) rs.add(t);
    if (isEmpty) return rs;

    t = cleaveOnBackAt(other.hi.z + 1);
    if (t != null) rs.add(t);

    return rs;
  }
}

runLine2(List<String> lines) {
  //on x=10..12,y=10..12,z=10..12
  var rs = <Cuboid>[];
  for (var l in lines) {
    var on = l[1] == 'n';
    var c = l.split(nre).skip(1).map(double.parse).toList();
    var v0 = Vector3(c[0], c[2], c[4]);
    var v1 = Vector3(c[1], c[3], c[5]);
    var r = Cuboid(v0, v1, on);
    // We only save ranges of 'on' lights. We use 'off' ranges to split those
    // 'on' ranges.
    if (on) {
      rs.add(r);
      continue;
    }
    // We have an off.
    for (var re in rs.toList() /*copy*/) {
      if (!re.overlapsWith(r)) continue;
      // We will save all the good parts, so remove the stub
      rs.remove(re);
      rs.addAll(re.gatherShards(r));
    }
  }
  return rs;
}

/// Count how many lights should be on. Many of the cuboids will overlap,
/// so we need to find those overlaps and deal with them. I use the same
/// approach as above: cleave the cuboids at the intersection planes and
/// collect the (up to 6, but normally 1) resulting cuboids.
int countOn(List<Cuboid> cubes) {
  var dirtys = cubes.skip(1).toList();
  var cleans = [cubes.first];
  while (dirtys.isNotEmpty) {
    //print(dirtys.length);
    var dirty = dirtys.removeLast();
    if (cleans.none((c) => c.overlapsWith(dirty))) {
      cleans.add(dirty);
      continue;
    }
    // Find an overlap, and gather the shards
    var clean = cleans.firstWhere((c) => c.overlapsWith(dirty));
    dirtys.addAll(dirty.gatherShards(clean));
  }
  return cleans
      .map((c) =>
          (c.hi.x - c.lo.x + 1) * (c.hi.y - c.lo.y + 1) * (c.hi.z - c.lo.z + 1))
      .sum
      .toInt();
}

main() {
  var lines = File('data/data22_01.txt').readAsLinesSync();
  var t = DateTime.now();
  var cubes = runLine2(lines.take(20).toList()); // initialisation region
  print(countOn(cubes)); // 596598
  cubes = runLine2(lines);
  print(countOn(cubes)); // 1199121349148621
  print('${DateTime.now().difference(t).inMilliseconds} milliseconds');
}