Posted in:

I made a bit of a meal of today’s Advent of Code puzzle. On one level it was simple enough. We had a grid of pixels, and each iteration we divided it up into blocks of either 2x2 pixels or 3x3 pixels (depending on grid size) and replaced each one with a larger block (2x2 blocks grew to 3x3 and 3x3 grew to 4x4).

Where it got tricky was that the lookup containing details of the replacement block needed to match any orientation of the input block. So it could be rotated or flipped in any axis.

The challenge was therefore to represent the grid in such a way that the replacement lookup would be quick. I decided that I would use a Map whose key was a string representation of each “input” block and whose value was the corresponding output. This meant taking the inputs in my puzzle input and rotating/reflecting them through all possible orientations.

So a 2x2 grid might be represented by the string “#..#” meaning that the pixels in the top left and bottom right are on. I tried a few ways of generating all the permutations of 2x2 and 3x3 grids but my initial attempts missed some possible options, so I ended up with a possibly overkill recursive solution so I could be sure I didn’t miss anything. The expand function takes a string representation of a 2x2 or 3x3 grid, then passes it into perms which recursively attempts all possible reflections and rotations, stopping when it finds configurations it’s seen before.

const flip2 = s => s[2]+s[3]+s[0]+s[1]
const flip2LR = s => s[1]+s[0]+s[3]+s[2]
const rot2 = s => s[2]+s[0]+s[3]+s[1]

const flip3 = s => s[6]+s[7]+s[8]+s[3]+s[4]+s[5]+s[0]+s[1]+s[2]
const flip3LR = s => s[2]+s[1]+s[0]+s[5]+s[4]+s[3]+s[8]+s[7]+s[6]
const rot3 = s => s[6]+s[3]+s[0]+s[7]+s[4]+s[1]+s[8]+s[5]+s[2]

function perms(s,q,ops) {
    s.add(q)
    for(let op of ops) {
        let f = op(q)
        if(!s.has(f)) {
            perms(s,f,ops)
        }
    }
}

function expand(p) {
    let s = new Set()
    if (p.length === 4) {
        perms(s,p,[flip2,flip2LR,rot2])
    }
    else if (p.length === 9){
        perms(s,p,[flip3,flip3LR,rot3])
    }
    else {
        throw new Error("unexpected expand length",p)
    }
    return s;
}

We can now use the expand function to help us parse our input into a lookup table.

const rules = input.map(i => i.replace(/\//g,'').split(' ')).map(p => [p[0],p[2]])
const lookup = new Map(flatMap(rules,([input,output]) => map(expand(input),i => [i,output])))

So far so good, but the main mistake I made was trying to keep the current state of the entire grid stored in strings like this. It meant that I failed to divide up even sized grids correctly if they were made up of 3x3 grids.

I ended up deciding on storing the state of the entire grid in an array of strings with one long string per line. I’d then break that big grid up into 2x2 or 3x3 sub-grids, construct the key to my lookup, look up the replacement, and then expand that back out into a new larger grid.

Here’s my function that goes through one iteration and produces a new grid:

function iterate(p, lookup) {
    let out = [];
    if (p.length % 2 == 0) {
        let y2 = 0
        // 2x2
        for(let y = 0; y < p.length; y+=2) {
            for(let x = 0; x < p.length; x+=2) {
                let key = p[y][x] + p[y][x+1] + p[y+1][x] + p[y+1][x+1]
                if (!lookup.has(key)) throw new Error("lookup not found [" + key + "]")
                let r = lookup.get(key) // will be 9 length string
                
                out[y2] = (out[y2] || "") +  r.slice(0,3)
                out[y2+1] = (out[y2+1] || "") + r.slice(3,6)
                out[y2+2] = (out[y2+2] || "") + r.slice(6,9)
            }
            y2+=3
        }
    }
    else {
        // 3x3
        let y2 = 0
        for(let y = 0; y < p.length; y+=3) {
            for(let x = 0; x < p.length; x+=3) {
                let key = p[y][x] + p[y][x+1] + p[y][x+2] + p[y+1][x] + p[y+1][x+1] + p[y+1][x+2] + p[y+2][x] + p[y+2][x+1] + p[y+2][x+2]
                if (!lookup.has(key)) throw new Error("lookup not found [" + key + "]")
                let r = lookup.get(key)// will be 16 length string
                out[y2] = (out[y2] || "") + r.slice(0,4)
                out[y2+1] = (out[y2+1] || "") + r.slice(4,8)
                out[y2+2] = (out[y2+2] || "") + r.slice(8,12)
                out[y2+3] = (out[y2+3] || "") + r.slice(12,16)
            }
            y2+=4
        }
    }
    return out;
}

Finally the answers for parts 1 and 2 were to count how many lights were on after a certain number of iterations. This is where my functional utilities library I’ve been building up came in handy. I can reuse my unfold function I made yesterday to produce a sequence of new states. Then I can skip over the desired number of repetitions and take the first element in the resulting sequence. I can use Array.reduce to count pixels that were left on at the end.

const repeats = (part === 1 ? 5 : 18);
let end = first(skip(unfold(start, s=>iterate(s,lookup)),repeats))
return end.reduce((a,s) => a + s.replace(/\./g,'').length,0)

I’m pleased I finally got my two stars today even if it took me longer than usual and I went a slightly tortuous route to get there. You can see the full code here.