Question

0

200

Views

Generate a path in a 2d matrix in Javascript

I am developing a ReactJs application and I have a 2d matrix. I need to generate a random path from a starting cell to an end cell given the number of rows and columns.

I found this code that calculate the number of paths possible, but I need the paths themselves.

Here is the code

function findMaxPath(currentRow, currentColumn, destRow, destCol) {
  // Base condition
  if (currentRow > destRow || currentColumn > destCol) {
    return 0;
  }
  // Successful path found
  if (currentRow === destRow && currentColumn === destCol) {
     return 1;
  }
  // Finding the number of paths that can be formed from increasing
  // the current row's Count and Current column's count one after the other.
  const pathsInRows = findMaxPath(currentRow + 1, currentColumn, destRow, destCol);
  const pathsInColums = findMaxPath(currentRow, currentColumn + 1, destRow, destCol);
  return (pathsInRows + pathsInColums);
}


function findMaxPathSrcToDes(rows, cols) {
  // Initial rows and columns to begin with.0,0 is the first row and col index we are choosing
  return findMaxPath(0, 0, rows - 1, cols - 1);
}

const num_of_paths = findMaxPathSrcToDes(3, 3);
console.log('Number of Paths', num_of_paths);

How can I get the paths?

The rules for this algorithm is:

I only need one path, it can change everytime
The starting point is always bottom-left, and the destination point is top-right
the path should go UP or LEFT or RIGHT (not U-turns)
The returned result can have this format [[0, 0], [0, 1], [2, 1]]

EDIT:

Desired type of paths:

about 4 years ago · Juan Pablo Isaza

2 answers

Answer question

0

WARNING: This answer may not be 100% accurate or complete

Please use this as a reference to build and refine further to obtain the solution that will be suited for the question.

const n = 3;

const getAllPaths = ({sr, sc, tr, tc, idx, arr, obj}) => {
//console.log('sr, sc: ', sr, sc, '\narr: ', arr);
  if (sr > tr || sc > tc) return false;
  if (sr === tr && sc === tc) {
    return ({
      obj: {
        ...obj,
        [idx + 1]: [...arr]
      },
      idx: idx + 1
    })
  };
  const rowRes = getAllPaths({
    sr: sr + 1, sc, tr, tc, idx, arr: arr.concat([[sr+1, sc]]), obj: {...obj}
  });
  //console.log('rowRes: ', rowRes);
  const colRes = getAllPaths({
    sr, sc: sc + 1, tr, tc,
    arr: arr.concat([[sr, sc+1]]),
    idx: rowRes ? rowRes.idx : idx,
    obj: rowRes ? {...rowRes.obj} : {...obj}
  });
  //console.log('colRes: ', colRes);
  return colRes ? {...colRes} : {idx, obj: {...obj}}
};

const getAllPathsSrcDest = (rows = n, cols = n) => getAllPaths(
  {sr: 0, sc: 0, tr: rows - 1, tc: cols - 1, idx: -1, arr: [[0,0]], obj: {}}
);

const allPaths = getAllPathsSrcDest()?.obj;
const renderNicely = obj => Object
  .entries(obj || {})
  .map(
    ([k,v]) => (`path num: ${+k+1} path: ${v.join(' - ')}`)
  );
console.log(renderNicely(allPaths));

const userInput = prompt('Enter matrix size 3, 4, 5, etc: ');
console.log('userInput: ', userInput);
console.log(
  renderNicely(
    getAllPathsSrcDest(userInput, userInput)?.obj
  )
);

Explanation

Use a similar approach as shown in OP's question
Instead of simply counting each way, track the exact path
The variables idx, arr and obj are used to identify and capture valid paths.

Known Issues

The list of paths is not complete. There are paths that are missing.
There is no random-ization - so, the exact same list of paths are returned
May explore option/s to memo-ize the solution and random-ize the value being returned on each call

about 4 years ago · Juan Pablo Isaza Report

Answer question

Find remote jobs

Accepted Answer · 2022-07-03T13:08:56.040Z

Since you only need one path, it would require too much memory to generate them all. Instead consider that it is known how many "moves" will be vertical, as they can only go up. If there are n rows in the matrix, then there will be n-1 up moves.

These up-moves can occur at any column, independent of the row. So the randomness lies in the selection of the column where the up-move will occur. If we have n numbers which each represent a column, then we have uniquely defined a path. It can be built from that information.

Here is an implementation, where the starting point is always at the bottom row, at a given X-coordinate, and the ending point is always at the top row, at a given X-coordinate:

function randint(range) {
    return Math.floor(Math.random() * range);
}

function randomPath(sizeX, sizeY, startX, endX) {
    let x = startX;
    let path = [];
    for (let y = sizeY - 1; y >= 0; y--) {
        let upX = y ? randint(sizeX) : endX;
        while (x != upX) {
            path.push([x, y]);
            if (x < upX) x++;
            else x--;
        }
        path.push([x, y]);
    }
    // Remove U-turns
    for (let i = path.length - 4; i >= 0; i--) {
        if (i+3 < path.length && path[i][1] === path[i+3][1] + 1 && path[i][0] === path[i+3][0]) {
            path.splice(i+1, 2); // Remove U
        }
    }
    return path;
}

function displayPath(sizeX, sizeY, path) {
    let grid = Array.from({length: sizeY}, () => Array(sizeX).fill("."));
    for (let [x, y] of path) {
        grid[y][x] = "X";
    }
    console.log(grid.map(row => row.join(" ")).join("\n"));
}

// Let's do this for a 7x7 matrix:
let sizeX = 7, sizeY = 7;
let path = randomPath(sizeX, sizeY, 2, 4); // Start at X=2 at bottom, end at X=4 at top
console.log(JSON.stringify(path));
displayPath(sizeX, sizeY, path);

When the first part of the code generates a U-turn, it will be a sequence of left-up-right or right-up-left. So for example: [3,0],[2,0],[2,1],[3,1] is a U turn. It can be seen that the first and last point are 1 y-unit apart. These points have 2 other points between them, so on the path they have a distance of 3.

The second part of the code will look for cases where points that are 3 steps apart on the path, have the same X coordinate and 1 unit of difference on the Y coordinate. If such an instance is found, the two points between them (which represent the turn) are cut out of the path.

0

200

Generate a path in a 2d matrix in Javascript

2 answers

0

0

Find remote jobs

Andres GPT