Instantly share code, notes, and snippets.

# EpiphanyMachine/robotPathsBasic Created Oct 8, 2013

What would you like to do?
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 */
Owner

### EpiphanyMachine commented Oct 8, 2013

 Thanks to Peter for the solutions! https://github.com/peterkhayes