0 Comments Posted in:

Today’s Advent of Code puzzle was a fun challenge reminiscent of the “crossy road” or frogger. Except that we’re not crossing a road, but a “firewall”. I’ll refer to it as a road in this post to keep things simple.

Parsing the input was a simple case of using regular expressions again, and I created an ES6 Map to store the “range” for each depth.

const firewall = new Map( input.map(s => /(\d+): (\d+)/.exec(s))
    .map(([,d,r]) => ([Number(d),Number(r)])))

For part 1 we crossed the road and calculated a score for each collision. The key to knowing whether there would be a collision was working out the periodicity of each of the moving “security scanners”. A scanner moves back and forth, and so if it has a depth of 4 it will cycle through positions (0,1,2,3,2,1,0,1,2,…). So every six steps it is back where it started. We could then simply work out whether there would be a collision based on modulo arithmetic:

const maxDepth = max(firewall.keys())

let score = 0;
for(let depth = 0; depth<=maxDepth; depth++) {
    let range = firewall.get(depth) || 0
    if (range > 0) {
        let period = 2 * (range - 1)
        let caught = depth%period === 0;
        if (caught)
            score += depth*range;
    }
}
return score;

For part 2 we needed to work out how long to delay before crossing the road so we wouldn’t have a collision. It wasn’t too hard to adapt the part 1 solution to this problem although there was one gotcha. The scoring algorithm for part 1 could return 0 even if there was a collision.

I refactored my code a bit so I could have a generator function that scores a “trip” across the road. It yields the score every time there is a collision. This allows me to sum all the values for part 1, and to abort the trip across the road after the first collision for part 2. Here’s the trip function:

function* trip(firewall, delay) {
    for(let [depth,range] of firewall) {
        if (isCollision(range,delay+depth)) {
            yield depth*range;
        }
    }
}

It uses a helper isCollision method using the same periodicity calculation as before. The current time is the “depth” we are at (how far across the road) plus the time we delayed by:

const isCollision = (range,currentTime) => range > 0 && currentTime%(2 * (range - 1)) === 0;

This means I can solve part 1 with a simple sum (which is a utility function to sum an iterable I created for earlier problems this year)

const scoreTrip = (firewall, delay) => sum(trip(firewall,delay));

For part 2, I needed some additional helper methods. First, to decide if I was caught as I crossed the road, I needed to see if the iterable returned by trip contains any elements. My first attempt looked like this:

function wasCaught(firewall,delay) {
    for(let s of trip(firewall,delay)) return true;
    return false;
}

But ESLint didn’t like the fact that I don’t use the s variable, but I’m not sure the for...of syntax allows me to avoid declaring a variable. So another approach would be to access the iterator protocol directly:

const wasCaught = (firewall,delay) => !trip(firewall,delay)[Symbol.iterator]().next().done;

This works fine, but is a little bit cryptic. It would be better to create another utility method that works on a generic sequence of elements and can tell me whether there are any elements in it. I came up with this any method that supports passing in an optional predicate to check for each element:

function any(seq, predicate) {
    if (typeof(predicate) === 'undefined') 
        return !seq[Symbol.iterator]().next().done
    for(let el of seq) {
        if (predicate(el)) return true;
    }
    return false;
}

Now our wasCaught method becomes:

const wasCaught = (firewall,delay) => any(trip(firewall,delay));

With that in place we can find the first value of delay where we cross the road without a collision:

for(let delay = 0; ; delay++) {
    if (!wasCaught(firewall,delay)) return delay;
}

And that works fine, but I thought it would be nice to enhance my utilities library with a couple more methods that can make my solution a bit more functional. First, I updated my range function to make the count parameter optional. This means I can generate an unending sequence of incrementing numbers:

function* range(start, count) {
    for (let n = 0; typeof(count) === 'undefined' || n < count; n++) {
        yield start++;
    }
}

And I also created a first function, returning the first element in a sequence with an optional predicate:

function first(seq, predicate) {
    if (typeof(predicate) === 'undefined') 
        return seq[Symbol.iterator]().next().value
    for(let el of seq) {
        if (predicate(el)) return el;
    }
}

This means that the solution to part 2 becomes:

first(range(0),d => !wasCaught(firewall,d))

Slowly, my utils module is picking up all the handy sequence manipulation utilities I’m used to using with LINQ or the F# seq module. Of course I know there are already plenty of JavaScript libraries with similar functionality, but the advantage of making my own is that they are named and work the way that makes sense to me, and I’m learning along the way. The downside of making my own is that mine won’t be performance optimised and are somewhat idiosyncratic.

My plan is that once I’ve finished these challenges I’ll explore some JavaScript iterable helper libraries (e.g. lodash or ramda) and see if any would work as a replacement for my own methods. Feel free to let me know in the comments which library you recommend.

Vote on HN