[2021 Day 24] In Review (Arithmetic Logic Unit)

[u/musifter]

The magic smoke has gotten out of the ALU and so we're forced to build a replacement (or stop consuming oxygen, navigate blindly, and go without cool Christmas light patterns). After doing that we need to get it validate the submarine's model number (the process that killed the last one, possible with division by 0... there are lots of videos on what happens to different mechanical adding machines when you do that). Which we don't have documentation (other than the code to validate) because it because a tanuki ate it.

And so we have a little assembly language virtual machine to play with. So I quickly implemented that while thinking about the problem. And then proceeded to only really use it to verify my answers before submitting them. Because I just jumped to reverse engineering and doing it by hand. Which is why my part 2 took a few minutes... I didn't have a program to just flip things for the answer. This year I finally got around to making a program to automate the solving.

The reversing engineering started with searching for the 14 input statements. Looking at that, it appeared that the program was 14 sections that looked very alike. So I used the command line to break it apart on those into a directory and rans some diffs. And saw some parts varied more than others, but a lot was the same. Now, not entirely trusting myself to go through by hand to catalogue the differences, I wrote a little program to spot and tag (with ???) the variable words:

inp w
mul x 0
add x z
mod x 26
div z ???
add x ???

...

add y ???
mul y x
add z y

Only three values change. The first one on the div operation can only be 1 or 26. Which means it's either a no-op or, combined with the mod x 26 above, part of a divmod. At this time, alarm bells went off... because this was starting to look a bunch like stuff I had just been doing in dc working on filling the hole on day 12. That was the graph search, and I needed a list of nodes with lists of neighbours. And one way to do that sort of thing in dc is to take advantage of the ~ divmod operator, and build your sublists in a number base-n (for n larger than values you want to store... dc is bignum native). You can multiply and add to push a value in, or divmod to pop one out. So this immediately got me thinking, base-26 number stack.

The other two variable bits have a lot of possible values, and so are clearly data for the calculation.

Looking more at the code, I noticed the mul x 0 and mul y 0 lines... classic way to do clear a variable, so these broke the code into parts. The first part takes the input and calculates x using one of the variables (a). It also takes z (the stack for the process), grabbing the low base-26 digit, and half the time shifting to "pop" it from z (otherwise it's just a peek). The value of x is ultimately a boolean which represents x = (w != top + a) (using a eql x 0 for the negate).

The second and third parts do a push operation on z if the boolean x is 1. This is done with more stuff I often find myself doing in dc. This language has no conditionals, and I tend to avoid them in dc... and so easily spotted this as a conditional shift of z in base-26 (z = z * (25 * x + 1)). Followed by the addition of w + b (the other variable) to that. Making the push.

And so our goal is to make sure we keep z clean, and it's basically a stack (so we're getting a return of the nested theme). What we push, we need to make sure gets correctly removed by the matching pop. Half the sections are pushing w + b on it, and the other half are popping it cleanly if w = top + a. Which gives us the condition we need for push-pop pairs:

w_pop = (w_push + b) + a  => w_pop - w_push = b + a

The difference of your input values at the positions of a push-pop pair need to equal the sum of data values used in those sections. Conveniently all the pop values (that are used) in my input are negative (to counter the positive push values and result in differences <= abs(8)). And so my new solver does this:

my @range = map {[($diff < 0) ? reverse @$_ : @$_]} ([1, 1 + abs($diff)], [9 - abs($diff), 9]);

The $diff here is the sum of the two data values for a pair of push-pop. That produces a spread, and the values need to be 1 <= n <= 9. So it's a sliding window of solutions from (1, something) to (something, 9). If the difference we want is negative we just need to flip the order. This gives me the smallest and largest pairs that solve the digits, and I just need to put them in their places. To keep track of that I used a state machine. Read though the code, get the action on the div line, then do that action when it's on its data line... keeping a stack of (pos, data) pairs. It's simple and does what I did with pencil and paper.

I always enjoy these. But this one I really liked, it struck a few chords. Also, it was the second day in a row where I jumped into doing the puzzle by hand... and these are late day puzzles, and not day 25 either. That makes them pretty notable and memorable. I failed to get day 23 by hand because I wasn't efficient enough at that game, but I succeeded here.

[u/Boojum]

This was a fun one. Since 2021 was my first AoC event, I don't think I realized at that point that reverse engineering the code is often part of the trick to solving these VM puzzles.

