The question is how do we make a robot travel across a square board of n dimensions from the top left corner to the bottom right corner without ever traveling across the same tile again? But that's just the starting point.
The real challenge is counting how many unique paths the robot can take that are valid solutions. Today, we'll write a function that can solve this for any board size.
Lets start off with some helper functions. The first will make a matrix that represents our board. Then, we'll attach a couple of methods to that board.
const makeBoard = (n) => {
const board = {};
for (let rowIndex = 0; rowIndex < n; rowIndex++) {
board[rowIndex] = {};
for (let colIndex = 0; colIndex < n; colIndex++) {
board[rowIndex][colIndex] = false;
}
}
First, I like to think about the most basic processes. When we traverse the board we could move up down left or right. But, at the same time, there are places that are clearly invalid, such as -1 column, or a column greater than the length of the board. We also can't travel to any place we've been for. That means we need to mark when we move to an area.
But be careful we need to unmark them when we're done or we'd have to make many clones of our matrix object which would greatly increase the space complexity. Numbers that are too high for the board size would make us reach our memory limit quickly due to the complexity of our solution.
The solution we'll be attempting here will be a brute force solution, that takes advantage of a computers biggest strength, raw computing power.
board.togglePiece = (rowIndex, colIndex) => {
board[rowIndex][colIndex] = !board[rowIndex][colIndex];
};
board.hasBeenVisited = (rowIndex, colIndex) => {
return !!board[rowIndex][colIndex];
};
return board;
};
const robotPaths = (n, board = makeBoard(n), rowIndex = 0, colIndex = 0) => {
let counter = 0;
if (rowIndex < 0 || rowIndex >= n || colIndex < 0 || colIndex >= n || board.hasBeenVisited(rowIndex, colIndex)){
return 0;
}
if (rowIndex === n-1 && colIndex === n-1){
// debugger;
return 1;
}
board.togglePiece(rowIndex, colIndex);
counter += robotPaths(n, board, rowIndex + 1, colIndex);
counter += robotPaths(n, board, rowIndex, colIndex + 1);
counter += robotPaths(n, board, rowIndex - 1, colIndex);
counter += robotPaths(n, board, rowIndex, colIndex - 1);
board.togglePiece(rowIndex, colIndex);
return counter;
}
const num = robotPaths(6);
console.log(num)
const makeBoard = (n) => {
const board = {};
for (let rowIndex = 0; rowIndex < n; rowIndex++) {
board[rowIndex] = {};
for (let colIndex = 0; colIndex < n; colIndex++) {
board[rowIndex][colIndex] = false;
}
}
board.togglePiece = (rowIndex, colIndex) => {
board[rowIndex][colIndex] = !board[rowIndex][colIndex];
};
board.hasBeenVisited = (rowIndex, colIndex) => {
return !!board[rowIndex][colIndex];
};
return board;
};
const robotPaths = (n, board = makeBoard(n), rowIndex = 0, colIndex = 0) => {
let counter = 0;
if (rowIndex < 0 || rowIndex >= n || colIndex < 0 || colIndex >= n || board.hasBeenVisited(rowIndex, colIndex)){
return 0;
}
if (rowIndex === n-1 && colIndex === n-1){
// debugger;
return 1;
}
board.togglePiece(rowIndex, colIndex);
counter += robotPaths(n, board, rowIndex + 1, colIndex);
counter += robotPaths(n, board, rowIndex, colIndex + 1);
counter += robotPaths(n, board, rowIndex - 1, colIndex);
counter += robotPaths(n, board, rowIndex, colIndex - 1);
board.togglePiece(rowIndex, colIndex);
return counter;
}
const num = robotPaths(6);
console.log(num)
With this solution, we are essiantly checking all possible paths. When a path eventually leads to a solution we return 1, and if it doesn't we return 0. this way without knowing what the eventual solution will be we still have achieved a number we can simply add. Then we take all of the current adds and add those back recursively.
Top comments (0)