robot paths

robotPathsBasic

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

/**
 * 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

/**
 * 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
 */

Thanks to Peter for the solutions!

https://github.com/peterkhayes