Advent of Code Day 3–Eternal Generators

In yesterday’s post we saw our first example of an ES6 “generator function”. The generator function we created yesterday emitted a finite sequence, but today we’re generating a “spiral” of positions, and we can use a generator function to emit an infinite sequence of positions.

Spiral Generator

The puzzle wanted us to generate a “spiral” pattern of numbers, starting with 1 at (0,0), then 2 at (0,1), then 3 at (0,-1) and so on. After a bit of thought I realized the pattern for the direction that we need to move in order to work out the next position for a number. The pattern is R1 U1 L2 D2 R3 U3 L4 D4 R5 …

In other words move right one, move up one, move left two, move down two, move right three, up three and so on. So we’re cycling through directions RULD, with the distance moved in that direction going up by one for every pair of directions.

This meant I could generate a sequence of objects containing the number and x,y position that number is found at:

function* numberPlacement() {
    const dir = "RULD";
    let [x,y] = [0,0];
    let curNumber = 1;
    let dirIndex = 0;
    let dist = 1;
    let move = () => {
        switch(dir[dirIndex]) {
            case "R": x++; break;
            case "U": y--; break;
            case "L": x--; break;
            case "D": y++; break;
        }
        return [x,y];
    }
    yield { n: curNumber, pos: [x,y]} // starting position
    for(;;) {
        for(let q = 0; q < 2; q++) {
            for(let n = 0; n < dist; n++) {
                yield { n: ++curNumber, pos: move()}
            }
            dirIndex++;
            dirIndex = dirIndex%dir.length;
        }
        dist++;
    }
}

With that in place, a simple function can be created that iterates through that sequence (using an ES6 for…of loop) until we find the target number, and the Manhattan distance is easily calculated from the output coordinates:

function distanceTo(targetNumber) {
     for(let p of numberPlacement()) {
         if (p.n === targetNumber) {
             return Math.abs(p.pos[0]) + Math.abs(p.pos[1]);
         }
     }
}

Higher Order Functions and Closures

One of the nice things about the Advent of Code puzzles is that each one comes in two parts, but you don’t know what part 2 will be until you solve part 1. This means that, just as in real world development, your code will need to be extended in ways you can’t necessarily anticipate in advance.

For part 2, the spiral shape remains, but the number in each position is calculated differently. We also need a different test for when we’ve reached the target position (now we’re looking for the first number greater than our input). And finally, we’re not returning “distance” but simply the number at the target position.

The first refactoring was to change the numberPlacement generator function to take a function that can calculate the next number. Apart from that, it didn’t really need to change

function* numberPlacement(nextNumber) {
    const dir = "RULD";
    let [x,y] = [0,0];
    let dirIndex = 0;
    let dist = 1;
    let move = () => {
        switch(dir[dirIndex]) {
            case "R": x++; break;
            case "U": y--; break;
            case "L": x--; break;
            case "D": y++; break;
        }
        return [x,y];
    }
    for(;;) {
        for(let q = 0; q < 2; q++) {
            for(let n = 0; n < dist; n++) {
                let nextPos = move();
                yield { n: nextNumber(nextPos), pos: nextPos}
            }
            dirIndex++;
            dirIndex = dirIndex%dir.length;
        }
        dist++;
    }
}

And the distanceTo function becomes find, which takes a function that can decide when to stop iterating through the sequence (isTarget), and a nextNumber function to pass on to our numberPlacement generator function. And now we need return the whole object rather than just calculating the distance:

function find(isTarget, nextNumber) {
    let state = { };
    state[[0,0]] = 1
    for(let p of numberPlacement(p => nextNumber(p,state))) {
        state[p.pos] = p.n;
        if (isTarget(p.n)) {
            return p;
        }
    }
}

The other thing of note here is that we’re accumulating all previous positions into a state object. That’s because for part 2, we need to examine the values at other positions to calculate the value of the next position. The state lookup is passed as a parameter into the nextNumber function, but is is only needed for part 2.

One nice surprise is that in JavaScript you can key an object on an array, so I can use the x,y coordinates directly as a lookup from position to value.

A function that takes another function as a parameter is called a “higher order function” and by refactoring our code into higher order functions, we end up with much more extensible code. Here the isTarget and nextNumber functions mean that the find function can be used to solve both part 1 and 2 of today’s challenge.

For part 1, we can rewrite it passing a simple nextNumber function that returns an incrementing value to help us recreate our original distanceTo function. We’re using a closure around the c variable, so that each call to nextNumber will give us the next value of c.

// part 1 solution
const distanceTo = targetNumber => {
    let c = 1;
    let nextNumber = () => ++c;
    let p = find(n => n === targetNumber, nextNumber)
    return Math.abs(p.pos[0]) + Math.abs(p.pos[1]);
}
return distanceTo(startingSquare);

And part 2’s solution is now just a case of using the accumulated state to sum up the values (if present) of surrounding cells. We can do this with a call to reduce on an array of vectors describing the eight surrounding cells, and make use of a nice feature of JavaScript that we can use the expression myObject[key] || 0, to return 0 if the key isn’t present.

// part 2 solution
const nextNumber = ([x,y],state) => 
    [[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1]].reduce((acc,[a,b]) => acc + (state[[x+a,y+b]] || 0), 0);
return find(n => n > startingSquare, nextNumber).n;

My full solution for day 3 is available here.