swlabr

P1: Here's what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.

To calculate the shortcut saving:

If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.

P2. The prompt wasn't really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it's the latter.

The above formula is then a special case of Y - X - manhattan distance(X, Y).

P1: Ok, a repeated dfs on suffixes. that shouldn't be too hard. (it was not hard)

P2: Ok, a repeated dfs is a little too slow for me, I wonder how I can speed it up?

forgets about memoisation, a thing that you can do to speed this sort of thing up

I guess the problem is I'm doing an O(mn) match (where m is the number of towels, n is the max towel length) when I can do O(n). I'll build a prefix tree!

one prefix tree later

Ok that still seems to be quite slow. What am I doing wrong?

remembers that memoisation exists

Oh I just need to memoise my dp from part 1. Oops.

Anyway posting the code because I shrunk it down to like two semicolons worth of lines.

(

List<String> input = getLines();
Set<String> ts = Set.from(input.first.split(', '));
Map<String, int> dp = {};

int dpm(String s) => dp.putIfAbsent(
    s,
    () => s.isNotEmpty
        ? ts
            .where((t) => t.matchAsPrefix(s) != null)
            .map((t) => dpm(s.substring(t.length)))
            .fold(0, (a, b) => a + b)
        : 1);

void d19(bool sub) {
  print(input
      .skip(2)
      .map((s) => dpm(s))
      .map((i) => sub
          ? i
          : i > 0
              ? 1
              : 0)
      .reduce((a, b) => a + b));
}

Fun: Ooooh, I get to simulate a computer, exciting!

Worst: Literally 8 edge cases where fucking up even just one can fuck up your hour.

Basically I looked at the program in the input and wrote it out, and realised that A was essentially a loop variable, where the number of iterations was the number of octal digits A would take to represent. The most significant octal digits (octits?) would determine the tail end of the output sequence, so to find the smallest A you can do a DFS starting from the MS octit. I did this by hand.

class Comp {
  List<int> reg;
  List<int> prog;
  int ip = 0;

  List<int> output = [];
  late List<(int, bool) Function()> ops;

  int get combo => prog[ip + 1] < 4 ? prog[ip + 1] : reg[prog[ip + 1] - 4];

  Comp(this.reg, this.prog) {
    ops = [
      () => (reg[0] = (reg[0] >> combo), false),
      () => (reg[1] ^= prog[ip + 1], false),
      () => (reg[1] = combo % 8, false),
      () => (reg[0] != 0) ? (ip = prog[ip + 1], true) : (0, false),
      () => (reg[1] ^= reg[2], false),
      () {
        output.add(combo % 8);
        return (0, false);
      },
      () => (reg[1] = (reg[0] >> combo), false),
      () => (reg[2] = (reg[0] >> combo), false)
    ];
  }

  compute() {
    output.clear();
    while (ip < prog.length) {
      if (!ops[prog[ip]]().$2) {
        ip += 2;
      }
    }
  }

  reset(int A) {
    ip = 0;
    reg[0] = A;
    reg[1] = 0;
    reg[2] = 0;
  }
}

void d17(bool sub) {
  List<String> input = getLines();
  Comp c = Comp(
      input.take(3).map((s) => s.split(" ").last).map(int.parse).toList(),
      input.last.split(" ").last.split(",").map(int.parse).toList())
    ..compute();
  print("Part a: ${c.output.join(",")}");

  if (!sub) return;

  List<int> sols = [];
  bool dfs(int cur) {
    bool found = false;
    sols.add(cur);
    int sol = sols.reduce((a, b) => 8 * a + b);
    c..reset(sol)..compute();
    if (c.prog
        .whereIndexed((i, e) => i >= c.prog.length - c.output.length)
        .foldIndexed(true, (i, p, e) => p && c.output[i] == e)) {
      if (found = c.output.length == c.prog.length) {
        print("Part b: $sol");
      } else {
        for (int i = 0; i < 8 && !(found = found || dfs(i)); i++) {}
      }
    }

    sols.removeLast();
    return found;
  }

  for (int a = 0; a < 8 && !dfs(a); a++) {}
}