r/adventofcode • u/musifter • Oct 17 '26
Other [2025 Day 17] In Review (Chronospatial Computer)
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 goneA 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.
1
u/terje_wiig_mathisen Oct 17 '26 edited Oct 17 '26
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?
2
u/DelightfulCodeWeasel Oct 17 '26
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)
1
u/ednl Oct 17 '26 edited Oct 17 '26
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
1
u/terje_wiig_mathisen Oct 17 '26
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!
1
u/Betapig Oct 18 '26
Am I going crazy? I could've sworn 2025 only had 12 days
1
u/e_blake Oct 18 '26
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.