Posted in:

As the daily Advent of Code challenges increase in difficulty, it become harder to anticipate what the correct approach is.

For today’s challenge, we were adding numbers to a circular buffer, but each time through we were adding the number to a different position. Inserting numbers into an array is inefficient because it requires all the other elements to shift up by one position, and so I did contemplate coding a linked list instead, but given that for part 1 of the puzzle I needed only 2017 insertions, I decided that an array would probably be fast enough

I created a function called spin which worked out the place to insert the new element into the list (based on a current position and “step” size), updated the list and then returned the new current position. JavaScript arrays have a handy splice method that makes it easy to insert an element at a specific index (which reminds me of the “splicing block” I once got for Christmas as a child).

image

Here’s the spin method using splice:

function spin(buffer, steps, curPos, val) {
    const insertPos = (curPos + steps)%buffer.length + 1
    buffer.splice(insertPos, 0, val);
    return insertPos;
}

For part 1 we needed to spin for 2017 iterations, so here’s a helper function to repeat the spin algorithm the required number of times with a specific step size.

function spinFor(iterations,steps) {
    let buf = [0]
    let curPos = 0;
    for(let n = 1; n <= iterations; n++) {
        curPos = spin(buf,steps,curPos,n)
    }
    return buf;
}

For part 1 we needed to find the element after 2017 in the array, which can be solved like this:

let buf = spinFor(2017,steps)
return buf[buf.indexOf(2017)+1]

For part 2 we needed to repeat the algorithm 50 million times and find the element after 0. So in theory, we’ve already got all the tools we need to solve it:

let buf = spinFor(50000000,steps)
return buf[buf.indexOf(0)+1]

Unsurprisingly, this turned out to be horribly slow and I quickly abandoned it. Splicing an array 50 million times is not going to perform well. And there was an interesting optimization opportunity. The way the algorithm worked was that the first element in the buffer would always be 0. So we knew we were looking for the second element in the buffer after the 50 million iterations.

I started off looking for some kind of pattern in the second element. For a step size of 3, the second element was 1,2,2,2,5,5,5,5,9,9,9,12,12,12,12,16,16,16,16,16,16… with the next change in the second element coming after 218 iterations. It didn’t take me long to realise that if there was some kind of pattern it was too complex for me to deduce.

But then I realised there was a very simple optimization possible. We don’t actually need to track the whole array. So the slow splice operation can go. We just need to track what the second element is. Here’s an updated version of spin that dispenses with tracking the whole array and just tracks the value of the current position and the second element.

function spin2(steps, curPos, val, second) { 
    const insertPos = (curPos + steps)%val + 1 
    return [insertPos, (insertPos === 1) ? val : second] 
}

With this modification, I could get the answer for part 2 in about a second. And it could be made twice as fast by dispensing with any helper functions and just solving it in one simple loop:

let second = -1
let curPos = 0;
for(let n = 1; n < 50000000; n++) {
    curPos = (curPos + steps)%n + 1
    if (curPos === 1) second = n;
}
return second;

I’m pleased that I managed to resist my initial urge to implement a linked list as that would have been a classic case of “premature optimization” – overcomplicating the solution to part 1 while not helping at all for the solution to part 2.

As usual you can find my code on GitHub.