0 Comments

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.

0 Comments

The difficulty level has been slowly ramping up in this year’s Advent of Code challenge, and today’s puzzle initially sent me off down a dead end.

Part 1 was simple enough. We’re given a series of “dance moves”, involving rearranging the order of a line of dancers. First of all I needed to parse the instructions, which I did with a regex:

let instructions = input[0].split(',')
     .map(i => i.match(/x(\d+)\/(\d+)|s(\d+)|p([a-z])\/([a-z])/))
     .map(([x,a,b,c,d,e]) => ({move:x[0],exA:Number(a),exB:Number(b),spin:Number(c),pA:d,pB:e}))

We needed two helpers to implement the three dance moves. “Exchange” swaps the position of two dancers, while “spin” moves a group of dancers from the end of the line to the front:

let exchange = (state,a,b) => {
    let tmp = state[a]
    state[a] = state[b]
    state[b] = tmp
    return state;
}
let spin = (state,n) => {
    return state.slice(state.length - n).concat(state.slice(0,state.length - n))
}

We can now simply iterate through the instructions and apply them, turning the final state back into a string:

function dance(instructions, start) {
    let s = [...start]
    for(let i of instructions) {
        switch(i.move) {
            case "x": s = exchange(s,i.exA,i.exB); break;
            case "s": s = spin(s,i.spin); break;
            case "p": s = exchange(s,s.indexOf(i.pA), s.indexOf(i.pB)); break;
        }
    }
    return s.join('')
}

So far so good. But for part 2 we were asked to repeat the dance 1 billion times. A quick calculation from the time taken to solve part 1 revealed this would take 2117 years! So I knew I couldn’t just optimise my part 1 solution – even a hundredfold speedup would be way too slow.

I realised there must be a way to short-circuit the problem. My first idea was that maybe after a certain number of dances, we would get back to the starting point. So if after 7 dances we are back to the starting position then after 7 million dances we will be in the same position again. However, when I considered how many possible orderings of dancers there were (16 factorial by my calculation), I abandoned this idea.

My second idea was that maybe the instructions for one dance could be collapsed into a simple reordering. Maybe at the end of the dance the dancer who started in position 1 always ends up in position 6, and so on for each dancer.

So I took the answer for part 1 and generated a lookup of starting to end position for each dancer. And then I reapplied it one billion times:

let m = new Map()
let part1 = "pkgnhomelfdibjac"
for(let n = 0; n < state.length; n++) {
    m.set(n, part1.indexOf(state[n]))
}
state = [..."abcdefghijklmnop"]
for(let n = 0; n < 1000000000; n++) {
    let next = []
    for (let i = 0; i < 16; i++) {
        next[m.get(i)] = state[i]
    }
    state = next;
}
return state.join('')

This took three minutes to run, but it generated the wrong answer. And on reflection, it wasn’t hard to see why this was never going to work. The “partner” dance move swapped dancers based on their original position, not their current position, so this optimization is way too simplistic.

So it was back to the drawing board, and it turns out that my first idea was the better one. If we repeatedly perform the dance, and wait until we see the starting state again, we’ve found the cycle length. From the cycle length we know how many additional dances are needed to make it up to one billion:

let cur = start;
let repetitions = 1000000000;
for(let n = 0; n < repetitions; n++) {
    cur = dance(instructions,cur);
    if (cur === start)
    {
        let cycle = n+1;
        let extras = repetitions % cycle;
        n = 0;
        repetitions = extras+1;
    }
}
return cur

With this optimization in place, I get the solution in a very respectable 300ms. The cycle size for my input was just 60 meaning only 40 extra repetitions were required. However, we could speed that up even further by storing the output for each dance, so that once we’d found the cycle, we could just return the answer we calculated from the first time through the cycle. That shaves it down to 200ms and looks like this (although I have just left my solution for part 2 as is):

let cur = start;
let solutions = []
let repetitions = 1000000000;
for(let n = 0; n < repetitions; n++) {
    cur = dance(instructions,cur);
    solutions.push(cur)
    if (cur === start)
    {
        let cycle = n+1;
        let extras = repetitions % cycle;
        return solutions[extras-1]
    }
}

