Rust on a DS? What a time to be alive.

I followed the link for Spectral Decomposition, and noped right out when I saw the banner "This article may be too technical for most readers to understand."

Great list though, thanks!

1.8s now. 99% of that in Sides. I've just had an idea though... ~~maybe too late for today though!~~

edit: prepending ≡⍚(-¤⊸/↧) toFields spared me from manipulating hundreds of irrelevant 0's, so time is very good now at 55ms.

Oh, good catch. That's certainly the case if an initial value of 0 correctly generates the required value of the quine. As I'd already started running some code against the live data that's what I tested against, and so it's only when I just tested it against the example data that I saw the problem.

I have changed the for-loop to read for (var a in (top ? 1 : 0).to(8)) for maximum terseness :-)

That still works for the example and my live data, and I don't think there should be a valid solution that relies on the first triplet being 0. Thanks for your reply!

Ooh, interesting, I'll have to give that a try. Thanks!

(edit) Wow, that replaced my three lines of overly complex code without a hitch. classify is an operator I never really got the point of before. Beautiful.

Data ← ⊜∘⊸≠@\n "AAAA\nBBCD\nBBCC\nEEEC"
N₄     ← [¯1_0 1_0 0_¯1 0_1]               # Four orthogonal neighbours.
Fences ← /+≡(/+=0⬚0⊡+N₄¤)⊙¤⊚.°⊚            # Fences for a field, by looking for edges.
Cs     ← [0 1 1 0 1 0 2 1 1 2 0 1 0 1 1 0] # Number of corners keyed by bitarray of 2x2 grid.
Sides  ← /+/+⧈(⊡:Cs°⋯♭)2_2⌝↘¯1_¯1⌝↘1_1°⊚   # Add border, look for corners in 2x2 windows.

Fields ← ⊜□:⇡△.+1⍜♭⊛Data

/+×≡◇⊃⧻Fences Fields
/+×≡◇⊃⧻Sides Fields

Dart

Part one was an exercise in building a simple OpCode machine. Part two was trickier. It was clear that the a register was repeatedly being divided by 8, and testing a few values showed that each 3-bits of the initial value defined one entry in the output, so I built a recursive routine that brute-forced each one in turn. Only <1ms to run though, so not that brutal.

(It's worth pointing out that at some stages multiple 3-bit values gave rise to the required value, causing a failure to resolve later on if not checked.)

(edit: for-loop in buildQuine now avoids using a 0 for the initial triplet, as this should not be a valid value, and if it turns out to generate the required digit of the quine, you will get an infinite recursion. Thanks to SteveDinn for bringing this to my attention.)

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

var prog = <int>[];
typedef State = (int, int, int);
State parse(List<String> lines) {
  var regs = lines.takeTo('').map((e) => int.parse(e.split(' ').last)).toList();
  var (a, b, c) = (regs[0], regs[1], regs[2]);
  prog = lines.last.split(' ').last.split(',').map(int.parse).toList();
  return (a, b, c);
}

List<int> runProg(State rec) {
  var (int a, int b, int c) = rec;
  combo(int v) => switch (v) { 4 => a, 5 => b, 6 => c, _ => v };
  var output = <int>[], pc = 0;
  while (pc < prog.length) {
    var code = prog[pc], arg = prog[pc + 1];
    var _ = switch (code) {
      0 => a ~/= pow(2, combo(arg)),
      1 => b ^= arg,
      2 => b = combo(arg) % 8,
      3 => (a != 0) ? (pc = arg - 2) : 0,
      4 => b ^= c, //ignores arg
      5 => output.add(combo(arg) % 8),
      6 => b = a ~/ pow(2, combo(arg)),
      7 => c = a ~/ pow(2, combo(arg)),
      _ => 0
    };
    pc += 2;
  }
  return output;
}

Function eq = const ListEquality().equals;
Iterable<int> buildQuine(State rec, List<int> quine, [top = false]) sync* {
  var (int a0, int b0, int c0) = rec;
  if (top) a0 = 0;
  if (quine.length == prog.length) {
    yield a0;
    return;
  }
  for (var a in (top ? 1 : 0).to(8)) {
    var newState = (a0 * 8 + a, b0, c0);
    var newQuine = runProg(newState);
    if (eq(prog.slice(prog.length - newQuine.length), newQuine)) {
      yield* buildQuine(newState, newQuine);
    }
  }
}

part1(List<String> lines) => runProg(parse(lines)).join(',');

part2(List<String> lines) => buildQuine(parse(lines), [], true).first;

Very interesting approach. Pruning deadends by spawning additional walls is a very clever idea.

Tell everyone that I’ve just watched a Jordan Peterson video and I’m going down the rabbit hole and ask them if they know where I can get my hands on some ketamine. My irrational behaviour and urgent need for fast access to my funds would then seem pretty par for the course.

Dart

I liked the flexibility of the path operator in the Uiua solution so much that I built a similar search function in Dart. Not quite as compact, but still an interesting piece of code that I will keep on hand for other path-finding puzzles.

About 80 lines of code, about half of which is the super-flexible search function.

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

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

/// 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) {
  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);
      }
      if (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]);
    }
  }

  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())));
}

typedef PP = (Point, Point);

