Can someone help me solve this problem? A javascript array represents a traversable path and obstacles
The route given is always sucess and does not contain an intersection. A motorcycle will always start from point 0 and must always reach the point of the last line and last column of the table and we cant go left A letter corresponds to each movement: R for: right, L for left, T for top: B for Bottom. Write down the path the car must travel to reach its goal.
I tried with this code but something is wrong
var traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','X','X','X','X','_'],
];
// Prints "0: a, 1: b, 2: c"
var current, next, last, itinerary, column ;
traverse.forEach(function callback(value, index) {
// console.log(`${index}: ${value}`);
console.log(value);
current = value[index];
next = value[index];
if (index > 0) {
last = current[index - 1];
}
addDirection(current, column, 'D', itinerary);
addDirection(next, column, 'B', itinerary);
addDirection(last, column, 'H', itinerary);
column++;
});
function addDirection(line, column, direction, itinerary)
{
line.forEach(function callback(value, index) {
if(index == column){
if (line[column] == '_') {
itinerary.push(direction);
}
}
});
}
console.log(itinerary);In this exemple the itinerary must contain R/B/B/R/R/T/T/R/R/B/B/B
Some of the many issues:
column is never initialisedcurrent gets a value from a cell, but in addDirection it is treated as a line. The line.forEach call can never work.The algorithm cannot work. I would use a search in the matrix where all three moves are inspected (except the one that goes back from where we came) and if it is possible, it is made. If it leads to a dead-end, backtracking should occur. This is basically a depth-first traversal over the _ fields in the matrix:
function getPath(matrix, row=0, col=0, vertical=0) {
if (matrix[row]?.[col] != "_") return null; // Obstacle
if (row == matrix.length - 1 && col == matrix[0].length - 1) return []; // Found target
if (vertical != -1) {
const path = getPath(matrix, row + 1, col, 1);
if (path) return ["B", ...path];
}
if (vertical != 1) {
const path = getPath(matrix, row - 1, col, -1);
if (path) return ["T", ...path];
}
const path = getPath(matrix, row, col + 1, 0);
if (path) return ["R", ...path];
return null;
}
const traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','X','X','X','X','_'],
];
const itinerary = getPath(traverse);
console.log(...itinerary);I was not sure whether the matrix could have dead-ends, like this one:
const traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','_','X','X','X','_'],
];
(Notice the extra "_" in the bottom row). The backtracking algorithm will make sure that if it goes in the wrong direction first, meeting a dead end, it will backtrack and still try the other direction. If such input is not possible, then the backtracking algorithm is a bit of overkill, but it actually does not represent much code, so it doesn't hurt to do it this way.
let traverse = [
['_', '_', 'X', '_', '_', '_'],
['X', '_', 'X', '_', 'X', '_'],
['X', '_', '_', '_', 'X', '_'],
['X', 'X', 'X', 'X', 'X', '_'],
];
let currentX = 0, currentY = 0;
let itinerary = [];
let lastDirection = '';
while(currentX != traverse[0].length - 1 && currentY != traverse.length - 1) {
if (lastDirection !== 'L' && traverse[currentY][currentX + 1] === '_') {
addDirection('R');
currentX++;
} else if (lastDirection !== 'T' && traverse[currentY + 1][currentX] === '_') {
addDirection('B');
currentY++;
} else if (lastDirection !== 'R' && traverse[currentY][currentX - 1] === '_') {
addDirection('L');
currentX--;
} else if (lastDirection !== 'B' && traverse[currentY - 1][currentX] === '_') {
addDirection('T');
currentY--;
}
}
console.log(itinerary.join('/'));
function addDirection(dir) {
itinerary.push(dir);
lastDirection = dir;
}