# Advent of Code 2017, Day 23

As with Day 18, today’s problem involved running a custom assembly program. However, as stated in part b, the program run with a = 1 is much too inefficient to run directly. Whereas with 18 you could simulate a machine in whichever language you choose and finish running the program in a reasonable amount of time, this problem requires deciphering what the program actually does, then optimizing it. We begin with the input (whose real values I won’t bother with hiding):

set b 81
set c b
jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000
set f 1
set d 2
set e 2
set g d
mul g e
sub g b
jnz g 2
set f 0
sub e -1
set g e
sub g b
jnz g -8
sub d -1
set g d
sub g b
jnz g -13
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23


We can first divide up the program into chunks where the loops are located by identifying negative jumps. The first negative jump is the innermost loop:

set g d
mul g e
sub g b
jnz g 2
set f 0
sub e -1
set g e
sub g b
jnz g -8


Then the next one is the middle loop:

set e 2
<inner loop>
sub d -1
set g d
sub g b
jnz g -13


And at last the outer loop:

set f 1
set d 2
<middle loop>
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23


This leaves the beginning of the program:

set b 81         int b = 81;
set c b          int c = b;
jnz a 2          // a == 1 so this step always executes
jnz 1 5          // skipped by previous step
mul b 100        b *= 100;
sub b -100000    b += 100000;
set c b          c = b;
sub c -17000     c += 17000;
<outer loop>


In short,

int b = 108100;
int c = 125100;
<outer loop>


Next, translating the inner loop:

set g t      g = d;
mul g e      g *= e;
sub g b      g -= b;
jnz g 2      if (g == 0) {
set f 0          f = 0;
}
sub e -1     e += 1;
set g e      g = e;
sub g b      g -= b;
jnz g -13    if (g == 0) {
// go back to beginning of loop
}


Register g appears to be used as the working register rather than a data-holding register. The last four lines will become a familiar pattern. It is equivalent to

if (e++ != b) {
// loop
}


which is clearly the classic for-loop. Combined with the first four lines checking if d * e == b, we have the final for-loop:

for (int e = 2; e < b; e++) {
if (d * e == b) {
f = 0;
}
}


The first line of the middle loop sets the initial value of e to 2; the last four lines follow the aforementioned pattern of breaking when d == b. Thus:

for (int d = 2; d < b; d++) {
for (int e = 2; e < b; e++) {
if (d * e == b) {
f = 0;
}
}
}


The first two lines set f to 1 (by now we know f only takes on values 0 or 1 so it can be a bool) and initialize d to 2. Translating the last eight lines,

jnz f 2      if (!f) {
sub h -1         h += 1;
}
set g b      g = b;
sub g c      g -= c;
jnz g 2      if (g == 0) {
jnz 1 3          break;
}
sub b -17    b += 17;
jnz 1 -23    // loop


This outer loop is also a for loop, only checks for b == c and increments b by 17 each time. Note however that the incrementation is done after checking the condition! This is equivalent to having b <= c in the for loop in place of b < c.

Putting it all together now:

int a = 1;
int h = 0;
int c = 125100;
for (int b = 108100; b <= c; b += 17) {
bool f = true;
for (int d = 2; d < b; d++) {
for (int e = 2; e < b; e++) {
if (d * e == b) {
f = false;
}
}
}
if (!f) {
h++;
}
}
return h;


This program checks if, for every number b in [108100, 108117..125100], there exists some factors d and e, i.e. checks if b is prime, and counts the number of non-prime numbers. This check can be simplified by checking if for all d in [2..sqrt b] we have b % d == 0. Also optimizing for space with judicious data type choices, we have the final program:

unsigned short h = 0;
for (long b = 108100; b < 125100; b += 17) {
bool f = true;
for (unsigned short d = 2; f && d * d <= b; d++) {
if (b % d == 0) {
f = false;
}
}
h += !f;
}
return h;


Alternatively, any prime-checking algorithm for checking the primality of b will do.

The equivalent in Haskell can be written concisely as a fold:

haskell foldr (\b h -> h + (fromEnum . or . map (\d -> b mod d == 0) \$ [2..(floor . sqrt . fromIntegral) b] )) 0 [108100, 108117..125100] `