# Advent of Code Day 24–Recursive Generators

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.