Advent of Code Day 23–Human Decompiler

Part 1 of today’s Advent of Code puzzle started off nice and easy. We were given a set of instructions very similar to day 18 and needed to run our program counting how many time the mul operator was executed.

So I just needed a few small modifications to the interpreter function I made for day 18 (sub instead of add, jnz instead of jgz and counting multiplications):

function interpreter(instructions, a) {
    const registers = new Map();
    registers.set('a',a)
    let curPos = 0
    let multiplies = 0;
    const getVal = v => isNaN(v) ? (registers.get(v) || 0) : Number(v)
    const commands = {
        set : (x,y) => registers.set(x,getVal(y)),
        sub : (x,y) => registers.set(x,getVal(x) - getVal(y)),
        mul : (x,y) => { multiplies++; registers.set(x,getVal(x) * getVal(y)) },
        jnz : (x,y) => curPos += (getVal(x) != 0 ? getVal(y) : 1)
    }
    const execute = () => {
        let [ins,arg1,arg2] = instructions[curPos]
        commands[ins](arg1,arg2)
        if (ins != "jnz") curPos++
        return (curPos < 0 || curPos >= instructions.length);
    }
    function showState() {
        console.log(curPos,instructions[curPos],registers)
    }
    return {execute,showState,mult:() => multiplies}
}

This enabled me to solve part 1 fairly easily:

const instructions = input.map(i => i.split(' '))

if (part === 1) {
    const int = interpreter(instructions, 0)
    while(!int.execute()) {
        //
    }
    return int.mult();
}

But part 2 introduced a twist. We needed to run the program again, but with register a set to 1. Unfortunately, this resulted in the program running horrendously slowly and not likely to finish by next Christmas let alone this one. So we needed to look at the code and understand what it was doing to see if any optimisations were possible.

I started off by converting my instructions into a basic JavaScript program. The complicated bit was implementing the jnz commands – jump if not zero. Forwards jumps turn into if statements. Backwards jumps became do…while loops.

So here’s the first stage of my decompilation:

function part2() {
    let a,b,c,d,e,f,g,h
    b = 67                      // set b 67
    c = b                       // set c b
    if (a !== 0) {              // jnz a 2
                                // jnz 1 5
        b *= 100                // mul b 100
        b += 100000             // sub b -100000
        c = b                   // set c b
        c += 17000 }            // sub c -17000
    do { f = 1                  // set f 1
        d = 2                   // set d 2
        do {e = 2               // set e 2
            do { g = d          // set g d
                g *= e          // mul g e
                g -= b          // sub g b
                if (g === 0)    // jnz g 2
                    f = 0       // set f 0
                e++             // sub e -1
                g = e           // set g e
                g -= b          // sub g b
            } while (g != 0)    // jnz g -8
            d++                 // sub d -1
            g = d               // set g d
            g -= b              // sub g b
        } while (g != 0)        // jnz g -13
        if(f ===0)              // jnz f 2
            h++                 // sub h -1
        g = b                   // set g b // these last 4 lines mean loop x1 in part 1 and x1000 in part 2
        g -= c                  // sub g c
        if (g === 0)            // jnz g 2
            return h            // jnz 1 3
        b += 17                 // sub b -17
    } while(true)               // jnz 1 -23
}

At this stage, it wasn’t obvious to me what was going on, but after some simple code refactoring steps, I got it down to:

function part2() {
    let f,h=0
    for(let b = 106700; b !== 123700; b += 17) { 
        f = 1                  // set f 1
        for(let d=2; d!=b; d++) {
            for(let e = 2; e != b; e++) { 
                if ((d * e) === b) {    // set g d, mul g e, sub g b, jnz g 2
                    f = 0       // set f 0
                }
            } 
        }
        if(f ===0)              // jnz f 2
            h++                 // sub h -1
    } 
    return h;
}

Suddenly it dawned on me. We were checking (extremely inefficiently) to see if b is prime, and counting how many non-prime numbers we encountered in the loop.

So now all we need is a standard prime checker function:

const isPrime = num => {
    for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num !== 1;
}

This allows us to easily check each number in the range. I managed to end up with an off by one error probably due to a mistake in my decompilation process, but once I’d figured that out, I got my gold star for part 2:

let h = 0
for(let b = 106700; b <= 123700; b += 17) { 
    if (!isPrime(b)) h++;
}
return h;

Just two days to go! All my solutions so far are up on GitHub.