AOC2022 day19

main.dart

// AOC 2022, Day 19: Not Enough Minerals
// Produce some machines that produce resources in a horrible network :-)
// 1) Find best results for a long list.
// 2) Now for a short list over a longer time.
// https://dartpad.dev/?id=741c3d8304eb54a167e065c0702eb38f

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 ore = 0, clay = 1, obsidian = 2, geode = 3;

class Blueprint {
  int number;
  List<List<int>> costs = [[], [], [], []];
  Blueprint(this.number, this.costs);
}

class State {
  int time;
  List<int> robots = [1, 0, 0, 0];
  List<int> stocks = [0, 0, 0, 0];
  List<bool> wasIdleInstead = [false, false, false, false];
  State(this.time);
  State.copyFrom(State other)
      : time = other.time,
        robots = other.robots.toList(),
        stocks = other.stocks.toList();

  canBuildRobot(int r, Blueprint bp) =>
      !wasIdleInstead[r] && 0.to(4).every((i) => stocks[i] >= bp.costs[r][i]);

  buildRobot(int r, Blueprint bp) {
    robots[r] += 1;
    for (var i in 0.to(4)) {
      stocks[i] -= bp.costs[r][i];
    }
  }

  @override
  int get hashCode => Object.hash(time, robots, stocks);

  @override
  bool operator ==(Object other) =>
      (other is State) &&
      time == other.time &&
      0.to(robots.length).every((e) => robots[e] == other.robots[e]) &&
      0.to(stocks.length).every((e) => stocks[e] == other.stocks[e]);
}

var debug = false;
Blueprint read(String line) {
  var reD = RegExp(r'\d+');
  var ms = reD.allMatches(line).map((m) => int.parse(m[0]!)).toList();
  return Blueprint(ms[0], [
    [ms[1], 0, 0, 0],
    [ms[2], 0, 0, 0],
    [ms[3], ms[4], 0, 0],
    [ms[5], 0, ms[6], 0]
  ]);
}

List<int> sums(List<int> a, List<int> b) =>
    [0, 1, 2, 3].map((e) => a[e] + b[e]).toList();
int getMaxGeodes(Blueprint bp, int timeLimit) {
  var best = 0;
  var q = QueueList.from([State(timeLimit)]);
  var seen = <int>{};
  while (q.isNotEmpty) {
    var curr = q.removeFirst();
    if (seen.contains(curr.hashCode)) {
      continue;
    }
    seen.add(curr.hashCode);
    if (curr.time == 0) {
      if (curr.stocks[geode] > best) {
        best = curr.stocks[geode];
      }
      continue;
    }
    // can we prune?
    //if we magically made geode bots every round, could we catch up with best?
    if (curr.stocks[geode] +
            curr.time * curr.robots[geode] +
            max((curr.time - 1) * (curr.time - 2) ~/ 2, 0) <
        best) {
      continue;
    }

    var nextState = State.copyFrom(curr)
      ..time -= 1
      ..stocks = sums(curr.stocks, curr.robots);

    // What should we build next?

    //Always build geode
    var buildGeode = curr.canBuildRobot(geode, bp);
    if (buildGeode) {
      q.add(State.copyFrom(nextState)..buildRobot(geode, bp));
    }

    // Geode >>> Obs, plus don't need too many
    var buildObs = !buildGeode &&
        curr.robots[obsidian] < bp.costs[geode][obsidian] &&
        curr.canBuildRobot(obsidian, bp);
    if (buildObs) {
      q.add(State.copyFrom(nextState)..buildRobot(obsidian, bp));
    }

    // Only build clay if we need it to feed obsidians
    var buildClay = !buildGeode &&
        !buildObs &&
        curr.robots[clay] < bp.costs[obsidian][clay] &&
        curr.canBuildRobot(clay, bp);
    if (buildClay) {
      q.add(State.copyFrom(nextState)..buildRobot(clay, bp));
    }

    // Only build clay if we need it to feed any of the others
    var buildOre = !buildGeode &&
        !buildObs &&
        // Next line based on
        // https://old.reddit.com/r/adventofcode/comments/zpihwi/2022_day_19_solutions/j0w8ujl/
        // may be data dependent
        curr.robots[clay] < 2 &&
        (curr.robots[ore] < bp.costs[geode][ore] ||
            curr.robots[ore] < bp.costs[obsidian][ore] ||
            curr.robots[ore] < bp.costs[clay][ore]) &&
        curr.canBuildRobot(ore, bp);
    if (buildOre) {
      q.add(State.copyFrom(nextState)..buildRobot(ore, bp));
    }

    // Dunno about these numbers... May be data-dependent
    var canIdle = !buildGeode &&
        (curr.stocks[ore] < 1 * bp.costs[geode][ore] ||
            curr.stocks[ore] < 1 * bp.costs[obsidian][ore] ||
            curr.stocks[ore] < 2 * bp.costs[clay][ore]) &&
        curr.stocks[clay] < 3 * bp.costs[obsidian][clay];
    if (canIdle) {
      // https://old.reddit.com/r/adventofcode/comments/zpihwi/2022_day_19_solutions/j0vvtdt/
      nextState.wasIdleInstead = [buildOre, buildClay, buildObs, buildGeode];
      q.add(nextState);
    }
  }
  return best;
}

part1(List<String> lines) =>
    lines.map(read).map((e) => getMaxGeodes(e, 24) * e.number).sum;

part2(List<String> lines) =>
    lines.take(3).map((e) => getMaxGeodes(read(e), 32)).reduce((s, t) => s * t);

var testdata = [
  "Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.",
  "Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian."
];

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