Skip to content

@EpiphanyMachine /robotPathsBasic
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
robot paths
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
*/
/**
* 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
*/
/**
* 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
*/
@EpiphanyMachine

Thanks to Peter for the solutions!

https://github.com/peterkhayes

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.