Write-up: Advent of Code 2017, day 18
I've been catching up on my Advent of Code journey. At the time of this writing I have 382 stars out of 500.
Today I was working on day 18 from 2017. The problem is called "Duet" and its full text you can find here.
The first part is straightforward. You are provided with an assembly code for a fictional CPU, and you're asked to implement the emulator for this CPU, run the program, and return the content of a particular register.
In the second part we learn that the program has two threads that run concurrently and communicate using the snd (send) and rcv (receive) instructions. We are again asked to simulate that execution and return the number of snd instructions executed by one of the threads.
Simulating this machine is fairly straightforward. Message passing basically ensures that changing the order of execution does not change the result, so we can choose an arbitrary ordering for the simulation.
However, Advent of Code puzzles of more recent years tend to be much more computationally hard, and require you to actually understand what the assembly code does, so that you can figure out the answer without simulating the execution. (See for example day 20 of 2023). Let's try doing that instead.
I'll first translate my original listing into a C program line by line:
int C1, C2, C3, C4; // These are constants specific to my instance of the problem.
int i = 0, a = 0, b = 0, f = 0;
// According to the problem, the p register contains the "program ID".
int p = pid();
// C code on the left, original assembly on the right:
i = 31; // set i 31
a = 1; // set a 1
p *= 17; // mul p 17
if (p > 0) goto label_1; // jgz p p
label_2:
a *= 2; // mul a 2
i -= 1; // add i -1
if (i > 0) goto label_2; // jgz i -2
a -= 1; // add a -1
i = 127; // set i 127
p = C1; // set p C1
label_3:
p *= C2 // mul p C2
p %= a; // mod p a
p *= C3; // mul p C3
p += C4; // add p C4
p %= a; // mod p a
b = p; // set b p
b %= 10000; // mod b 10000
send(b); // snd b
i -= 1; // add i -1
if (i > 0) goto label_3; // jgz i -9
label_1:
if (a > 0) goto label_4; // jgz a 3
label_5:
b = recv(); // rcv b
if (b > 0) goto label_5; // jgz b -1
label_4:
f = 0; // set f 0
i = 126; // set i 126
a = recv(); // rcv a
label_6:
b = recv(); // rcv b
p = a; // set p a
p *= -1; // mul p -1
p += b; // add p b
if (p > 0) goto label_7; // jgz p 4
send(a); // snd a
a = b; // set a b
if (1 > 0) goto label_8; // jgz 1 3
label_7:
send(b); // snd b
f = 1; // set f 1
label_8:
i -= 1; // add i -1
if (i > 0) goto label_6; // jgz i -11
send(a) // snd a
if (f > 0) goto label_4; // jgz f -16
if (a > 0) goto label_5; // jgz a -19
Now let's try to find what is the purpose of various blocks of code, and rewrite them in more sensible C. First, let's find various conditionals and loops:
if (p >= 0) goto label_1: this just skips a block of code, so we replace it with anif-block,i = 31,i -= 1andif (i >= 0) goto label_2can be merged in afor-loop,- similarly for
label_3andlabel_6, b = recv()andif (b > 0) goto label_5can be replaced with awhile-loop,label_4is referenced twice. Let's replace one of theifstatements with adoloop, but leave the other as agotofor now,label_5can also be replaced with adoloop.
We also have this sequence:
if (p > 0) goto label_7;
// block 1
if (1 > 0) goto label_8;
label_7:
// block 2
label_8:
We can clearly see that only block 1 or block 2 will execute, depending on the value of p, so this can be replaced with an if-else block. Here's our result so far:
// set i 31
a = 1; // set a 1
p *= 17; // mul p 17
if (p <= 0) { // jgz p p
for (i=31; i>0; i--) {
a *= 2; // mul a 2
i -= 1; // add i -1
} // jgz i -2
a -= 1; // add a -1
// set i 127
p = C1; // set p C1
for (i=127; i>0; i--) {
p *= C2 // mul p C2
p %= a; // mod p a
p *= C3; // mul p C3
p += C4; // add p C4
p %= a; // mod p a
b = p; // set b p
b %= 10000; // mod b 10000
send(b); // snd b
// add i -1
} // jgz i -9
}
if (a > 0) goto label_4; // jgz a 3
do {
while ((b = recv()) > 0); // rcv b
// jgz b -1
do {
label_4:
f = 0; // set f 0
// set i 126
a = recv(); // rcv a
for (i=126; i>0; i--) {
b = recv(); // rcv b
p = a; // set p a
p *= -1; // mul p -1
p += b; // add p b
if (p <= 0) { // jgz p 4
send(a); // snd a
a = b; // set a b
} else { // jgz 1 3
send(b); // snd b
f = 1; // set f 1
}
// add i -1
} // jgz i -11
send(a) // snd a
} while (f > 0); // jgz f -16
} while (a > 0); // jgz a -19
Now this is much more clear. Remember that the p register tells us which "thread" we're currently running. So only our thread 0 will execute the if (p <= 0) block, which will generate and send 127 numbers to thread 1. As an exercise, can you tell how the numbers are generated?1.
After thread 0 generates and sends the numbers, both threads jump over the while ((b = recv()) > 0); loop straight into the do-while loop at label_4. The loop does the following:
- set
f(for "flag"?) to zero, - receive one number, store it in
a, - for each of the next 126 numbers, do the following:
- receive next number, store it in
b, - if
a > b, sendato the other thread, storebina, - otherwise, send
bto the other thread, store1inf,
- receive next number, store it in
- send
ato the other thread, - continue the loop if
fis1.
Let's see what happens if we apply this algorithm to a shorter array, say, [2, 5, 3, 1]:
- 2 is received and stored in
a. - 5 is received. 2 > 5 is false, so 5 is sent, and 1 is stored in
f. - 3 is received. 2 > 3 is false, so 3 is sent, and 1 is stored in
f(again). - 1 is recieved. 2 > 1 is true, so 2 is sent, and
b = 1is stored ina. - finally, the value of
a = 1is sent.
The resulting array is [5, 3, 2, 1]. The other thread will receive the array and process it in the same way, which will continue until eventually one of the threads never sets their f flag to 1.
Does this look familiar? I hope it does, because it's nothing else than an elaborate implementation of bubble sort using send/receive queues to store the arrays. To get the answer (how many snd instructions did thread 1 execute) we need to:
- find the number of iterations of bubble sort needed to sort this random array (which will be between 1 and 127),
- divide it by 2 and take the ceiling (since thread 1 will only perform half of the iterations),
- multiply the result by 127 (one
sndinstruction per element).
There is probably a way to find out the number of bubble sort iterations needed to sort the array without implementing bubble sort itself (e.g. for a fully sorted array it's always 1, for a reverse sorted array it's always the length of the array), let me know if you find an elegant solution to that!
Let me know what you think on Mastodon.
- the code generates numbers between 0 and 9999 using a linear congruential generator with seed C1, modulus 2^31-1, multiplier C2*C3, and increment C4.↩︎