Advent of Code 2017 Day 5 (part 1) in Functional Programming (FP)

Question

I wanted to practice functional programming (FP) without using any library but using vanilla JS only. So I took a problem from Advent of Code (the 1st part of Day 5):

An urgent interrupt arrives from the CPU: it's trapped in a maze of jump instructions, and it would like assistance from any programs with spare cycles to help find the exit.

The message includes a list of the offsets for each jump. Jumps are relative: -1 moves to the previous instruction, and 2 skips the next one. Start at the first instruction in the list. The goal is to follow the jumps until one leads outside the list.

In addition, these instructions are a little strange; after each jump, the offset of that instruction increases by 1. So, if you come across an offset of 3, you would move three instructions forward, but change it to a 4 for the next time it is encountered.

For example, consider the following list of jump offsets:

0
3
0
1
-3

Positive jumps ("forward") move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found:

• (0) 3 0 1 -3 - before we have taken any steps.
• (1) 3 0 1 -3 - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1.
• 2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
• 2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind.
• 2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2.
• 2 5 0 1 -2 - jump 4 steps forward, escaping the maze.

In this example, the exit is reached in 5 steps.

How many steps does it take to reach the exit? Input : https://adventofcode.com/2017/day/5/input

My solution in FP:

  const parsedInput = input => input
    .split('\n')
    .map(c => parseInt(c));

  const jumper = input => {
    const currentMaze = input.maze;
    const currentPosition = input.position;
    const currentStepNumber = input.stepNumber;
    if (currentPosition >= currentMaze.length) {
      return currentStepNumber;
    }
    const newOffset = currentMaze[currentPosition] + 1;
    const maze = currentMaze
     .slice(0, currentPosition)
     .concat(newOffset)
     .concat(currentMaze.slice(currentPosition + 1));
    const position = currentPosition + currentMaze[currentPosition];
    const stepNumber = currentStepNumber + 1;
    return jumper({
      maze, position, stepNumber
    });
  };

  const startMaze = parsedInput(INPUT);
  const solution = jumper({
    maze: startMaze,
    position: 0,
    stepNumber: 0
  });

  console.log("solution ", solution);

Running this code with node9 in normal mode will create a RangeError: Maximum call stack size exceeded. I had to "cheat" by running this code in node 6: node --harmony 05_1.js (node 6 supports Tail Cail Optimization (TCO) when the flag --harmony is turned on). I also tried to cache the maze but this didn't help either. I got the feeling that big size Input is the limit for FP.

Answer 1

Simple and pure

Regarding the comments the following is an example of a simple JS solution to the problem. Turns out that it is also a pure function.

// list is a copy of input, thus passing strings is inherently pure
function traverseJumpList(list) {
    list = list.split("\n");  // no need to parse the numbers as
                              // the ++ operator will coerce a string to
                              // a number for you..
    var jumps = 0, index = 0;
    // Assuming that an exit jump is also jumping to negative index
    while (index >= 0 && index < list.length) {
        jumps += 1;
        index += list[index]++;
    }
    return jumps;
}
const solution = traverseJumpList(INPUT);

Recursion

This particular problem can not be solved via recursion without proper tail calls because you can not know the max steps in advance.

Memory

Even with tail calls on you are still fighting JS because you are not being memory aware. In the function jumper you create a new copy of the maze and then make the next jump via recursion.

This means for each jump you create a complete copy of the maze and hold it in memory until the end. So if you have a maze with 1024 items and it takes 2048 jumps to complete you will have 2097152 unique items. This is very wasteful by any standard.

You should release the previous maze before you make the next jump

  const jumper = input => {
    var currentMaze = input.maze;
    const currentPosition = input.position;
    const currentStepNumber = input.stepNumber;
    if (currentPosition >= input.maze.length) {
       return currentStepNumber;  
    }
    const newOffset = input.maze[currentPosition] + 1;
    const maze = input.maze
     .slice(0, currentPosition)
     .concat(newOffset)
     .concat(input.maze.slice(currentPosition + 1));
    const position = currentPosition + input.maze[currentPosition];
    const stepNumber = currentStepNumber + 1;

    // clean up memory
    input = undefined;

    return jumper({maze, position, stepNumber});

  };

Indirect recursion.

An alternative to direct recursion is indirect recursion. This is done by calling the recuse function using a time event. The code is similar but you will need to provide the result as a function call.

This method gives unlimited recursion and frees up all incidental memory by releasing each recursive call's context from the heap before doing the next iteration. Also exiting to context idle makes GC more efficient.

Using your jumper function as an example.

  const jumper = input => {
    const currentMaze = input.maze;
    const currentPosition = input.position;
    const currentStepNumber = input.stepNumber;
    if (currentPosition >= currentMaze.length) {
      // return currentStepNumber;  
      showAnswer(currentStepNumber);   // The result must be called in
      return;
    }
    const newOffset = currentMaze[currentPosition] + 1;
    const maze = currentMaze
     .slice(0, currentPosition)
     .concat(newOffset)
     .concat(currentMaze.slice(currentPosition + 1));
    const position = currentPosition + currentMaze[currentPosition];
    const stepNumber = currentStepNumber + 1;
    // call next step via timeout. This will not execute until after
    // this function has exited.
    setTimeout(() => jumper({maze, position, stepNumber}),0);

    // this function now exits before the next jump releasing the
    // original input object
  };

And the starting and answer functions

  jumper({maze: startMaze, position: 0, stepNumber: 0});
  const showAnswer = (result) => console.log(result);

Or you could have jumper return a promise on the first pass which resolves with the answer. I am not too sure if this fits the FP paradigm.