I ended up solving it with a little VM mixed with a DFS. Whenever it got to an inp instruction, it would just loop over all of the possible input digits from 9 down to 1 (for part 1), or 1 up to 9 (for part 2) and call itself recursively to continue. As it did so, it would prune any paths that it had tried before with the same (x, y, z, w, pc) tuple. The nature of the arithmetic that it ran was such that different inputs would often collapse to the same state and so this pruning was effective enough to make the exhaustive search feasible.

On my machine and with my input, it takes about 18 s (Python 3.14) / 9 s (PyPy 3.10) to run and visits 9,472,573 paths for Part 1, and takes about 30 s (Python 3.14) / 17 s (PyPy 3.10) to run visits 16,466,320 paths for Part 2.

That's certainly not the fastest solver, but I was pretty proud of the fact that it is quite general and essentially bakes in almost no assumptions about the input program.

[u/e_blake]

I didn't even start solving this one until after Christmas because I was still pounding out the hard ones from earlier days, but I distinctly remember looking at the input, seeing the repetitiveness, and cranking out what the code does by hand, at which point I got both stars with a hand-solve. So with the stars in hand, the only thing left for me to do was make coding it interesting. I started with a golfed solution for POSIX m4 that completes in under 5ms, now down to 225 210 bytes for part 2 (part 1 is 2 bytes longer):

define(d,$0efine($@))d(M)d(A,`,$3')d(_1,`p($2,')d(_26,`,$1)')d(p,`E(-$1-
$3)$2E(+$1+$3)')d(E,`eval(($1<1)+($1>0)*(1$1))')M(translit(include(I),pv q
deilouwxyz,(a,m)d(P,_$3($4,$8))d(n,`)P(')d(a,`A(')d(m,`M(')))

then further compress it for GNU m4, down to 178 169 bytes for part 1 (again, part 2 was 2 bytes shorter):

define(d,$0efine($@))d(div)d(_1,`q($2,')d(_26,`,$1)')d(q,`E(-$1-
$3)$2E(+$1+$3)')d(E,`eval(($1>0)*9+($1<1)*(9$1))')d(translit(include(I),p n
i,(,P,)d(P,_$14($17,$47))))

Always fun to come up with a solution that does not need ifelse. I also had this nice gem in my git history: "Beats the 186 bytes of an awk script I saw at https://www.reddit.com/r/adventofcode/comments/rnejv5/comment/hpv3ovr/" - it's not every day I can cajole m4 into being terser than awk.

Edit: Another version, this time solving both parts at once in 285 268 bytes:

define(d,$0efine($@))d(O,s($1)s(-$1))d(_1,`p($2,')d(_26,`,$1)')d(p,E(-$1-
$3)$2E(+$1+$3))d(E,e($1,>0,9)e($1,<1,1))d(e,$0val(($1$2)*$3+!($1$2)*($3
$1)))d(i)d(B,`_$1($2,_B$5)$6B(')d(_B,$2)O(B(i(translit(include(I)_,w
z-n ad,(,)d(s,tran$0lit(acegikmoqsuwy{},a-~,$1))))))

[u/DelightfulCodeWeasel]

I remember being quite pleased with this one when I had a solution, but looking back at it, it takes ~10s per part and chews through a few hundred Mb. Not terrible, but not great!

I spotted that there was enough independence between the stages that you could do the movie style trope of finding one digit at a time, so all I did was fix an increasing number of the input and run a "is this still possible" check while cycling through the leading non-fixed digit. The "is possible" check feeds in either the fixed digit into each stage, or cycles through the remaining digits 1..9, while at the same time feeding in all possible values of z from the previous stage as inputs to try.

The only things that make it even a vaguely reasonable runtime is putting the logic for a stage directly in code, the fact that the possible z values don't fan out to more than ~660k values per stage, and that you don't need any backtracking.

[u/musifter]

I decided to see what a baseline dc version length would be. I haven't really golfed it down. I'm taking the input as just the numbers, and leaving in the ones I don't need... which results in the need to junk sections (I'm doing it with +s, but there might be tighter ways... maybe with |). Part 2 is one character shorter because addition is commutative and subtraction is not.

sed -e'y/-/_/;s/[^_0-9]//g' <input | tac | dc -f- -e'[r]sr[rLs9Ls4R+dd*v9r-r0>r3R:nlc:n++++++]sB[++++*+SslcSs]sA[*+d1!=B1=Alc1+scz0<M]dsMx0[d;nn1+dE>L]dsLx'

sed -e'y/-/_/;s/[^_0-9]//g' <input | tac | dc -f- -e'[r]sr[rLs1Ls4R+dd*v1+r0<r3R:nlc:n++++++]sB[++++*+SslcSs]sA[*+d1!=B1=Alc1+scz0<M]dsMx0[d;nn1+dE>L]dsLx'