Using Generator Functions in NodeJS to Solve a Puzzle

Together with a few of my colleagues I’ve been participating in Eric Wastl’s Advent of Code. My goal is to solve all the puzzles with Node 9, using just ‘vanilla’ node, no extra libraries. My solution for day 3 involved a generator function, which turned out to be a very nice fit for this puzzle.

The Puzzle

The day three puzzle is about a spiral memory grid that you have to walk in the correct order:

17  16  15  14  13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...

In the first part of the puzzle you had to find the location of a cell with a certain value. Of course I first tried to be clever and find a sequence or pattern so I could solve the puzzle without code, but I was not smart enough. Then I decided to use code to solve the puzzle.

First I tried to be clever but that didn’t work

Walking the Spiral Grid

The naive approach is to just start walking the grid in the correct order, until you find the value you are looking for. I broke the problem down. First I made a function that returns a list of coordinates when it walks from S to E:

    
x S
E
Calling it with S = ( 1, 0) results in : 
[
( 1, 0), ( 1, 1), // Walking up
( 0, 1), (-1, 1), // Walking left
(-1, 0), (-1,-1), // Walking down
( 0,-1), (1, -1) // Walking right
]

The first part of the puzzle can then be solved if you keep applying this function while keeping count.

Second Part of the Puzzle

In the second part of the puzzle, you had to assign each cell a value based on the values of its neighbours that already had values assigned, and then again find a specific cell.

This was when I wanted to decouple my ‘grid walking’ code from the code that searched for the solution. I needed a generator function.

Using a Generator Function

When you call a generator function*, you get an iterator back. Each time you call next()on this iterator, the generator function executes until the next yield statement, where it pauses. It then patiently waits for you, all scopes intact, until you decide to call next() again on the iterator. This allowed me to write a gridwalker that keeps walking ‘forever’. In pseudo code:

function* gridWalker() {
while (true) {
// Calling yield with the coordinates on every cell;
- Walk up until top of square
- Walk left until left side
- Walk down until bottom
- Walk right until right side
- Walk one more right
}

Solving part one of the puzzle is then as simple as:

const iter = gridWalker();
let value = 1;
while (value < PUZZLE_INPUT) {
iter.next();
value++;
}
const coord = iter.next().value;

To compute the second part of the puzzle, I needed a data structure to hold the entire grid (to keep track of the neighbours), but building this datastructure with the generator function was easy: you can read my entire solution on github.

Wrapping Up

This is the first time I participate in the Advent of Code challenge, but I’m already hooked. Today was also the first time I actually had a good reason to use generators and it made my code simpler and more clear.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.