Advent of Code Day 18-Parallel Programs

Fortunately I had the day off work, because I made a real meal of solving today’s challenge. On the surface it seemed simple enough. We had a bunch of instructions that we needed to follow, updating registers and occasionally jumping backwards and forwards in the instructions. It’s the type of problem we’ve seen plenty of times before in Advent of Code, such as on day 8 this year.

The main bulk of my solution was in my interpreter function, which took the instructions, a program identifier (used to initialize register p), and send and recv functions to support communication between two programs (needed for part 2).

The execute method exposed on the object returned by interpreter executes the next command, and returns a flag indicating if we are now “blocked”. We’re blocked if we get a “receive” command but the recv function doesn’t return a number. For part 1, we’ll always be blocked but in part 2 we can receive data from another instance of the program.

You can also see I added a showState method, as part of my attempts to debug part 2.

function interpreter(instructions, id, send, recv) {
    const registers = new Map();
    registers.set('p',id)
    let blocked = false;
    let curPos = 0
    const getVal = v => isNaN(v) ? (registers.get(v) || 0) : Number(v)
    const commands = {
        snd : x => send(getVal(x)),
        set : (x,y) => registers.set(x,getVal(y)),
        add : (x,y) => registers.set(x,getVal(x) + getVal(y)),
        mul : (x,y) => registers.set(x,getVal(x) * getVal(y)),
        mod : (x,y) => registers.set(x,getVal(x) % getVal(y)),
        rcv : x => { let r = recv(); if (typeof(r) === 'undefined') blocked = true; else { registers.set(x,r); blocked = false; } },
        jgz : (x,y) => curPos += (getVal(x) > 0 ? getVal(y) : 1)
    }
    const execute = () => {
        let [ins,arg1,arg2] = instructions[curPos]
        commands[ins](arg1,arg2)
        if (!blocked && ins != "jgz") curPos++
        if(curPos < 0 || curPos >= instructions.length) throw Error(`program ${id} exited`)
        return blocked
    }
    function showState() {
        console.log(`Prog ${id}`, curPos,instructions[curPos],blocked,registers)
    }
    return {execute,showState}
}

We also need a method to run until we’re blocked on a receive command. All the logic slowly moved out of here into my interpreter during my solution to part 2, so there’s not a lot left now:

function runUntilBlocked(interpreter) {
    //interpreter.showState()
    while (!interpreter.execute()) { //
    }
}

With these two methods in place we can solve part 1, which requires us simply to record the last value sent when we arrive at the first receive command.

let sent = -1
runUntilBlocked(interpreter(instructions, 0, n => sent = n, () => undefined))
return sent;

For part 2, things got a little more interesting. Two versions of the program run concurrently, each getting blocked in its receive method until the other one sends it some data via the send method. The program ends when both programs are blocked waiting for each other. The answer for part 2 was to count the total number of values sent by program 1.

So it was simply a case of setting up two queues, connecting them up to be the input and output for the two programs and then keep running until both queues were empty

let sent0 = []
let sent1 = []
let i0 = interpreter(instructions, 0, n => sent0.push(n), () => sent1.shift())
let totalSent1 = 0;
let i1 = interpreter(instructions, 1, n => { sent1.push(n); totalSent1++ }, () => sent0.shift())
do {
    runUntilBlocked(i0)
    runUntilBlocked(i1)
} while(sent0.length > 0 || sent1.length > 0)
return totalSent1

It should have been simple, but two silly mistakes slowed me down. Here’s my buggy code. See if you can spot the problems:

rcv : x => { let r = recv(); if (typeof(r) === 'undefined') blocked = true; else registers.set(x,r); } },
jgz : (x,y) => curPos += (getVal(x) ? getVal(y) : 1)

My mistakes were: first, the rcv command never reset blocked to false, meaning my program exited too early. And second, my jgz (jump greater than zero) command wasn’t checking greater than zero – it was just checking non-zero. In this case, they were both problems I found through code review rather than through debugging.

As a bonus, I made a short video showing off my development setup I’m using for solving this year’s Advent of Code challenges which is basically VS Code, Node.js, Jasmine, ESLint. To see the full source code including ESLint, Jasmine and npm config files, see my GitHub repostory. I’m really liking using VS Code as a development environment, and I can foresee it replacing Visual Studio for many types of development (including .NET core).