Dart

I knew keeping my search code from day 16 would come in handy, I just didn’t expect it to be so soon.

For Part 2 it finds that same path (laziness on my part), then does a simple binary chop to home in on the last valid path. (was then searches for the first block that will erm block that path, and re-runs the search after that block has dropped, repeating until blocked. Simple but okay. )

90 lines, half of which is my copied search method. Runs in a couple of seconds which isn’t great, but isn’t bad. Binary chop dropped it to 200ms.

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

var d4 = <Point<num>>[Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];

solve(List<String> lines, int count, Point end, bool inPart1) {
  var blocks = (lines
      .map((e) => e.split(',').map(int.parse).toList())
      .map((p) => Point<num>(p[0], p[1]))).toList();
  var blocksSofar = blocks.take(count).toSet();
  var start = Point(0, 0);
  Map<Point, num> fNext(Point here) => {
        for (var d in d4
            .map((d) => d + here)
            .where((e) =>
                e.x.between(start.x, end.x) &&
                e.y.between(start.y, end.y) &&
                !blocksSofar.contains(e))
            .toList())
          d: 1
      };

  int fHeur(Point here) => 1;
  bool fAtEnd(Point here) => here == end;
  var cost = aStarSearch<Point>(start, fNext, fHeur, fAtEnd);

  if (inPart1) return cost.first;
  var lo = count, hi = blocks.length;
  while (lo <= hi) {
    var mid = (lo + hi) ~/ 2;
    blocksSofar = blocks.take(mid).toSet();
    cost = aStarSearch<Point>(start, fNext, fHeur, fAtEnd);
    (cost.first > 0) ? lo = mid + 1 : hi = mid - 1;
  }
  var p = blocks[lo - 1];
  return '${p.x},${p.y}';
}

part1(lines, count, end) => solve(lines, count, end, true);
part2(lines, count, end) => solve(lines, count, end, false);

/// Returns cost to destination, plus list of routes to destination.
/// Does Dijkstra/A* search depending on whether heuristic returns 1 or
/// something better.
(num, List<List<T>>) aStarSearch<T>(T start, Map<T, num> Function(T) fNext,
    int Function(T) fHeur, bool Function(T) fAtEnd,
    {multiplePaths = false}) {
  var cameFrom = SetMultimap<T, T>.fromEntries([MapEntry(start, start)]);

  var ends = <T>{};
  var front = PriorityQueue<T>((a, b) => fHeur(a).compareTo(fHeur(b)))
    ..add(start);
  var cost = <T, num>{start: 0};
  while (front.isNotEmpty) {
    var here = front.removeFirst();
    if (fAtEnd(here)) {
      ends.add(here);
      continue;
    }
    var ns = fNext(here);
    for (var n in ns.keys) {
      var nCost = cost[here]! + ns[n]!;
      if (!cost.containsKey(n) || nCost < cost[n]!) {
        cost[n] = nCost;
        front.add(n);
        cameFrom.removeAll(n);
        cameFrom[n].add(here);
      }
      if (multiplePaths && cost[n] == nCost) cameFrom[n].add(here);
    }
  }

  Iterable<List<T>> routes(T h) sync* {
    if (h == start) {
      yield [h];
      return;
    }
    for (var p in cameFrom[h]) {
      yield* routes(p).map((e) => e + [h]);
    }
  }

  if (ends.isEmpty) return (-1, []);
  var minCost = ends.map((e) => cost[e]!).min;
  ends = ends.where((e) => cost[e]! == minCost).toSet();
  return (minCost, ends.fold([], (s, t) => s..addAll(routes(t).toList())));
}