⟨ortho|normal⟩

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:

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