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.

0 Comments

In today’s Advent of Code puzzle, we were generating “hashes”. I won’t go into huge detail on the algorithm, but part of the problem required us to reverse a section of a circular array. This is the type of problem that is in theory quite simple, but very easy to make silly mistakes on. So I took a test-driven approach. I made some simple Jasmine test cases to cover various edge cases including reversing a section that wraps around the end of the array.

const reverseTests = [ [[0,1,2,3,4], 0, 2, [1,0,2,3,4] ],
[[0,1,2,3,4], 1, 3, [0,3,2,1,4] ],
[[0,1,2,3,4], 2, 3, [0,1,4,3,2] ],
[[0,1,2,3,4], 3, 3, [3,1,2,0,4] ],
]

describe("2017 day 10", function() {
    it ("can reverse sections", function() {
        for (let [input,pos,len,expected] of reverseTests)
            expect(reverseSection(input,pos,len)).toEqual(expected);
    })

and that allowed me to create my reverseSection function with confidence, with the unit tests quickly identifying an off by one error I needed to fix (missing a –1).

function reverseSection(list, currentPos, length) {
    let out = Array.from(list)
    for(let n = 0; n < length; n++) {
        out[(n+currentPos)%out.length] = list[(currentPos+length-n-1)%out.length]
    }
    return out;
}

Destructuring Objects into Existing Variables

I’ve talked several times in this series about ES6 destructuring – it’s a really nice feature, but today I needed to use it in a slightly different way. I had an applyLengths function which returned an object containing three properties – result, currentPos and skipSize.

If I wanted to destructure the output of that function into some new variables, I could do that quite easily like this:

let {result,currentPos,skipSize} = applyLengths(/* args */);

But what if I already have declared some local variables and want to assign to them instead? In my case I had local variables called start, currentPos and skipSize. To perform that assignment using ES6 destructuring I need to do the following:

({result:start,currentPos,skipSize} = applyLengths(/* args */);

There are two important things to observe here. First, when the variable name we want to assign to doesn’t match the property name we can use a colon syntax to indicate the mapping from object property to variable name. In this case result:start puts the result property of the object returned by applyLengths into the start variable.

Second, you’ll notice the whole statement is surrounded by parenthesis. This is needed to help the compiler understand that this is a destructuring assignment and not simply the start of a code block.

Range and Batch Utilities

Finally, for today’s problem I needed a couple of utilities. First, a range function that outputs incrementing numbers, to help me fill an array with the numbers 0 to 255. I’d already made a range function in my utilities module:

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

So I could use that to initialize my array:

let start = Array.from(range(0,256));

And I also needed to batch up entries in an array into groups of 16. I made another general purpose utility function to help with that, again making it an ES6 generator function for maximum reusability in the future. This implementation returns the batches as arrays of elements, and emits the leftovers as a final batch at the end.

function* batch(seq, size) {
    let b = []
    for(let el of seq) {
        b.push(el)
        if (b.length === size) {
            yield b;
            b = []
        }
    }
    if (b.length > 0)
        yield b
}

And this simplified the xor operation I needed to do to build the hash:

let hash = ""
for(let b of batch(start,16)) {
    let xor = b.reduce((a,b) => a^b)
    hash+= ("0" + xor.toString(16)).slice(-2)
}

I could of course start simplifying this code further by making versions of map and reduce that work on iterables. However, I’d also want a way joining them in a pipeline to preserve the ordering of data flow in my code. In other words, I want to write code like sequence.filter(f1).map(f2).reduce(f3) instead of reduce(map(filter(sequence,f1),f2),f3). I’ve seen various approaches to this such as chain in lodash and pipe in Ramda, but have yet to try these out myself.

Let me know in the comments if you have a preferred way of setting up a functional pipeline in a LINQ style in JavaScript.

Here’s my code in GitHub for today’s challenge.

0 Comments

In today’s Advent of Code puzzle, we needed to parse a long string, counting how deep into nested brackets we were, and following rules to ignore “garbage”.

I was able to create one function that solved both parts of the puzzle by looping through all characters in the input string, counting how many “garbage” characters we’d seen, and tracking how deep our nesting level was so we could keep a “score” up to date:

function parseInput(input) {
    let nestingLevel = 0;
    let score = 0;
    let garbageChars = 0;
    let inGarbage = false;
    for(let n = 0; n < input.length; n++) {
        let c = input[n]
        if(c === '!') n++;
        else if(c === '>') inGarbage = false;
        else if(inGarbage) garbageChars++;
        else if(c === '<') inGarbage = true;
        else if(!inGarbage && c === '{') score += ++nestingLevel;
        else if(!inGarbage && c === '}') nestingLevel--;
    }
    return [score,garbageChars];
}

Testing with Jasmine

I decided again to create some Jasmine tests to check my answers against the test cases. I decided to implement my own very simplistic data driven tests, and one nice feature of the Jasmine test runner, is that it will keep running all the expects, rather than stopping after the first failure, so just one run of these tests is needed to discover all failing test cases.

const { parseInput } = require("../2017/09/solve")

const testScores = [ ['{}', 1 ],
    [ '{{{}}}', 6 ],
    [ '{{},{}}', 5 ],
    [ '{{{},{},{{}}}}', 16 ],
    [ '{<a>,<a>,<a>,<a>}', 1 ],
    [ '{{<ab>},{<ab>},{<ab>},{<ab>}}', 9 ],
    [ '{{<!!>},{<!!>},{<!!>},{<!!>}}', 9 ],
    [ '{{<a!>},{<a!>},{<a!>},{<ab>}}', 3 ] ]

const garbageCounts = [
    [ '<>', 0 ],
    [ '<random characters>', 17 ],
    [ '<<<<>', 3 ],
    [ '<{!>}>', 2 ],
    [ '<!!>', 0 ],
    [ '<!!!>>', 0 ],
    [ '<{o"i!a,<{i<a>', 10 ],
];

describe("2017 day 9", function() {
    it ("scores the tests correctly", function() {
        for (let [s,n] of testScores)
            expect(parseInput(s)[0]).toBe(n);
    })

    it ("counts garbage chars correctly", function() {
        for (let [s,n] of garbageCounts)
            expect(parseInput(s)[1]).toBe(n);
    })
});

Having these unit tests was hugely valuable. My first attempt at solving part 2 failed because I’d ordered my else if checks wrong, so I moved one up a line and that solved part 2, but introduced a regression for part 1. That’s where taking the extra time to create unit tests really pays off. I might not have noticed I’d broken part 1’s answer without them. But it was third time lucky as I eventually got these three else if clauses into the right order:

else if(c === '>') inGarbage = false;
else if(inGarbage) garbageChars++;
else if(c === '<') inGarbage = true;

Clean up your code with ESLint

I’ve not yet mentioned another development tool I’m using and that’s ESLint. To get it working I installed the ESLint extension for VS Code and then I installed ESLint in my project with npm install eslint.

What happened next was initially quite frustrating as you need to configure ESLint with an .eslintrc.js configuration file. This can be set up to “extend” a set of rules, and so I chose to extend the “eslint:recommended” rules which seems to be a good starting point.

However, I found it soon complained about me using undeclared symbols. To fix that I needed to tell it about my “environment”. I’m using node, so I can use things like require, I’m using ES6 so I can use things like Map, and my tests are using Jasmine, so I can use things like describe. I also overrode the default no-console rule.

Here’s the config file I ended up with:

module.exports = {
    "extends": "eslint:recommended",
    "parserOptions": {
        "ecmaVersion": 6
      },
      "env": {
        "browser": false,
        "node": true,
        "es6": true,
        "jasmine": true
    },
    "rules": {
        "no-console": "off"
    }
};

With this in place, it very helpfully warns me about unused parameters, undeclared variables or other places where I’m not following good JavaScript coding practices. After configuring it, I went through and fixed all ESLint warnings for my 2015 answers, and you can see here the sorts of changes I made. On the whole most of them I thought were steps in the right direction. There were a few you could legitimately quibble with, but you can always add additional rules to your ESLint config file to customise it to your taste.

I definitely recommend getting a setup where the linter is showing you issues while you’re in your editor, encouraging you to fix up style problems as you go rather than leaving it to the end.

As usual, you can explore my solutions on GitHub

0 Comments

In today’s Advent of Code puzzle, we found ourselves needing to interpret a program. This has been a recurring theme over the years, and so the steps to solve it were familiar. First, parse the instructions, then, run the instructions, and finally, extract the answer to each part of the puzzle.

Parsing with RegEx

The instructions in our puzzle input took the following form:

sg inc 242 if kmh <= 9

In this example, if register khm is less than or equal to 9, increment the value of register sg by 242. Here’s my rough and ready regex that I used to parse each instruction into a simple object:

function parseInstruction(instruction) {
    let g = /(\w+) (\w+) (-?\d+) if (\w+) ([<>=!]+) (-?\d+)/.exec(instruction)
    return { target: g[1], op: g[2], amount: Number(g[3]), testReg: g[4], testOp: g[5], testAmount: Number(g[6]) };
}

Running the Instructions

To run the instructions we needed to store the state of all the registers. I opted once again for the ES6 Map. I passed the empty map into my executeInstructions function which looped through each instruction executing each instruction. I made a helper to test if the condition was met, testRegister, and another helper, applyOp, to apply the operation to a register.

function executeInstructions(registers, instructions) {
    for (let i of instructions) {
        if (testRegister(registers.get(i.testReg) || 0, i.testOp, i.testAmount)) {
            registers.set(i.target, applyOp(registers.get(i.target) || 0, i.op, i.amount));
        }
    }
}

Once again, in JavaScript land, it’s easier to mutate our state than go for a fully functional approach. If we had an immutable map type available to us, then that could easily be used here.

To cope with registers that are not yet set in the map, we can use the shorthand registers.get(i.testReg) || 0 syntax to return 0 if the key is not found in the map.

The initial helper functions testRegister and applyOp I created looked like this:

function testRegister(value, op, amount) {
    switch(op) {
        case '<': return value < amount;
        case '>': return value > amount;
        case '<=': return value <= amount;
        case '>=': return value >= amount;
        case '!=': return value !== amount;
        case '==': return value === amount;
        default: throw new Error("invalid test op " + op)
    }
}

function applyOp(value, op, amount) {
    switch(op) {
        case 'inc': return value + amount;
        case 'dec': return value - amount;
        default: throw new Error("invalid op " + op)
    }
}

Solving the Puzzle

The answer to part 1 was just to find the maximum register value. This can be done using the max helper function I created for an earlier puzzle to find the maximum value

let part1 = max(registers.values())

For part 2, we were required to return the largest value that had been in any register. This is easily tracked in the executeInstructions function just before we set the register value

let newValue = applyOp(registers.get(i.target) || 0, i.op, i.amount)
largest = Math.max(largest,newValue)
registers.set(i.target, newValue);

Refactoring

Once I’ve solved an Advent of Code puzzle, if time permits I like to refactor my solution a bit. I’m not trying to “code golf” it, but often simplifications are possible.

For example, the testRegister and applyOp functions are very similar, and could be combined into one, using a lookup that works both for the conditional tests and increment or decrements:

const ops = {'<':(a,b)=>a<b,'>':(a,b)=>a>b,'<=':(a,b)=>a<=b,'>=':(a,b)=>a>=b,'!=':(a,b)=>a!==b,'==':(a,b)=>a===b,'inc':(a,b)=>a+b,'dec':(a,b)=>a-b };
const applyOp = (val,op,amt) => ops[op](val,amt)

I also changed the output structure of the parseInstruction function to better reflect the similarity between the test condition and action:

function parseInstruction(instruction) {
    const g = /(\w+) (\w+) (-?\d+) if (\w+) ([<>=!]+) (-?\d+)/.exec(instruction)
    return { action: {reg:g[1], op:g[2], amount:Number(g[3])}, test: {reg:g[4], op:g[5], amount:Number(g[6])} };
}

With these changes in place, my updated version of executeInstructions uses ES6 destructuring to unpack the instructions and tracks the largest value. One benefit of this implementation is that executeInstructions is at least a pure function now, as it creates its own map of registers that it returns.

function executeInstructions(instructions) {
    const registers = new Map();
    let largest = 0;
    const applyOpToReg = ({reg,op,amount}) => applyOp(registers.get(reg) || 0, op, amount)
    for (let {action,test} of instructions) {
        if (applyOpToReg(test)) {
            let newValue = applyOpToReg(action)
            largest = Math.max(largest,newValue)
            registers.set(action.reg, newValue);
        }
    }
    return {largest,registers};
}

Of course, more improvements are possible, and I suspect that this won’t be the last of this sort of problem in this year’s Advent of Code challenges, so maybe I’ll improve it further. As usual you can see my solution on GitHub.

0 Comments

Today’s Advent of Code challenge was a little trickier than previous ones, and I didn’t help myself by making a couple of silly mistakes on part 2. It did however provide an opportunity to use some techniques we’ve not yet put to use including regular expressions, recursion, depth first searches and debugging node.js in Visual Studio Code.

Parsing input with regex

First of all, we needed to parse input that looked like this:

ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq

JavaScript has a built-in regex syntax, that is more straightforward to work with than the .NET RegEx class. By calling exec on my regex I can then easily access the matched groups to parse the input into a list of “programs”

const parseInput = input => input.map(x => 
    /(\w+) \((\d+)\)( -> ([\w, ]+))?/.exec(x))
    .map(g => ({name:g[1],weight:Number(g[2]),children:g[4]?g[4].split(', '):[],parents:[] }))

Building the tree

I then created a simple function to update my list to properly link to all children (rather than just having an array of their names), and include backwards links to parents. I used the ES6 Map again as an easy way to create a lookup of nodes by name.

function buildTree(programs) {
    let nodes = new Map(programs.map(p => [p.name,p]));
    
    for(let p of programs) {
        p.children = p.children.map(c => nodes.get(c))
        for(let c of p.children) {
            c.parents.push(nodes.get(p.name))
        }
    }
    return programs; 
}

One gotcha I hit with Map is that you must use get rather than square brackets syntax to perform lookups.

image

Finding the root

The solution to part 1 was to find the root of the tree – i.e. the node with no parents. This could easily be done with the find method on Array:

function findRoot(programs) {
    return programs.find(p => p.parents.length === 0);
}

Weighing nodes

For part 2, we needed the ability to calculate a node’s “weight”. This meant adding its own weight to the weights of all its children. This can be done simply with recursively calling to get the weight of our children, summing them together with reduce.

function getNodeWeight(node) {
    return node.weight + node.children.reduce((a,b) => a + getNodeWeight(b),0)
}

Finding the unbalanced node

The main challenge of part 2 was to find the “unbalanced” node and return the new weight it should be given. I chose to start from the root node, and again recursively look for an “unbalanced” node. An unbalanced node is one where all of its children don’t have the same weight.

My solution is below, but I made two mistakes that slowed me down. First, this needed to be a depth-first search. In other words, I must first check if my children are unbalanced before checking if I am unbalanced. So the function starts by recursively checking the children and only then checking whether this node is unbalanced.

function findUnbalancedNode(node) {
    if (node.children.length === 0) return;
    for(let c of node.children) {
        let unbalanced = findUnbalancedNode(c);
        if (unbalanced) return unbalanced;
    }

    let weights = node.children.map(getNodeWeight);
    let [differentIndex,correctIndex] = findDifferentIndex(weights);
    if (differentIndex < 0) { // all same
        return;
    }
    else {
        let difference = weights[differentIndex] - weights[correctIndex];
        let differentNode = node.children[differentIndex];
        return {differentNode,correctWeight:differentNode.weight - difference};
    }
}

My second mistake was in the findDifferentIndex function. The premise is simple – in an array of numbers where one maybe differs from the others, find the index of the different one. It sounds simple, but I managed to get it wrong resulting in me submitting some wrong answers for the first time this year. Here’s a working version (that I really should clean up further now its fixed)

function findDifferentIndex(arr) {
    let n = arr.findIndex(w => w !== arr[0])
    if (n < 0) return [-1];
    return (n === 1 && arr[n] === arr[arr.length - 1]) ? [0,n] : [n,0];
}

This is the type of mistake that a good suite of unit tests should find. For example, here are some Jasmine tests that had I written them up front would have found my mistake immediately:

it ("finds different index if different is first", function() {
    expect(findDifferentIndex([2,1,1,1])).toEqual([0,1])
})

it ("finds different index if different is last", function() {
    expect(findDifferentIndex([1,1,1,2])).toEqual([3,0])
})

it ("finds different index if different is second", function() {
    expect(findDifferentIndex([1,2,1,1])).toEqual([1,0])
})

Debugging Node in VS Code

My troubles getting part 2 correct meant I had my first opportunity to try out debugging node in Visual Studio Code. I was very impressed with how easy it was. Simply add a breakpoint, hit F5 and VS Code automatically launched index.js and attached a debugger. It really was very straightforward and its impressive how VS Code is good enough to be an IDE replacement in many scenarios.

image

As usual you can explore my full solution to today’s puzzle on GitHub.