Advent of Code Day 5-Mutable Arrays

综合技术 2017-12-05 阅读原文

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.

责编内容by:SoundCode 【阅读原文】。感谢您的支持!

您可能感兴趣的

Tuple library for JavaScript – immutable sequences... tuplerone A tuple data structure implementation in JavaScript based on ES2015 WeakMap . Tuples are finite ordered sequences of values, a...
ReasonML Fundamentals Part 1 Intro Hello and welcome back to your tutorial series on Reason ML. Yesterday we got familiar with what ReasonML is, what it has to o...
Immutable.js and Lazy Evaluation At PSPDFKit, we have a strong bias toward functional programming, which emphasizes immutability. Using immutable data structures has a lot ...
How Custom Assertion Matchers will keep mocks away I cannot write a series about avoiding mocks without mentioning Custom Assertion Matchers. If you don’t know what custom assertions are, here is p...
深入探究Immutable.js的实现机制(一) Immutable.js 由 Facebook 花费 3 年时间打造,为前端开发提供了很多便利,如今 React+Redux+Immutable.js 的组合已经成为许多项目的标配。我们知道 Immutable.js 采用了 持久化数据结构 和 结构共享 ,保证每一个对象都是不可变的,任何添加、修...