Advent of Code Day 11-Don’t Reinvent the Hexagon

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.

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 path is 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.