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

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
2
down vote

favorite












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.







share|improve this question





















  • JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
    – Blindman67
    Jan 13 at 18:59











  • @Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
    – thadeuszlay
    Jan 13 at 19:01






  • 1




    I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
    – Blindman67
    Jan 13 at 19:09










  • That's a great suggestion! Thanks @Blindman67
    – thadeuszlay
    Jan 13 at 19:10

















up vote
2
down vote

favorite












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.







share|improve this question





















  • JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
    – Blindman67
    Jan 13 at 18:59











  • @Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
    – thadeuszlay
    Jan 13 at 19:01






  • 1




    I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
    – Blindman67
    Jan 13 at 19:09










  • That's a great suggestion! Thanks @Blindman67
    – thadeuszlay
    Jan 13 at 19:10













up vote
2
down vote

favorite









up vote
2
down vote

favorite











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.







share|improve this 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.









share|improve this question












share|improve this question




share|improve this question








edited Jan 13 at 19:02
























asked Jan 13 at 17:50









thadeuszlay

435212




435212











  • JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
    – Blindman67
    Jan 13 at 18:59











  • @Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
    – thadeuszlay
    Jan 13 at 19:01






  • 1




    I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
    – Blindman67
    Jan 13 at 19:09










  • That's a great suggestion! Thanks @Blindman67
    – thadeuszlay
    Jan 13 at 19:10

















  • JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
    – Blindman67
    Jan 13 at 18:59











  • @Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
    – thadeuszlay
    Jan 13 at 19:01






  • 1




    I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
    – Blindman67
    Jan 13 at 19:09










  • That's a great suggestion! Thanks @Blindman67
    – thadeuszlay
    Jan 13 at 19:10
















JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
– Blindman67
Jan 13 at 18:59





JavaScript is so badly suited to FP you are doing your self a dis service by trying to learn FP using Javascript. Why not use a language that is designed for FP. eg Haskell haskell.org
– Blindman67
Jan 13 at 18:59













@Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
– thadeuszlay
Jan 13 at 19:01




@Blindman67 The reason I'm learning FP with JS is because JS is my main language and I want to see how far I can push JS.
– thadeuszlay
Jan 13 at 19:01




1




1




I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
– Blindman67
Jan 13 at 19:09




I have been using JS for over 20 years, FP is not how to use JS and attempting to is only going to produce slow unusable code. You should with each exercise write two versions, one using FP and one using the simplest JS you can find to solve the solution. Then you can weigh the pros and cons of both styles.
– Blindman67
Jan 13 at 19:09












That's a great suggestion! Thanks @Blindman67
– thadeuszlay
Jan 13 at 19:10





That's a great suggestion! Thanks @Blindman67
– thadeuszlay
Jan 13 at 19:10











1 Answer
1






active

oldest

votes

















up vote
2
down vote



accepted










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.






share|improve this answer























    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185049%2fadvent-of-code-2017-day-5-part-1-in-functional-programming-fp%23new-answer', 'question_page');

    );

    Post as a guest






























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    2
    down vote



    accepted










    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.






    share|improve this answer



























      up vote
      2
      down vote



      accepted










      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.






      share|improve this answer

























        up vote
        2
        down vote



        accepted







        up vote
        2
        down vote



        accepted






        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.






        share|improve this answer















        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.







        share|improve this answer















        share|improve this answer



        share|improve this answer








        edited Jan 15 at 0:06


























        answered Jan 14 at 10:33









        Blindman67

        5,4001320




        5,4001320






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185049%2fadvent-of-code-2017-day-5-part-1-in-functional-programming-fp%23new-answer', 'question_page');

            );

            Post as a guest













































































            Popular posts from this blog

            Chat program with C++ and SFML

            Function to Return a JSON Like Objects Using VBA Collections and Arrays

            Will my employers contract hold up in court?