Advent of Code Day 7-Regex,Depth First, and Recursion

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.

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.

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