So today’s challenge was a good lesson in optimization techniques, and a reminder not to be too quick to dismiss your initial ideas. I was wrong about the total number of possible orderings of dancers – its not 16 factorial (20,922,789,888,000), its a more reasonable 140 squared (19,600) – courtesy of the mathematical geniuses on the AoC reddit. And in any case just because the number of possible orderings is high, doesn’t mean the cycle size was high. If I’d started off by searching for a cycle, with an upper bound of say 10,000 repetitions I would have wound up at the answer much quicker.

0 Comments

A couple of days ago I mentioned that my utils library is slowly growing with LINQ-like methods as I’ve worked through solving the daily Advent of Code challenges this year. For today’s puzzle, I needed to create a new zip method, as well as use count and take.

The puzzle required us to generate a sequence of numbers, and to do so I created an ES6 generator function capable of generating the sequences we needed for both parts of the puzzle:

function *generator(seed,factor,test) {
    let cur = seed;
    for(;;) {
        cur = (cur*factor)%2147483647
        if (!test || test(cur)) yield cur;
    }
}

This method generates an unending sequence, but we only needed to take a certain number of elements from the sequence (40 million for part 1, 5 million for part 2). So I need a take method that takes the first n elements from an iterable sequence. Here’s my implementation:

function *take(seq, count) {
    let n = 0;
    for(let el of seq) {
        if (++n > count) return;
        yield el;
    }
}

Next, we were comparing elements in two sequences, and that’s where a zip method comes in handy. My zip method iterates through both sequences, yielding a two element array containing the pair of elements at the same position. It exits when either sequence ends.

function *zip(seq1,seq2) {
    let it1 = seq1[Symbol.iterator]()
    let it2 = seq2[Symbol.iterator]()
    for(;;) {
        let el1 = it1.next()
        if(el1.done) return;
        let el2 = it2.next()
        if(el2.done) return;
        yield [el1.value,el2.value]
    }
}

And finally we needed to count how many elements in the zipped sequence matched a certain condition. I could do this by filtering my sequence with my where utility method and then passing it into my count method. But I decided to upgrade my count method to take an optional predicate to count all elements that match a certain condition:

function count(seq, predicate) {
    let n = 0;
    for(let el of seq) {
        if (!predicate || predicate(el)) n++
    }
    return n;
}

With these very generic and reusable utility methods at my disposal, solving the challenge becomes very easy. I can combine them to count all the elements in the pair of sequences that match according to a specific rule:

function countMatch(seq1,seq2,n) {
    const comp = ([a,b]) => (a&0xFFFF) === (b&0xFFFF); // brackets are needed!
    return count(take(zip(seq1,seq2),n),comp)
}

One gotcha I ran into was the operator precedence of my comparison. The equality comparison clearly has higher precedence than the bitwise AND operator which was not what I was expecting:

image

All that remained was to parse my input and then use my generator and countMatch functions to solve both parts of today’s puzzle:

function solve(input, part) {
    const parse = s => Number(/\d+/.exec(s)[0])
    let genAStart = parse(input[0])
    let genBStart = parse(input[1])
    const aFactor = 16807, bFactor = 48271

    if (part === 1) 
        return countMatch(generator(genAStart,aFactor), 
                        generator(genBStart,bFactor), 40000000);
    else 
        return countMatch(generator(genAStart,aFactor,n=>(n%4)===0), 
                        generator(genBStart,bFactor,n=>(n%8)===0), 5000000);
}

As my utils library is slowly growing, I’ve started to break out the Jasmine tests for each utility out into their own “Spec”. It’s important to keep this utility code well covered by tests as these methods are being relied on in more and more places, and are slowly picking up new capabilities, such as the optional predicate for the count function. A good suite of unit tests protects against regressions and also is invaluable when attempting performance optimizations. Maybe I’ll see if I can turn my utils library into an npm package once I’m done.

0 Comments

Today’s Advent of Code puzzle required us to reuse the hash generation code from day 10. We had to create 128 hashes, and then each of the 128 bits of those hashes was used to fill in a 128x128 grid.

