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 【阅读原文】。感谢您的支持!

您可能感兴趣的

Immutable Data with Immer and React setState Immer is an incredible new library for JavaScript immutability. In previously libraries like Immutable.js it required w...
Pastate.js 响应式框架(二)多组件应用 这是pastate 专栏系列教程的第二章,欢迎关注,持续更新。 这一章,我们在上一章的 state 结构中添加多一些信息,并用多个组件来组织 pastate 应用。 分别开发 basicInfo 和 address 的...
De-throning the List Listen, I have a plan. What kind of a plan, you ask? A cunning one. As cunning as a fox? Yeah, I'd say so. As cunning as...
Learn these JavaScript fundamentals and become a b... JavaScript has primitives, objects and functions. All of them are values. All are treated as objects, even primitives...
抱歉,学会 Proxy 真的可以为所欲为 Proxy 是 JavaScript 2015 的一个新特性,下面让我们看看他实现哪些有趣的东西。 更安全的枚举类型 在 JavaScript 里,我们通常用一个对象来表示枚举值。 但这往往是不安全,我们希望枚举值: ...