Advent of Code 2017 Day 5 (part 1) in Functional Programming (FP)
Clash 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.
javascript programming-challenge functional-programming ecmascript-6
add a comment |Â
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.
javascript programming-challenge functional-programming ecmascript-6
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
add a comment |Â
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.
javascript programming-challenge functional-programming ecmascript-6
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.
javascript programming-challenge functional-programming ecmascript-6
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
add a comment |Â
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
add a comment |Â
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.
add a comment |Â
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.
add a comment |Â
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.
add a comment |Â
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.
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.
edited Jan 15 at 0:06
answered Jan 14 at 10:33
Blindman67
5,4001320
5,4001320
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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