For part 1, we simply needed to count how many bits were set in the grid. I created a helper function called getRow to calculate the hash for each row, calling into the hashString method from day 10 which I modified to return the hash as a byte array.

const getRow = (key,row) => hashString(`${key}-${row}`)

Now we can solve part 1 by counting how many bits are set in each of the bytes of the 128 hashes

let totalBits = 0;
for(let n = 0; n < 128; n++) {
    totalBits += getRow(key,n).reduce((a,b) => a + bitsSet(b),0)
}
return totalBits;

This uses a bit counting function called bitsSet. My initial solution was not one that I expected to perform well, but it was nice and simple – format the number as a binary string and count how many “1” characters there are:

function bitsSet(byte) {
    let n = 0;
    for(let c of byte.toString(2)) {
        if (c === '1') n++;
    }
    return n;
}

A faster bit counting approach (courtesy of stack overflow) would be something like this:

function bitsSet2(n) {
    let count = 0;
    while (n) {
      n &= (n-1);
      count++;
    }
    return count;
}

However, switching to this counting method didn’t make any noticeable performance impact, as it was the hash generation that was taking the time. And that’s an important performance tuning lesson for real world projects – make sure you measure what is taking the time before investing too much effort in optimizing a particular method. It’s all too easy to invest a lot of effort optimizing the wrong bit of code.

Part 2 introduced an interesting problem – we had to count “regions” of bits set within the grid. Two bits are in the same region if they are adjacent to another set bit.

To make life easier for me, I decided to expand the grid into a 128x128 array containing the ‘#’ and ‘.’ characters for bits that were set and empty. This meant I could visualise grids easily, and also would make it easier to mark bits as having been visited by my region counting code. Here’s the buildGrid and expandHash function that produces the grid:

const buildGrid = key => {
    let grid = []
    for(let n = 0; n < 128; n++) {
        grid.push(expandHash(getRow(key,n)))
    }
    return grid;
}

const expandHash = hash => {
    let b = []
    for (let h of hash) {
        let m = 0x80;
        while(m) {
            b.push(m&h ? '#' : '.')
            m = m>>1
        }
    }
    return b;
}

Now to count regions, I simply needed to iterate through all cells in the grid and whenever I came across a bit that was set, find all other bits in that region and unset them. The clearRegion recursively clears out bits in the same region from a starting point (this would be a cool algorithm to visualize):

const clearRegion = (grid,x,y) => {
    if(grid[x][y] !== '#') return
    grid[x][y] = '.';
    if(y+1 < grid[x].length) clearRegion(grid,x,y+1)
    if(y > 0) clearRegion(grid,x,y-1)
    if(x+1 < grid.length) clearRegion(grid,x+1,y)
    if(x > 0) clearRegion(grid,x-1,y)
}

Now we can solve part 2 by counting regions, clearing them as we go so no region gets double counted:

const countRegions = grid => {
    let regions = 0;
    for(let x = 0; x < grid.length; x++) {
        for(let y = 0; y < grid[x].length; y++) {
            if(grid[x][y] === '#') {
                regions++;
                clearRegion(grid,x,y)
            }
        }
    }
    return regions;
}

My solution to today’s puzzle takes about 3.5 seconds, which is one of the slower solutions, but the bulk of that time is spent calculating the hashes. So if I wanted to speed it up significantly, I’d need to revisit my solution to day 10 and look for improvements.

As usual you can find my full solution on GitHub.

0 Comments

Today’s Advent of Code puzzle was a fun challenge reminiscent of the “crossy road” or frogger. Except that we’re not crossing a road, but a “firewall”. I’ll refer to it as a road in this post to keep things simple.

Parsing the input was a simple case of using regular expressions again, and I created an ES6 Map to store the “range” for each depth.

const firewall = new Map( input.map(s => /(\d+): (\d+)/.exec(s))
    .map(([,d,r]) => ([Number(d),Number(r)])))

For part 1 we crossed the road and calculated a score for each collision. The key to knowing whether there would be a collision was working out the periodicity of each of the moving “security scanners”. A scanner moves back and forth, and so if it has a depth of 4 it will cycle through positions (0,1,2,3,2,1,0,1,2,…). So every six steps it is back where it started. We could then simply work out whether there would be a collision based on modulo arithmetic:

