Dart

I just mapped the filesystem onto a list holding value at each block (with -1 for spaces), and manipulated that.

It’s slow, but it’s honest work.

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

List<int> parse(List<String> lines) => lines.first
    .split('')
    .map(int.parse)
    .mapIndexed((i, e) => List.filled(e, (i.isOdd ? -1 : i ~/ 2)))
    .reduce((s, t) => s + t);

part1(List<String> lines) {
  var fs = parse(lines);
  var i = 0;
  while ((i = fs.indexOf(-1)) >= 0) {
    while (fs.last == -1) {
      fs.removeLast();
    }
    fs[i] = fs.removeLast();
  }
  return fs.mapIndexed((i, e) => i * e).sum;
}

Function eq = const ListEquality().equals;
part2(List<String> lines) {
  var fs = parse(lines);
  for (var target in 1.to(fs.max + 1).reversed) {
    var index = fs.indexOf(target);
    var length = fs.sublist(index).takeWhile((e) => e == target).length;
    var sseq = List.filled(length, -1);
    var space = fs
        .indices()
        .where((e) => e < index)
        .firstWhereOrNull((i) => eq(fs.sublist(i, i + length), sseq));
    if (space == null) continue;
    // Copy the file, clear old location.
    fs.replaceRange(space, space + length, List.filled(length, target));
    fs.replaceRange(index, index + length, List.filled(length, -1));
  }
  return fs.mapIndexed((i, e) => i * max(e, 0)).sum;
}

Updated version

Massive speedup from implementing a modified Knuth–Morris–Pratt algorithm -> around 0.5sec runtime for part 2.

I really don’t understand why efficiently matching a sublist isn’t a builtin function. Implementing it manually was half an hour of unneeded head-scratching.

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

List<int> parse(List<String> lines) => lines.first
    .split('')
    .map(int.parse)
    .mapIndexed((i, e) => List.filled(e, (i.isOdd ? -1 : i ~/ 2)))
    .flattened
    .toList();

part1(List<String> lines) {
  var fs = parse(lines);
  var i = 0;
  while ((i = fs.indexOf(-1)) >= 0) {
    while (fs.last == -1) {
      fs.removeLast();
    }
    fs[i] = fs.removeLast();
  }
  return fs.mapIndexed((i, e) => i * e).sum;
}

part2(List<String> lines) {
  var fs = parse(lines);
  for (var target in 1.to(fs.max + 1).reversed) {
    var index = fs.indexOf(target);
    var length = fs.skip(index).takeWhile((e) => e == target).length;
    int? space = findSpace(index, length, fs);
    if (space == null) continue;
    // Copy the file, clear old location.
    fs.setRange(space, space + length, List.filled(length, target));
    fs.setRange(index, index + length, List.filled(length, -1));
  }
  return fs.mapIndexed((i, e) => i * max(e, 0)).sum;
}

/// Knuth–Morris–Pratt algorithm
int? findSpace(int limit, int length, List<int> fs) {
  for (var si = 0; si < limit - length + 1; si++) {
    if (fs[si] != -1) continue;
    var match = true;
    for (var ssi in 0.to(length)) {
      if (fs[si + ssi] != -1) {
        si += ssi;
        match = false;
        break;
      }
    }
    if (match) return si;
  }
  return null;
}