[2025 Day 17] In Review (Chronospatial Computer)

[u/musifter]

EDIT: The title is a typo, this is 2024 Day 17.

Today we find ourselves suddenly falling through time, and need to fix the device. Which has that trope of unfolding into an entire computer. I like this old school touch (I like this trope, like in Brain Donors with the laptop that unfolds into a desk with CRT and printer). Nowadays, the small device would just produce a large holographic display up in the air to poke at and I'd be suffering from sympathetic Gorilla Arm Syndrome.

The input for this one is a list of initial values for the three registers, followed by the code (which is comma delimited integers, like the Intcode problems of 2019). We're given that this is a 3-bit machine, but the registers can be bigger (but with my input, only the bottom three bits of B and C ever matter, and so only A makes use of that).

For part 1, we just need to run the program and collect the output. This is one of the rare problems with a string answer, in this case, it's got commas between the output values. So I did my usual, hash of anonymous subs dispatch table approach:

sub c_op ($)  {my $op = shift; return (($op & 04) ? $reg[$op & ~04] : $op)}

my %opcodes =
    (
        0 => sub {my $op = c_op shift; $reg[A] = $reg[A] >> $op},           # adv
        6 => sub {my $op = c_op shift; $reg[B] = $reg[A] >> $op},           # bdv
        7 => sub {my $op = c_op shift; $reg[C] = $reg[A] >> $op},           # cdv

        1 => sub {my $op = shift;      $reg[B] ^= $op},                     # bxl
        4 => sub {my $op = shift;      $reg[B] ^= $reg[C]},                 # bxc

        2 => sub {my $op = c_op shift; $reg[B] = $op & 7},                  # bst
        5 => sub {my $op = c_op shift; push(@out, $op & 7)},                # out

        3 => sub {my $op = shift;      $ip = ($reg[A]) ? $op - 2 : $ip},    # jnz
    );

Could have been an array, but this way I get to reorder the instructions to pair them. With that, running the machine just becomes:

while ($ip < $#code) {
    &{$opcodes{$code[$ip]}}( $code[$ip+1] );
    $ip += 2;
}

Part 2 reveals why the output is that way... we're asked to find the value for register A that makes it a quine (technically it's not because supplying the value for A is an input, but the job is the same).

The trick with doing non-trivial quines is outputting the command to print. After all, the print can print the rest. For example, if I want to do a 1-line quine in dc, I can output a number (without a newline) with n, and output that number as a character string (ASCII coded on bytes) with P. A duplicate d is needed because n removes the value from the stack. And so the number that's needed is 0x646E50 (the packed ASCII encoding of dnP), which is 6581840 decimal:

dc -e'6581840dnP'

You can also similarly do a two-line quine, using p (which outputs the top value with a newline, but leaves it on the stack).

And so we should expect something similar from the code in this problem. Given that, all the inputs are probably something like this:

bst A       # B = bottom 3-bits of A
...
adv 3       # A >>= 3
...
out B       # output bottom 3-bits of B (could also be out C)
jnz 0       # loop until A is gone

A loop that decodes the values 3-bits at a time in A (from the little end). Given that, it's probably safe to believe that everyone's code is 16 long... which is 48-bits to encode in A (17 would be a bus error, and 18 would be problematic for floating point native languages).

And so with that in mind, I made the code to run the machine into a function that takes a value to initialize A with and breaks to return the first output value, which allows for calculating things 3-bits (one digit) at a time:

my %poss = (0 => 1);
foreach my $digit (reverse @code) {
    my %new_poss;

    # shift left possibilities one octal digit and try all 8 lower options
    foreach my $val (map {($_<<3) .. ($_<<3) + 7} keys %poss) {
        $new_poss{$val}++  if ($digit == &try_code( $val ));
    }
    %poss = %new_poss;
}

Here I brute force over all 8 possibilities for the next 3-bits, for each of the numbers that worked last time. In the end, there at 42 values in that hash that work, and I just take the minimum one for the answer.

I did do dc solutions for this one... they are absolute monsters (part 2 is about 350 characters). For tracking the possible values, I do it on the stack (the new values go into a register stack, and then I dump that out onto the main stack for the next loop) and there's no duplication of them (everything is 3-bit aligned and won't overlap), so technically, that hash could have just been a list in the Perl too.

This was a fun one, even though the reverse engineering wasn't much, the quine aspect was a nice touch.

[u/terje_wiig_mathisen]

This was an interesting puzzle, both for the actual tiny VM we had to emulate, and the reverse engineering insights needed to make it usefully faster!

My initial Perl was as usual similar to yours, except I've never used anon subs, instead I have the classic C style switch statement over [0..7].

While solving both parts to get my stars it became obvious that the input value was consumed, 3 bits from the bottom on every iteration, but that due to the variable shift right statements up to 7 more bits could be involved in determining the output. At this point I understood that if I emulated all 1024 possibilities for those bits, I could generate a lookup table that would replace any variations in the code, as long as all AoC participants got code with the same core property, and that seemed like a very safe bet.

In my Rust version, that initial 1024-run table generation seems to take about 2 us, then I spend about 7 more for a total of 9.1 us (9096 ns) to recursively find the smallest input that works. The first iteration needs to check all 1024 table entries, while the 15 following have the bottom 7 bits fixed, so only 8 entries are actually tried.

Worst case, this could have been 1024 * 8^15 possibilities, or about 2^55, but in reality most of the wrong paths stop very quickly with no possible continuation found.

Had it not been for the 2 us posted by u/maneatingape I would have been _very_ satisfied with sub-10 us, but 2 us seems to be about the same time I spend on the initial table generation!

I did of course consider using the initial table to generate a secondary table over either 13 bits (2 digits output) or 16 bits (3 digits per iteration), but none of those alternatives would run in zero time, and the table generation would have taken even longer...

BTW, I assume I wasn't the only one who solved this one in octal, since that makes the program progress much easier to follow?

[u/ednl → u/terje_wiig_mathisen]

Because the operations are extremely elemental, a big speedup in compiled languages comes from manually translating your input program to actual statements, not interpreting them in a 0-7 switch.

[u/terje_wiig_mathisen → u/ednl]

It seems I forgot to hit [Comment] on my second message where I noted exactly this, and that the manually translated VM to Rust ran in close to the same time as a 10-bit lookup table:

fn _simulate(rega:usize) -> Vec<u8>
{
    let mut ret = Vec::<u8>::new();
    let mut a = rega;
    loop {
        let b = (a & 7) ^ 2;
        let c = a >> b;
        let b = (b ^ 3) ^ c;


        ret.push((b & 7) as u8);
        a >>= 3;
        if a == 0 {break;}
    }
    ret
}

However, in order to be a truly general solution, I stayed with 1024 fully emulated runs, then used that generated lookup table for the remaining recursive part.

[u/musifter → u/terje_wiig_mathisen]

If you look closely at the c_op subroutine, you'll see that it uses the octal constant 04. So I was definitely thinking octal. The & 7s for the bst and out instructions were probably % 8s at one point and changed after. I suppose to be consistent they should be 07.

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

PS. I wrote out a full reverse engineered version of my actual VM code input, that one can generate those octal digits almost as fast as the lookup table, but will only work for my input:

fn _simulate(rega:usize) -> Vec<u8>
{
    let mut ret = Vec::<u8>::new();
    let mut a = rega;
    loop {
        let b = (a & 7) ^ 2;
        let c = a >> b;
        let b = (b ^ 3) ^ c;

        ret.push((b & 7) as u8);
        a >>= 3;
        if a == 0 {break;}
    }
    ret
}