const maxDepth = max(firewall.keys())

let score = 0;
for(let depth = 0; depth<=maxDepth; depth++) {
    let range = firewall.get(depth) || 0
    if (range > 0) {
        let period = 2 * (range - 1)
        let caught = depth%period === 0;
        if (caught)
            score += depth*range;
    }
}
return score;

For part 2 we needed to work out how long to delay before crossing the road so we wouldn’t have a collision. It wasn’t too hard to adapt the part 1 solution to this problem although there was one gotcha. The scoring algorithm for part 1 could return 0 even if there was a collision.

I refactored my code a bit so I could have a generator function that scores a “trip” across the road. It yields the score every time there is a collision. This allows me to sum all the values for part 1, and to abort the trip across the road after the first collision for part 2. Here’s the trip function:

function* trip(firewall, delay) {
    for(let [depth,range] of firewall) {
        if (isCollision(range,delay+depth)) {
            yield depth*range;
        }
    }
}

It uses a helper isCollision method using the same periodicity calculation as before. The current time is the “depth” we are at (how far across the road) plus the time we delayed by:

const isCollision = (range,currentTime) => range > 0 && currentTime%(2 * (range - 1)) === 0;

This means I can solve part 1 with a simple sum (which is a utility function to sum an iterable I created for earlier problems this year)

const scoreTrip = (firewall, delay) => sum(trip(firewall,delay));

For part 2, I needed some additional helper methods. First, to decide if I was caught as I crossed the road, I needed to see if the iterable returned by trip contains any elements. My first attempt looked like this:

function wasCaught(firewall,delay) {
    for(let s of trip(firewall,delay)) return true;
    return false;
}

But ESLint didn’t like the fact that I don’t use the s variable, but I’m not sure the for...of syntax allows me to avoid declaring a variable. So another approach would be to access the iterator protocol directly:

const wasCaught = (firewall,delay) => !trip(firewall,delay)[Symbol.iterator]().next().done;

This works fine, but is a little bit cryptic. It would be better to create another utility method that works on a generic sequence of elements and can tell me whether there are any elements in it. I came up with this any method that supports passing in an optional predicate to check for each element:

function any(seq, predicate) {
    if (typeof(predicate) === 'undefined') 
        return !seq[Symbol.iterator]().next().done
    for(let el of seq) {
        if (predicate(el)) return true;
    }
    return false;
}

Now our wasCaught method becomes:

const wasCaught = (firewall,delay) => any(trip(firewall,delay));

With that in place we can find the first value of delay where we cross the road without a collision:

for(let delay = 0; ; delay++) {
    if (!wasCaught(firewall,delay)) return delay;
}

And that works fine, but I thought it would be nice to enhance my utilities library with a couple more methods that can make my solution a bit more functional. First, I updated my range function to make the count parameter optional. This means I can generate an unending sequence of incrementing numbers:

function* range(start, count) {
    for (let n = 0; typeof(count) === 'undefined' || n < count; n++) {
        yield start++;
    }
}

And I also created a first function, returning the first element in a sequence with an optional predicate:

function first(seq, predicate) {
    if (typeof(predicate) === 'undefined') 
        return seq[Symbol.iterator]().next().value
    for(let el of seq) {
        if (predicate(el)) return el;
    }
}

This means that the solution to part 2 becomes:

first(range(0),d => !wasCaught(firewall,d))

Slowly, my utils module is picking up all the handy sequence manipulation utilities I’m used to using with LINQ or the F# seq module. Of course I know there are already plenty of JavaScript libraries with similar functionality, but the advantage of making my own is that they are named and work the way that makes sense to me, and I’m learning along the way. The downside of making my own is that mine won’t be performance optimised and are somewhat idiosyncratic.

My plan is that once I’ve finished these challenges I’ll explore some JavaScript iterable helper libraries (e.g. lodash or ramda) and see if any would work as a replacement for my own methods. Feel free to let me know in the comments which library you recommend.