0 Comments Posted in:

I did it! I got my 25 stars on Advent of Code for this year, with all my solutions in JavaScript. With today being Christmas day, I was hoping it would be a quick one and thankfully it was relatively kind. Basically, the input described a simple state machine, with the rules for what to do in each state as you filled up a “tape” with values.

I opted to speed up things a bit by not parsing the input directly and hard-coding the values from my input. I needed the start state, and number of steps as well as a bunch of rules governing what should happen in each of the six states:

let state = 'A'
const steps = 12481997
let cursor = 0
let tape = {}

let rules =
    {'A': [1,1,'B',0,-1,'C'],
     'B': [1,-1,'A',1,1,'D'],
     'C': [0,-1,'B',0,-1,'E'],
     'D': [1,1,'A',0,1,'B'],
     'E': [1,-1,'F',1,-1,'C'],
     'F': [1,1,'D',1,1,'A']}

With this in place, I just iterate through for the number of steps, and each step we update the contents of the “tape” at the current “cursor” position, as well as move to a new state. The decision of what to do is based on the value of the current position in the tape. In previous days I’ve used the ES6 Map object to store the contents of the tape, but here I’m using a regular JavaScript object as it allows a slightly simplified syntax in our loop, using destructuring arrays to assign three values each time through the loop:

for(let step = 0; step < steps; step++) {
    let rule = rules[state];
    [tape[cursor],cursor,state] = (tape[cursor]) ? 
        [rule[3],cursor+rule[4],rule[5]] :
        [rule[0],cursor+rule[1],rule[2]];
}

Finally to get the puzzle input we need to count how many entries in the tape have the value 1. JavaScript objects are not “iterables” so we need to use the for…in syntax rather than for…of:

let checksum = 0
for(let p in tape) {
    if (tape[p] === 1) checksum++;
}
return checksum;

So I managed to solve today’s puzzle relatively quickly, although sadly this year I wasn’t able to make the leaderboard on any of the 25 days. The leaderboard (top 100) is usually full by about 6:00am UK time, and I typically started solving each day’s puzzle at 7:30.

I felt a bit bad about not parsing the input for today’s puzzle, so I took the opportunity to refactor during some down-time in the afternoon to use regexes to construct the rules from the input file:

let state = input[0].match(/Begin in state (.)\./)[1]
const steps = Number(input[1].match(/after (\d+) steps/)[1])
let cursor = 0, tape = {}, rules = {}
const parseState = s => s.match(/state (.)/)[1] 
const parseVal = s => Number(s.match(/the value (\d)\./)[1])
const parseDir = s => s.match(/to the right/) ? 1 : -1 
for(let b of batch(skip(input,2),9)) { // nb blank input lines already stripped
    rules[parseState(b[0])] = [parseVal(b[2]),parseDir(b[3]),parseState(b[4]),
                               parseVal(b[6]),parseDir(b[7]),parseState(b[8])]
}

It’s been a great learning experience doing this year’s Advent of Code challenges in node.js with ES6, and I highly recommend doing a daily coding challenge like this if you want to pick up a new language. My code for all the days is available on GitHub and I’d love to hear any feedback on how I can improve my solutions.

All that remains is for me to wish you a very Happy Christmas! I hope you are able to enjoy some relaxing time with friends and family during the holidays, and that you’ve learned something useful from these blogs.


0 Comments Posted in:

Today’s Advent of Code challenge was a fun one, and allowed me to use one of my favourite ES6 features – generator functions and the yield* keyword. But it also left me wishing for some immutable collections. That will teach me for bad-mouthing immutability on day 5.

The premise was simple – we had a bunch of components that could be connected together into a bridge according to certain rules, and had to try to make the strongest (and longest) “bridge” we could out of them.

This problem is crying out for a recursive generator function that yields all possible bridges. Internally it loops through all the available components, and checks if each one can be used by comparing both its ends to the current value need.

If a piece is usable, we add it to the list of used pieces and remove it from the list of available pieces. That’s where things are sub-optimal in JavaScript as arrays are not immutable. We need to create a brand new array of used pieces, and a new filtered array of available pieces.

We then recursively call into our build function, using the yield* keyword to emit every element in the resulting sequence. We’re also tracking the strength of each bridge as we go, although it could be calculated from the values in the used array.

Finally, we actually yield a possible “bridge” whenever we run out of available pieces that we can use:

function *build(cur,used,available,strength) {
    for(let [a,b] of available) {
        if(a === cur || b === cur) {
            yield* build(a === cur ? b : a,[...used,[a,b]],available.filter(([x,y]) => !(x===a && y===b)),strength+a+b)
        }
    }
    yield {used,strength}
}

For part 1 we needed to find the strongest bridge. I’ve already got a max utility function that can do this, so we just need to parse our input and search the output of build for the strongest bridge.

let parts = input.map(i => i.split('/').map(n => Number(n)))
if (part === 1) {
    return max(build(0,[],parts,0),c => c.strength)
}

For part 2, we’re looking for the longest bridge, but using strength as a tie-breaker if multiple bridges have the same length. In F# there’s a nice trick of ordering a sequence by a tuple of the two sort elements. I wanted to find the same thing for JavaScript and it turns out there is a similar trick of using Array.sort with the || operator. So we order by length first and then strength, to put the desired bridge at the front of the list:

let bridges = [...build(0,[],parts,0)]
return bridges.sort((a,b) => b.used.length - a.used.length || b.strength - a.strength)[0].strength

I’m quite pleased with the way today’s solution turned out, although there is still scope for improvement, particularly in terms of performance. It’s not very efficient to do lots of array copying, and one obvious shortcut is to not track the used array at all, since we only need its length for this puzzle.


0 Comments Posted in:

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.