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.js v4.0.0-rc.3 发布,不可变数据集合... Immutable.js v4.0.0-rc.3 发布,不可变数据集合 达尔文 发布于2017年10月01日 收藏 0 腾讯云-1小...
Immutable npm install immutable immutable 可以基于共享部分对象来创建新的对象 :可以理解为两个对象,相同的地方引用的都是同一部分,是相同的。不同的地方是不同的。 let ...
基于 Immutable.js 实现撤销重做功能 浏览器的功能越来越强大,许多原来由其他客户端提供的功能渐渐转移到了前端,前端应用也越来越复杂。许多前端应用,尤其是一些在线编辑软件,运行时需要不断处理用户的交互,提供了撤消重做功能来保证交互的流畅性...
Lenses with Immutable.js – Brian Lonsdorf Lenses with Immutable.js Recommended listening during read: spotify:track:3bCmDqflFBHijgJfvtqev5...
使用immutable优化React 文章同步于Github Pines-Cheng/blog React在减少重复渲染方面确实是有一套独特的处理办法,那就是虚拟DOM,但显然在首次渲染的时候React绝无可能超越原生的速度,或者...