What is this, day 16?

Simultaneously very fun and also the fucking worst.

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.

I did this by hand. sort of. I mean I didn’t code up something that found the answer.

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++) {}
}

I used A*, though mathematically I would have been fine with Dijkstra’s. Also, here’s how I remember how to spell Dijkstra: ijk is in alphabetical order.

If you’ve implemented path/back tracking on a search algo before, this wasn’t too bad, though instead of tracking best parent you need to track equivalently best parents. Woke AOC trying to normalise families with more than two parents, SMH

The issue with my code was that I didn’t make a push atomic, i.e. I would move boxes even if their ancestors couldn’t be pushed. Making a list of candidate boxes to push solved this.

Here’s the visualisation of the complete solution, though it doesn’t show the last 100 frames or so. Please forgive me

https://imgur.com/a/RL50MaC

Pretty easy. Just check in the direction you want to push if you have space.

Currently debugging with test cases from the subreddit. I’ve also created a shitty visualiser for it, stay tuned!

https://imgur.com/a/KFddeG0

I made a pretty shitty animation to render the bots and paused it when the tree appeared. This took me way longer than if I had just looked at the 10000 entry text file that I had already made. If I have the energy I’ll make a screen recording.

Given the lack of edge cases, I feel the latter possibility is strong. I’m just glad it was easy!

Ok. So, I overthought this a little. Ultimately, this problem boils down to solving a system of 2 linear equations aka inverting a matrix.

Of course, anyone who has done undergraduate linear algebra knows to look to the determinant in case some shit goes down. For the general problem space, a zero determinant means that one equation is just a multiple of the other. A solution could still exist in this case. Consider:

a => x+1, y+1
b => x+2, y+2
x = 4, y = 4 (answer: 2 tokens)

The following has no solution:

a => x+2, y+2
b => x+4, y+4
x = 3, y = 3

I thought of all this, and instead of coding the solution, I just checked if any such cases were in my input. There weren’t, and I was home free.

No real changes to the solution to p1 aside from the new targets. I wasn’t sure if 64 bit ints were big enough to fit the numbers so I changed my code to use big ints.

I’m looking at my code again and I’m pretty sure that was all unnecessary.

In the world that Lorenz posits, where prediction markets somehow represent accurate news reporting, either a journalist participates in the market whilst reporting news (conflict of interest), or they don’t, and they are bad at their job (and not performing at your job is unethical, I guess?)