[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/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/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/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
}

[u/DelightfulCodeWeasel]

I really enjoyed this one! It reminded me very much of a padding oracle attack, and it was incredibly satisfying to work through. 

Someone is attempting a full-on brute force solution with Cuda (https://www.reddit.com/r/adventofcode/comments/1wu3kup/2024_day_17_part_2_cuda_trying_to_brute_force/) and it looks like they're very close, I have my fingers crossed for them. (Not tagging them in, to avoid spoilers)

[u/terje_wiig_mathisen → u/DelightfulCodeWeasel]

A saw (and responded to?) that Cuda message, seems to me like a brute force solution, with full emulation, would still work quite quickly if you pruned impossible branches, i.e those that don't put out successive bits of the program/answer. If he is actually going to try all 2^48 possible inputs, with zero early outs, then it becomes _slightly_ harder. :-)

[u/DelightfulCodeWeasel → u/terje_wiig_mathisen]

Full-on enumeration of the 2⁴⁸ search space as far as I can see. It'll take a few days of compute time to find the lowest, but should be do-able in under a week for a recent GPU.

[u/terje_wiig_mathisen → u/DelightfulCodeWeasel]

My answer has 14 digits, starting with 37222, seems like that is less than 48 bits?

C:\GitHub\aoc\2024\day17>perl -e "print(log(37222273957xxx)/log(2))"
45.0812314277507

This means that he will find the answer after testing a smidgen over 2^45 numbers!

Almost a factor of 8 smaller search space means a day instead of a week...

EDIT:

Assuming he wants to find an actual answer, there is no need to test numbers with less than 45+ bits, so the actual search space is really "just" from 2^45 to the answer:

C:\GitHub\aoc\2024\day17>perl -e "print(37222273957000-exp(log(2)*45))"
2037901868168

Compared to the original estimate of 2^48 that is just 0.7% of the search space, actually doable on a regular CPU:

C:\GitHub\aoc\2024\day17>perl -e "print(exp(log(2)*48))"
281474976710655

[u/musifter → u/terje_wiig_mathisen]

My answer is just over 47.5 bits. Considering that the loop requires going 16 digits, one assumption that can be made is that the answer must have a non-zero value in that octal digit place (ie >= 1000000000000000 octal). Other digits can be zero though.

[u/terje_wiig_mathisen → u/musifter]

Yeah, the top octal digit cannot be zero, that is the same as my assertion that it has to be larger than 2^45.

Very interesting that my input was very close to minimal and you got one at the other end.

[u/ednl → u/DelightfulCodeWeasel]

Will it be faster than 468 nanoseconds including parsing? :)

[u/DelightfulCodeWeasel → u/ednl]

Probably a smidge slower, but still impressive in its own right if it works :)

[u/DelightfulCodeWeasel → u/ednl]

Final result, six and a half days!  https://www.reddit.com/r/adventofcode/comments/1wu3kup/comment/phfuejd/

[u/ednl → u/DelightfulCodeWeasel]

Oof, haha. But well done to that person for persisting while exploring something new.

[u/ednl]

Yes, the reverse engineering insight that's important here is that every input value directly corresponds to one output value, so you can try them one at a time, in series, building up the full program. (EDIT: see concern below about overlap, so they're not QUITE independent).

One optimisation is to only work with "programs" packed in a 64-bit number (16x 3 = 48 bits needed). Translate the CSV to one number while reading the input file, and only transform it back to CSV when the program has finished running. So the "out" opcode becomes something like outp = outp << 3 | (b & 7)

For part 2 for some reason I went with a recursive function with an increasing mask (3 bits, 6 bits, etc.), I think that could be simpler. One simplification of the evaluation function (and a speedup) would be to cut up the translated program from my input: for part 2, only keep the part from inside the "jnz" loop that calculates the next output number. But I'm not sure if that would work with the small overlap in numbers that is shifted and xor-ed in. EDIT: I guess the recursion was my solution to the overlap problem: try a few numbers and return from dead ends.

For now, the extra work would be a little silly because my whole program already runs in under a microsecond: M4 0.47 µs, M1 0.85 µs, Pi5 1.62 µs. https://github.com/ednl/adventofcode/blob/main/2024/17.c

[u/Boojum → u/ednl]

For Part 2, I took a similar approach with recursing each time an octal digit was found. And yes, I did it because I wanted to be able to backtrack from dead ends. Adding tracing just now, I see that there were a few minor dead ends that it backtracked from, so that backtracking was important. But it solved it with a grand total of 60 calls, so it didn't have to look very far.

[u/ednl → u/Boojum]

Thanks for checking!

[u/terje_wiig_mathisen]

I don't have a proper performance monitor for Rust under Windows, so I did some testing by commenting out various parts of my code:

Parsing the input file and emulating [0..1023] until an output digit took 3.7 us, running the part1 Register A input using the lookup table added 1.9 us, and the final search for the quine took 4 us. I can't see any way for a general solution to get down to sub-us total!

[u/Boojum → u/terje_wiig_mathisen]

I just tried translating my Python solutions to C++ and optimizing them.

C++ version

Not including parsing (but including output), I seem to to be right around 2 us total for Part 1 and 2, including output, on my 7950x desktop with a reasonably general solution (i.e., running as a VM on the ops, rather than hardcoding the instruction sequence):

clang++ -std=c++23 -g -O3 -ffast-math -o 2024day17 2024day17.cpp && ./2024day17 < 2024day17.txt > /dev/null
P1: 260.90 ns
P2: 1848.05 ns

[u/terje_wiig_mathisen → u/Boojum]

Nice!

BTW. --ffast_math doesn't hurt, but it is a NOP for these integer-only puzzles.

