Advent of Code Day 22-Sparse Grids

Today’s Advent of Code challenge required us to work on an infinite grid. Each point on the grid could contain a virus or be clean (and there were two additional states for part 2). Obviously with an infinite grid we can’t use an Array, but we can use a simple Map with the coordinates as a key. I just turned the (x,y) coordinates into a string. This allows us to maintain a sparse grid, where the map doesn’t need to contain values for every possible coordinate. Any coordinates not in the grid are assumed to be “clean”

First, here’s the code I used to parse my input into a Map of only squares with viruses (indicated with a # character) included. I used my flatMap utility function to collapse the rows into a single sequence.

let delta = Math.floor(input.length / 2)
const viruses = new Map([...flatMap(input.map((row,y) => [...row].map((ch,x) => [ch,x-delta,y-delta]).filter(([ch]) => ch === '#')))].map(([,x,y]) => [`${x},${y}`,'#']))

Now to get the value of a square we can just say viruses.get(coords.toString()) || '.'.

Now to solve the puzzle we ran through a set number of “bursts”. In each burst a “virus scanner” visits a single point on the grid. Depending on the state of that point, it can change direction and also change the state of that point. And then it moves forward one step.

My solution isn’t particularly compact. In part 1 I delete grid points from the map if they are clean, but I could equally just update the entry to the new state. In part 2, we are now cycling through states and so its easiest to always update the map with the new state

let curPos = [0,0]
let curDir = 'U'
const dirs = "URDLURDL"
let newInfections = 0;
let bursts = part === 1 ? 10000 : 10000000;
for(let burst = 0; burst < bursts; burst++) {
    const key = curPos.toString()
    if (part === 1) {
        const isInfected = viruses.get(key) === '#'
        curDir = dirs[dirs.indexOf(curDir) + (isInfected ? 1 : 3)]
        if (isInfected) {
            viruses.delete(key); 
        }
        else {
            newInfections++;
            viruses.set(key,'#')
        }
    }
    else {
        const states = ".W#F.";
        const curState = viruses.get(key) || '.'
        if (curState === '.') curDir = dirs[dirs.indexOf(curDir) + 3] // left
        else if (curState === '#') curDir = dirs[dirs.indexOf(curDir) + 1] // right
        else if (curState === 'F') curDir = dirs[dirs.indexOf(curDir) + 2] // reverse
        const newState = states[states.indexOf(curState) + 1]
        if (newState === '#') newInfections++;
        viruses.set(key, newState)
    }
    if(curDir === 'U') curPos[1]--;
    else if(curDir === 'D') curPos[1]++;
    else if(curDir === 'L') curPos[0]--;
    else curPos[0]++;
}
return newInfections;

The full code for today’s solution is available here. By the way, for anyone else looking to improve their JavaScript, I came across a nice site with short JavaScript snippets called 30 Seconds of Code. There’s a few handy tips in there that might come in useful like a curry function.