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.