AOC2022 day17

main.dart

// AOC 2022, Day 17: Pyroclastic Flow
// Drop simple tetris pieces that get moved sideways by jets of air.
// Both cycle forever. Measure the height of the resulting stack.
// 1) after 2022 pieces.
// 2) after 1000000000000 pieces.
// https://dartpad.dev/?id=7be747054a44186eab0f39911a889b96
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);
}

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

typedef P = Point<int>;
// Starring, in order of appearance.
const rocks = {
  'dash': [P(0, 0), P(1, 0), P(2, 0), P(3, 0)],
  'plus': [P(1, 0), P(0, 1), P(1, 1), P(2, 1), P(1, 2)],
  'bend': [P(0, 0), P(1, 0), P(2, 0), P(2, 1), P(2, 2)],
  'pole': [P(0, 0), P(0, 1), P(0, 2), P(0, 3)],
  'cube': [P(0, 0), P(1, 0), P(0, 1), P(1, 1)],
};
late List<List<String>> grid;
var width = 7;
isInBounds(Point p) =>
    p.x.between(0, grid.first.length - 1) && p.y.between(0, grid.length - 1);

canMove(List<P> rock, P offset) =>
    rock.map((e) => e + offset).every((e) => isInBounds(e) && cellAt(e) == '.');

String cellAt(P p) => grid[p.y][p.x];
String cellAtSet(P p, String v) => grid[p.y][p.x] = v;

int solve(List<String> lines, int targetRock) {
  var shortCutRun = false;
  // Let a decent number of rows build up before checking.
  var nLinesToCheck = 50;

  var jets =
      lines.first.split('').map((e) => e == '>' ? const P(1, 0) : const P(-1, 0)).toList();
  // Generously big. Don't link this to `targetRock` because of part 2 :-)
  grid = List.generate(10000, (index) => List.generate(width, (i) => '.'));
  var topRow = -1;
  // rocks fall upwards...
  var fall = const P(0, -1);
  var rockSource = rocks.keys.iterator;
  // loop through the index rather than the values, for later cycle check.
  var jetSource = 0.to(jets.length).iterator;
  var seen = <int, List<int>>{};
  var rockCount = 0;
  var topAdd = 0;
  // loop manually to allow adjustment to rockCount for part 2
  while (true) {
    // We want to drop rock infinitely, so restart if at end.
    if (!rockSource.moveNext()) rockSource = rocks.keys.iterator..moveNext();
    var rock = rockSource.current;
    var row = topRow + 4;
    var col = 2;
    var pos = P(col, row);
    while (true) {
      // Get next jet (infinitely)
      if (!jetSource.moveNext()) {
        jetSource = 0.to(jets.length).iterator..moveNext();
      }
      var jet = jets[jetSource.current];
      // blow
      if (canMove(rocks[rock]!, pos + jet)) pos += jet;
      // can we still fall?
      if (!(canMove(rocks[rock]!, pos + fall))) {
        break;
      }
      pos += fall;
    }
    topRow = [topRow, rocks[rock]!.map((e) => e.y).max + pos.y].max;
    // ignore: avoid_function_literals_in_foreach_calls
    rocks[rock]!.forEach((e) => cellAtSet(e + pos, '#'));
    if (!shortCutRun && jetSource.current == 0 && topRow > nLinesToCheck) {
      var key = (topRow - nLinesToCheck)
          .to(topRow)
          .map((e) => grid[e].join(''))
          .join('')
          .hashCode;
      // Handle the large number of cycles in part two.
      if (!seen.containsKey(key)) {
        seen[key] = [rockCount, topRow];
      } else {
        //we have a repeat
        shortCutRun = true;

        var rDiff = rockCount - seen[key]!.first;
        var topDiff = topRow - seen[key]!.last;

        var mult = (targetRock - rockCount) ~/ rDiff;
        rockCount += rDiff * mult;
        topAdd += topDiff * mult;
        // updated rock count means we will break out of loop just below.
      }
    }
    rockCount += 1;
    if (rockCount >= targetRock) break;
  }
  return topRow + 1 + topAdd;
}

part1(List<String> lines) => solve(lines, 2022);

part2(List<String> lines) => solve(lines, 1000000000000);

var testdata = r""">>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>""".split('\n');

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