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.

0 Comments

I didn’t have a lot of time for todays’ Advent of Code challenge, but I was able to get my two stars, so here’s a quick breakdown of how I solved it.

We were given an which could be thought of as a list of locations and reachable destinations. Here location 0 can reach locations 5, 8 and 10:

0 <-> 5, 8, 10

If we then had another line saying that:

5 <-> 0, 7, 9

That means that from 0 you can also reach 7 and 9. So locations 0, 5, 7, 8, 9 and 10 are effectively in a “group” – they can all be reached from one another.

I parsed each line with a regex like this:

const parse = s => {
    let [,from,dest] = /(\d+) <-> ((\d+)(, \d+)*)/.exec(s);
    return {from,to:dest.split(', ')}
}

For part 1 I needed to find how many locations (called ‘programs’ in this puzzle) are reachable from location 0. I did this by starting at 0, maintaining an ES6 Set of places I’d already visited, and then recursively following all the destinations until I’d seen them all.

const getGroup = (start,programs) => {
    let s = new Set()
    visit(s, programs[start].to, programs)
    return s;
}

const visit = (visited,destinations,programs) => {
    for(let d of destinations) {
        if (!visited.has(d)) {
            visited.add(d)
            visit(visited,programs[Number(d)].to,programs)
        }
    }
}

That left me with a set containing every destination reachable from 0, meaning the answer was just its size.

For part 2, I had to find out how many unique groups (locations from which you can reach all the other locations in the group) there were. I solved this by maintaining a set of locations that were part of any group. So I calculated the group containing 0, and put all locations in that group into the set. Then I found the next location that wasn’t in the set of already visited locations, calculated its group, and so on.

let groups = 0;
let inAnyGroup = new Set();
for(let g = 0; g < programs.length; g++) {
    if(!inAnyGroup.has(g.toString())) {
        groups++;
        let group = getGroup(g,programs);
        for(let m of group) {
            inAnyGroup.add(m)
        }
    }
}
return groups;

As I said, I didn’t have a lot of time today to optimize my solution, but it performs pretty quickly and shows off how the Set object can be very useful for tracking unique values. I’m sure there were plenty of other approaches that could have been taken today so do let me know in the comments how you tackled it. As usual you can find my full solution code on GitHub.

0 Comments

Today’s Advent of Code puzzle required us to follow instructions to move around a hexagonal grid. I quickly realized I would need to come up with some kind of coordinate system to track where I was in the grid. And then we needed to be able to work out the distance between hexagons in terms of minimum number of steps to get from one to the other.

I started off by sketching out some ideas for a coordinate system for a hexagonal grid. It is possible to give each hexagon a unique position in a 2D grid by shifting each vertical column of hexagons down half a step.

image

This puts then nicely in a 2D grid but with the quirk that of the eight cells surrounding each cell in the grid, 6 of them are truly adjacent, whilst 2 of them are 2 steps away. I realised that if I went with this coordinate system, calculating the distance could end up becoming complex.

So I asked myself – do I want to spend my time for today inventing my own hex grid coordinate system and distance algorithm? Or do I want to learn what the “best practice” for hexagonal grids in code is? Maybe the second option feels a bit like “cheating” for something like Advent of Code, but part of the appeal of these puzzles is the opportunity for me to learn new algorithms and techniques, so I was happy to do a bit of research before attempting today’s puzzle.

Coordinate Systems for Hexagonal Grids

It didn’t take long to discover there is a definitive article on the hexagonal grids, at Red Blob Games. It brilliantly describes various coordinate systems, with beautiful interactive diagrams. Several options are discussed, but the one that seemed most promising was a “3 dimensional” coordinate system. From every hexagon there are essentially three axes you can move forwards and backwards in – the North/South axis, the NE/SW axis, and the NW/SE axis. It’s better to call them x,y, and z as the mapping is a little more complex as we’ll see in a moment.

Following a Path

First I needed a function that moved from my starting position [0,0,0] following a direction to get the new coordinate. The move function takes a position and a direction and returns the new position. One fascinating feature of this coordinate system is that for each move we actually change the values of two coordinates. I put the vectors to move by into a lookup dictionary and you can see the symmetry on each axis:

const move = (from,dir) => lookup[dir].map((v,n) => v+from[n])

const lookup = {
    "n": [0,1,-1],
    "s": [0,-1,1],
    "nw": [-1,1,0],
    "se": [1,-1,0],
    "ne": [1,0,-1],
    "sw": [-1,0,1],
}

Following the Path

Of course, we had plenty of steps to follow, and I went for a more functional approach, using reduce to apply the move to each direction in the sequence, tracking the current position through. In this function, the input pathis a comma separated list of directions so we just need to split it before calling reduce with a starting position of [0,0,0].

const followPath = path => path.split(',').reduce((pos,dir) => move(pos,dir),[0,0,0])

Distance Calculation

The main motivation for finding a good coordinate system for my hex grid was to make the distance calculation easy. By simply inspecting the output from the test cases, I could see that the distance was simply the largest absolute value of any of the x,y and z coordinates. The article at Red Blob Games confirms this, supplying two ways to calculate the distance. I went with the max absolute value approach:

const distance = ([x,y,z]) => Math.max(Math.abs(x),Math.abs(y),Math.abs(z))

Adding Extra State to Reduce

For part 2 we had to discover what the furthest distance we’d been from the start position was at any point on our journey. This is where many developers new to functional programming can get frustrated with it. If only followPath had been implemented with a straightforward loop, then each time through the loop we could calculate the distance from the start and update a max value. How can our reduce solution produce two answers?

Well the answer is that the accumulator state can actually contain more than one piece of information. For example, in our case it can contain the current position and the maximum distance away from the start. So let’s say that the accumulated state is an array containing a position and a max distance from the start. It’s initial value is now [[0,0,0],0]. Now in reduce, we still call move but also calculate a new max distance:

const followPath = path => path.split(',')
                            .reduce(([pos,maxdist],dir) => {
                                let newPos = move(pos,dir)
                                return [newPos, Math.max(maxdist,distance(newPos))] }
                                ,[[0,0,0],0])

Of course, this starts to look quite messy, so we might decide to split updateState out into its own function:

const updateState = ([pos,maxdist],dir) => {
    const newPos = move(pos,dir)
    return [newPos, Math.max(maxdist,distance(newPos))] 
}
const followPath = path => path.split(',').reduce(updateState,[[0,0,0],0])

Now the updated followPath function can solve both parts of the puzzle:

function solve(input, part) {
    const [endPos,maxDist] = followPath(input[0])
    return (part === 1) ? distance(endPos) : maxDist;
}

Don’t Reinvent the Wheel

The lesson from today’s challenge is that very often in programming, there are existing algorithms that can elegantly and efficiently help us solve the problems. Whilst it might be fun to try to derive these yourself from first principles, in real world software engineering it’s almost always best to spend some time learning about these tried and tested algorithms and incorporate them into your own toolkit. Whether its sorting or shuffling a list, or searching a graph, you’ll usually find there’s an established algorithm that performs a lot better than trying to invent your own.