Advent of Code Day 5-Mutable Arrays

Today’s Advent of Code puzzle required us to work through a series of instructions. Each instruction was simply the offset of the next instruction to jump to, but we also needed to modify the offsets as we went.

My solution for part 1 was fairly simple. Read the instructions into an array of integers, and loop through them, executing each one until the exit condition was met:

function solve(input, part) {
    const offsets = input.map(Number)
    return countStepsUntilExit(offsets);
}

function countStepsUntilExit(offsets) {
    let currentIndex = 0;
    let steps = 0
    while(currentIndex >= 0 && currentIndex < offsets.length) {
        let skip = offsets[currentIndex];
        offsets[currentIndex] += 1;
        currentIndex+=skip;
        steps++;
    }
    return steps;
}

For part 2, the rule to update offsets changed, but we can modify countStepsUntilExit to be a higher order function capable of solving both parts with minimal code changes:

function solve(input, part) {
    const offsets = input.map(Number)
    return countStepsUntilExit(offsets, part === 1 ? () => 1 : n => (n>=3)?-1:1);
}

function countStepsUntilExit(offsets, updateOffset) {
    let currentIndex = 0;
    let steps = 0
    while(currentIndex >= 0 && currentIndex < offsets.length) {
        let skip = offsets[currentIndex];
        offsets[currentIndex] += updateOffset(skip);
        currentIndex+=skip;
        steps++;
    }
    return steps;
}

What about immutability?

In the last two years I’ve used F# to solve the Advent of Code challenges, and F# strongly pushes you in the direction of immutable data structures. However, in JavaScript, everything is mutable by default and you have to go out of your way to make things immutable.

Today’s challenge is an example of one that is easier to solve with mutability. The code is easy to follow as we update the current index and set of instructions each time through the loop. To debug, we can easily add a breakpoint in the loop and examine the state each time through.

Now of course it is possible to tackle this functionally with immutable data, by generating a sequence of “state” objects. Each “state” object contains the list of instructions and current position. From each state, we can generate a new list of instructions and updated position. And so we could repeatedly do that until we meet the exit condition and never have to mutate anything.

The downside of an immutable approach is that it requires the creation of a brand new list of instructions just to change one value. And so using immutable data with problems like this can result in slower code due to all the memory allocations required.

So today’s puzzle is a reminder that just because “immutability” is a functional programming concept that brings a lot of benefits, it doesn’t mean its a good fit for all problems. And this puzzle is a good example of a problem that doesn’t benefit from immutability.