Posted in:

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.