(num, List<List<PP>>) solve(List<String> lines) {
  var grid = {
    for (var r in lines.indexed())
      for (var c in r.value.split('').indexed().where((e) => e.value != '#'))
        Point<num>(c.index, r.index): c.value
  };
  var start = grid.entries.firstWhere((e) => e.value == 'S').key;
  var end = grid.entries.firstWhere((e) => e.value == 'E').key;
  var dir = Point<num>(1, 0);

  fHeur(PP pd) => 1; // faster than euclidean distance.
  fNextAndCost(PP pd) => <PP, int>{
        for (var n in d4
            .where((n) => n != pd.last * -1 && grid.containsKey(pd.first + n)))
          (pd.first + n, n): ((n == pd.last) ? 1 : 1001) // (Point, Dir) : Cost
      };
  fAtEnd(PP pd) => pd.first == end;

  return aStarSearch<PP>((start, dir), fNextAndCost, fHeur, fAtEnd);
}

part1(List<String> lines) => solve(lines).first;

part2(List<String> lines) => solve(lines)
    .last
    .map((l) => l.map((e) => e.first).toSet())
    .flattenedToSet
    .length;

Uiua

Uiua's new builtin path operator makes this a breeze. Given a function that returns valid neighbours for a point and their relative costs, and another function to test whether you have reached a valid goal, it gives the minimal cost, and all relevant paths. We just need to keep track of the current direction as we work through the maze.

(edit: forgot the Try It Live! link)

Data  ← ≡°□°/$"_\n_" "#################\n#...#...#...#..E#\n#.#.#.#.#.#.#.#^#\n#.#.#.#...#...#^#\n#.#.#.#.###.#.#^#\n#>>v#.#.#.....#^#\n#^#v#.#.#.#####^#\n#^#v..#.#.#>>>>^#\n#^#v#####.#^###.#\n#^#v#..>>>>^#...#\n#^#v###^#####.###\n#^#v#>>^#.....#.#\n#^#v#^#####.###.#\n#^#v#^........#.#\n#^#v#^#########.#\n#S#>>^..........#\n#################"
D₄    ← [1_0 ¯1_0 0_1 0_¯1]
End   ← ⊢⊚=@EData
Costs ← :∩▽⟜:≡(≠@#⊡:Data⊢).≡⊟⊙⟜(+1×1000¬≡/×=)+⟜:D₄∩¤°⊟
path(Costs|≍End⊙◌°⊟)⊟:1_0⊢⊚=@SData
&p ⧻◴≡⊢/◇⊂ &p :

Dart

canMove does a recursive search and returns all locations that need moving, or none if there's an obstacle anywhere downstream. For part2, that involves checking if there's half of a box in front of us, and if so ensuring that we also check the other half of that box. I don't bother tracking whether we're double-checking as it runs fast enough as is.

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

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

solve(List<String> lines, {wide = false}) {
  if (wide) {
    lines = lines
        .map((e) => e
            .replaceAll('#', '##')
            .replaceAll('.', '..')
            .replaceAll('O', '[]')
            .replaceAll('@', '@.'))
        .toList();
  }
  var room = {
    for (var r in lines.takeWhile((e) => e.isNotEmpty).indexed())
      for (var c in r.value.split('').indexed().where((c) => (c.value != '.')))
        Point<num>(c.index, r.index): c.value
  };
  var bot = room.entries.firstWhere((e) => e.value == '@').key;
  var moves = lines.skipTo('').join('').split('');
  for (var d in moves.map((m) => d4[m4.indexOf(m)])) {
    if (didMove(d, bot, room)) bot += d;
  }
  return room.entries
      .where((e) => e.value == '[' || e.value == 'O')
      .map((e) => e.key.x + 100 * e.key.y)
      .sum;
}

bool didMove(Point m, Point here, Map<Point, String> room) {
  var moves = canMove(m, here, room).toSet();
  if (moves.isNotEmpty) {
    var vals = moves.map((e) => room.remove(e)!).toList();
    for (var ms in moves.indexed()) {
      room[ms.value + m] = vals[ms.index];
    }
    return true;
  }
  return false;
}

List<Point> canMove(Point m, Point here, Map<Point, String> room) {
  if (room[here + m] == '#') return [];
  if (!room.containsKey(here + m)) return [here];
  var cm1 = canMove(m, here + m, room);
  if (m.x != 0) return (cm1.isEmpty) ? [] : cm1 + [here];

  List<Point> cm2 = [here];
  if (room[here + m] == '[') cm2 = canMove(m, here + m + Point(1, 0), room);
  if (room[here + m] == ']') cm2 = canMove(m, here + m - Point(1, 0), room);

  return cm1.isEmpty || cm2.isEmpty ? [] : cm1 + cm2 + [here];
}

Uiua

Pretty much just a transcription of my Dart solution.

Data  ← ⊜(⊜(⊜⋕⊸∈"0123456789")⊸≠@\n)⊸(¬⦷"\n\n")"Button A: X+94, Y+34\nButton B: X+22, Y+67\nPrize: X=8400, Y=5400\n\nButton A: X+26, Y+66\nButton B: X+67, Y+21\nPrize: X=12748, Y=12176\n\nButton A: X+17, Y+86\nButton B: X+84, Y+37\nPrize: X=7870, Y=6450\n\nButton A: X+69, Y+23\nButton B: X+27, Y+71\nPrize: X=18641, Y=10279"
IsInt ← <0.00001⌵-⁅.
AB    ← ÷°⊂≡(/-×⇌°⊟)⊏[0_1 2_1 0_2]
Cost  ← /+×IsInt.×3_1AB
&p /+≡Cost Data
&p /+≡(Cost⍜(⊡2|+1e13))Data