public
Created

robot paths

  • Download Gist
robotPathsBasic
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
var paths = function (n) {
var time = new Date();
var board = [];
for (var i = 0; i < n; i++) {
board.push([]);
for (var j = 0; j < n; j++) {
board[i].push(0);
}
}
board[0][0] = 1;
 
var count = 0;
var move = function(board, x, y) {
if (x === n-1 && y === n-1){
count++;
return;
}
if (board[y-1] && board[y-1][x] === 0) {
board[y-1][x] = 1
move(board, x, y-1);
board[y-1][x] = 0
}
if (board[y+1] && board[y+1][x] === 0) {
board[y+1][x] = 1
move(board, x, y+1);
board[y+1][x] = 0
}
if (board[y][x-1] === 0) {
board[y][x-1] = 1
move(board, x-1, y);
board[y][x-1] = 0
}
if (board[y][x+1] === 0) {
board[y][x+1] = 1
move(board, x+1, y);
board[y][x+1] = 0
}
};
 
move(board, 0, 0);
console.log(n+":", count, ' | solved in',new Date() - time, 'ms');
return count;
};
 
paths(5);
 
/** Result
* 5: 8512 | solved in 24 ms
*/
robotPathsOpt1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
/**
* This solution uses the symmetry of the square to divide the work
* in half. We block out the moves to the right and multiple the
* result by 2.
*/
 
 
var paths = function (n) {
var time = new Date();
var board = [];
for (var i = 0; i < n; i++) {
board.push([]);
for (var j = 0; j < n; j++) {
board[i].push(0);
}
}
board[0][0] = 1;
board[0][1] = 1;
 
var count = 0;
var move = function(board, x, y) {
if (x === n-1 && y === n-1){
count++;
return;
}
if (board[y-1] && board[y-1][x] === 0) {
board[y-1][x] = 1;
move(board, x, y-1);
board[y-1][x] = 0;
}
if (board[y+1] && board[y+1][x] === 0) {
board[y+1][x] = 1;
move(board, x, y+1);
board[y+1][x] = 0;
}
if (board[y][x-1] === 0) {
board[y][x-1] = 1;
move(board, x-1, y);
board[y][x-1] = 0;
}
if (board[y][x+1] === 0) {
board[y][x+1] = 1;
move(board, x+1, y);
board[y][x+1] = 0;
}
};
 
move(board, 1, 0);
console.log(n+":", 2*count, ' | solved in',new Date() - time, 'ms');
return 2*count;
};
 
paths(5);
 
/** Result
* 5: 8512 | solved in 18 ms
*/
robotPathsOpt2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
/**
* This solution uses the symmetry optimization and adds more.
* If you are along the top or bottom wall you never need to go right.
* If you are along the right or left side you never need to go up.
*/
 
var paths = function (n) {
var time = new Date();
var board = [];
for (var i = 0; i < n; i++) {
board.push([]);
for (var j = 0; j < n; j++) {
board[i].push(0);
}
}
board[0][0] = 1;
board[0][1] = 1;
 
var count = 0;
var move = function(board, x, y) {
if (x === n-1 && y === n-1){
count++;
return;
}
if (board[y-1] && board[y-1][x] === 0 && x !== 0 && x !== n-1) {
board[y-1][x] = 1;
move(board, x, y-1);
board[y-1][x] = 0;
}
if (board[y+1] && board[y+1][x] === 0) {
board[y+1][x] = 1;
move(board, x, y+1);
board[y+1][x] = 0;
}
if (board[y][x-1] === 0 && y !== 0 && y !== n-1) {
board[y][x-1] = 1;
move(board, x-1, y);
board[y][x-1] = 0;
}
if (board[y][x+1] === 0) {
board[y][x+1] = 1;
move(board, x+1, y);
board[y][x+1] = 0;
}
};
 
move(board, 1, 0);
console.log(n+":", 2*count, ' | solved in',new Date() - time, 'ms');
return 2*count;
};
 
paths(5);
 
/** Result
* 5: 8512 | solved in 13 ms
*/

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.