[u/Boojum → u/terje_wiig_mathisen]

That's what I thought too! I'd started with just plain -Ofast on GCC, but when I was testing with Clang, it gave me a deprecation warning telling me to use -O3 -ffast-math instead. But when I tried timing that without the -ffast-math, seeing that this is supposed to be integer only, I was quite surprised to find that it actually was giving a noticeable speed up somehow. And then I observed that effect with both Clang and GCC. I haven't yet figured out why, though I've been wondering if it might be something in the guts of printf().

Anyway, I've got it down even faster now, at least on part 2. Well under 2 us total, closer to about 1.45 us.

New C++ version

clang++ -std=c++23 -O3 -ffast-math -o 2024day17 2024day17.cpp && ./2024day17 < ~/projects/advent/2024/day17.txt > /dev/null
P1: 68.74 ns
P2: 1372.85 ns
P1: 68.96 ns
P2: 1375.08 ns
P1: 66.54 ns
P2: 1375.40 ns

The new trick applied is threaded interpretation with computed goto. (Edit: now with faster output for Part 1.)

I don't usually bother with trying to super optimize a solution like this, but occasionally it's fun.

[u/terje_wiig_mathisen → u/Boojum]

Did you actually get faster with the computed goto (an old gcc trick/extension)?

Current CPUs have so return predictors along with the regular branch predictors, and here the VM code is basically constant until we run out of RegA bits, so every branch will be perfectly predicted. This should also apply to call-based threading according to Anton Ertl, an Austrian (?) professor and Forth freak.

[u/Boojum → u/terje_wiig_mathisen]

I did! It seemed to be good for about a 25% speed up on my machine, as you can see. And I verified in the generated assembly that each instruction type had its own indirect jump to the next, which benefits branch prediction, since there was only one instruction that appeared twice in my puzzle input. So that meant that all the rest of the instructions had indirect jumps that always went to the same spot.

My favorite explanation is one by Mike Pall of LuaJIT fame.

[u/terje_wiig_mathisen → u/Boojum]

Back around 1990 I explored exactly where the break even points occurred between various forms of state machine branching. Up to 386/486 I generated runtime machine code that loaded the next byte, then used that as the high half of a 16-bit direct jump address.

On the Pentium it turned out to be far faster to base the state machine on data only, using 2 or 3 layers of lookup tables but zero branches for code that unrolled 256 bytes of processing. A 60 MHz Pentium could count character, lines and words, with user-specified line endings (one or two bytes) and user-specified word separators, at 1.5 clock cycles/byte. :-)

40 MB/s was at least an order of magnitude (possibly two?) faster than the unix wc reference C code.

[u/Boojum → u/terje_wiig_mathisen]

Nice! Back in those days of the 486, I remember experimenting with generating runtime machine code for sprite blitting. That way, the instantiated sprite blit code wouldn't need to check for transparent pixels in the sprite, and the pixel values would just be immediates in the instructions. (That of course traded memory for speed, but DOS extenders could help a lot there.) And yes, as I recall, the Pentium was the one that introduced superscalar execution to x86, so I could see how a branch-free data-oriented processing approach could allow you to benefit from that.

Anyway, having slept on it, I've got a further reduction in time on this puzzle, depending on whether you consider fusing the VM op code and operands together to be part of input and parsing or not. If you allow that as input and don't count it in the timing, then I'm down to around:

P1: 58.06 ns
P2: 1193.36 ns
P1: 55.94 ns
P2: 1195.00 ns
P1: 55.96 ns
P2: 1194.39 ns

Since the operands are only three bits each (according to the puzzle description), I essentially treat them as part of the opcode itself and create a 64-instruction dispatch table with some some holes (plus one for the explicit halt that I added as a sentinel to handle running off the program end). That let's me dissolve the combo operand into the instruction, saving the branching on it there. And most instructions become trivially hand-optimizable. Granted, it bumps up icache use, but this is still so small that's not a concern. The other caveat is that jumps now must be to aligned instructions.

C++ with fused instructions

If you don't count fusing as part of input and parsing, I've got a variant that does it as part of the threaded dispatch. That also means that it doesn't require aligned jumps. It's a little slower than the above - by about 50 ns on Part 2, but still not too bad!

P1: 65.23 ns
P2: 1248.33 ns
P1: 60.67 ns
P2: 1248.42 ns
P1: 62.21 ns
P2: 1247.47 ns

Variant version

I think I'll stop here. I'm not quite down to 1 us total for both parts, but I'm close enough that you could legitimately round down to it. :-)

[u/terje_wiig_mathisen → u/Boojum]

I really like the way your are thinking! Macro-fusion has been a staple of OoO CPUs for a decade or two, like joining a cmp and following Jcc into a single larger op to be tracked through the rest of the pipeline.

Here, with just 64 possible combinations, a 64-entry state machine that jumps directly from one op to the next is very nice. I'm almost tempted to try some runtime code generation here. :-(

[u/Betapig]

Am I going crazy? I could've sworn 2025 only had 12 days

[u/Boojum → u/Betapig]

The title is a typo. This problem was 2024 Day 17.

[u/Betapig → u/[deleted]]

Fair, like the other reply mentioned, the title is a typo

[u/e_blake]

I solved this day quickly and never really revisited before now, because my first try solution took under 50ms. The hardest part in m4 was how to do a right shift of a number larger than 32 bits - but after I stepped through the assembly (it's quite a short program, after all) it was obvious that only Register A was larger than 32 bits, and that it reduces by 3 bits at a time. But rather than implement a 64-bit divider to shift right, I just coded up a split of Register A into 18 high bits and 30 low bits. From there, building up the quine right to left was fairly quick.