AOC2022 day14

main.dart

/// Build a passage, then flow sand through it
/// 1) until it is "filled" - any more flows out
/// 2) until the pile reaches the source
/// https://dartpad.dev/?id=018911e7d2f3acf18878b98c80f5ddcf

import 'dart:math';
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);
}

var grid = <Point<int>>{};
void drawLines(List<String> ps) {
  for (var i in 0.to(ps.length - 1)) {
    drawLine(ps.sublist(i, i + 2));
  }
}

void drawLine(List<String> ps) {
  var l1 = ps.first.split(',').map(int.parse);
  var p1 = Point<int>(l1.first, l1.last);
  var l2 = ps.last.split(',').map(int.parse);
  var p2 = Point<int>(l2.first, l2.last);
  var d = p2 - p1;
  var pd = Point(d.x.sign, d.y.sign);
  var i = p1;
  while (i != p2) {
    grid.add(i);
    i += pd;
  }
  grid.add(p2);
}

const dropDirections = [Point(0, 1), Point(-1, 1), Point(1, 1)];
late int maxX, minX, maxY;
addLines(List<String> lines) {
  grid = <Point<int>>{};
  lines.map((e) => e.split(' -> ').toList()).forEach((e) => drawLines(e));
  maxX = grid.map((e) => e.x).max;
  minX = grid.map((e) => e.x).min;
  maxY = grid.map((e) => e.y).max;
}

const sourcePoint = Point(500, 0);

part1(List<String> lines) {
  addLines(lines);
  var s = sourcePoint;
  var grains = 0;
  nextdrop:
  while (true) {
    var sn = s;
    for (var d in dropDirections) {
      sn = s + d;
      // We've overflowed, so stop counting and return the answer.
      if (sn.x < minX || sn.x > maxX || sn.y > maxY) break nextdrop;
      // We've found a space for us to fall into, so fall into it.
      if (!grid.contains(sn)) {
        s = sn;
        break;
      }
    }
    // No spaces were found to fall into, so come to rest here, and
    // prepare the next grain.
    if (s != sn) {
      grid.add(s);
      s = sourcePoint;
      grains += 1;
    }
  }
  return grains;
}

const shade = [Point(-1, 0), Point(0, 0), Point(1, 0)];
const below = Point(0, 1);

// Find the 'shadow' cast by all the lines above, and remove this
// from the natural triangular pile.
part2(List<String> lines) {
  addLines(lines);
  maxY += 2;
  // Build list of points to check, scanning from top down.
  var ps = [
    for (var y in 1.to(maxY))
      for (var x in (500 - maxY).to(500 + maxY + 1)) Point(x, y)
  ];
  // If any point and its two neighbours are all in the shade of something,
  // the point below must also be in the shade, ie no sand can flow there.
  ps
      .where((p) => shade.every((e) => grid.contains(e + p)))
      .forEach((e) => grid.add(e + below));
  // For each row, start with maximum possible number of grains in that row,
  // then count how many are in shade and subtract that number.
  return (0.to(maxY))
      .map((y) =>
          (2 * y + 1) -
          ((500 - y).to(500 + y + 1))
              .where((x) => grid.contains(Point(x, y)))
              .length)
      .sum;
}

var testdata = r"""498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9"""
    .split('\n');

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