Posted in:

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.

Comments

Comment by Mikhail Shilkov

I want to challenge your last conclusion :-)
I totally solved this puzzle with immutable data structure (but in Scala, could be F# too). The code for both parts ran on free public web site ScalaFiddle.io with no issues whatsoever, so immutability is not a show-stopper (maybe javascript is?).
The idea is simple: I have a recursive function which gets current Maze as a parameter, together with current Index and Step. Maze is a Vector of Int's: it's indexed and immutable. Each function call creates a new Maze based on the previous one, but with current item updated and passes it to recursive call. Vector is a persistent data structure, so it doesn't allocate the whole array every time.
Of course, one can question whether immutability is needed here. Maybe not. But, by reading your "solve" function - would I be able to immediately tell that "const offsets" is actually modified in drastically unpredictable way inside innocently looking "countStepsUntilExit"? ;-)
You can find my code here: https://github.com/mikhails...

Mikhail Shilkov
Comment by Mark Heath

Yes, I was being deliberately provocative in my conclusion, so glad someone took the bait! Vector sounds like an ideal data structure for this sort of problem - don't know if F# has an equivalent, but something indexed and immutable would greatly minimise the overhead. Obviously in JavaScript land you'd need to use a functional library to get something like Vector, - my main point was that introducing whole array copies would introduce inefficiency for no real benefit. Liked your solution though - thanks for sharing!

Mark Heath
Comment by Mark Heath

Cool, I don't feel so bad for not knowing about Vector now. Hope they add one to F#

Mark Heath