AOC2022 day18

readme.md

AOC2022 day18

Created with <3 with dartpad.dev.

main.dart

// AOC 2022, Day 18: Boiling Boulders
// Find the surface area of a cluster of cubes
// 1) as given
// 2) excluding interior voids
// https://dartpad.dev/?id=d7d31d6b8c9cd1c2b2fb1f4eb272e729

import 'package:collection/collection.dart';

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

const d6 = [
  Cube(1, 0, 0),
  Cube(-1, 0, 0),
  Cube(0, 1, 0),
  Cube(0, -1, 0),
  Cube(0, 0, 1),
  Cube(0, 0, -1)
];

class Cube {
  final int x, y, z;
  const Cube(this.x, this.y, this.z);
  Cube operator +(Cube other) => Cube(x + other.x, y + other.y, z + other.z);

  List<Cube> get n6 => [for (var d in d6) this + d];

  @override
  int get hashCode => Object.hash(x, y, z);
  @override
  bool operator ==(Object other) =>
      other is Cube && other.x == x && other.y == y && other.z == z;
  @override
  String toString() => '($x, $y, $z)';
}

int surfaceArea(Iterable<Cube> cubes) =>
    cubes.map((e) => e.n6.where((n) => !cubes.contains(n)).length).sum;

Set<Cube> buildCubes(List<String> lines) => lines
    .map((e) => [for (var n in e.split(',')) int.parse(n)])
    .map((e) => Cube(e[0], e[1], e[2]))
    .toSet();

part1(List<String> lines) => surfaceArea(buildCubes(lines));

part2(List<String> lines) {
  var cubes = buildCubes(lines);
  // Find the bounding box (with a padding of 1 on every side).
  dirBounds(Iterable<int> e) => (e.min - 1).to(e.max + 2);
  var bounds = (
    x: dirBounds([for (var c in cubes) c.x]),
    y: dirBounds([for (var c in cubes) c.y]),
    z: dirBounds([for (var c in cubes) c.z]),
  );

  // Note every location in the bounding box that doesn't hold a cube.
  var spaces = {
    for (var x in bounds.x)
      for (var y in bounds.y)
        for (var z in bounds.z) Cube(x, y, z)
  }.difference(cubes);

  // Propagate across all connected spaces starting
  // from the top front left.
  var q = {spaces.first};
  var seen = {spaces.first};
  while (q.isNotEmpty) {
    var here = q.first;
    q.remove(here);
    seen.add(here);
    q.addAll(here.n6.where((e) => !seen.contains(e) && spaces.contains(e)));
  }
  // Any spaces that were not seen must be internal voids. Fill them.
  cubes.addAll(spaces.where((c) => !seen.contains(c)));

  // Now this gives the required answer.
  return surfaceArea(cubes);
}

var testdata = [
  "2,2,2",
  "1,2,2",
  "3,2,2",
  "2,1,2",
  "2,3,2",
  "2,2,1",
  "2,2,3",
  "2,2,4",
  "2,2,6",
  "1,2,5",
  "3,2,5",
  "2,1,5",
  "2,3,5"
];

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