Javascript algorithm - path with fewest line strokes in grid

Question

I'm working on javascript code where inputs are grid, starting position and destination position. f.e.

let grid = 

[
  [{ state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'empty' }],
  
  [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
  
  [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }],
  
  [{ state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],

  [{ state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }],

  [{ state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }],
];

let start = [1,1];

let end = [4,4];

I need to find a path between start and end with fewest line strokes. In this example it would be [1,1] [1,2] [1,3] [2,3] [3,3] [4,3] [4,4], so there are only three line strokes. I tried bfs (https://codeburst.io/how-to-find-a-path-between-two-cells-in-a-grid-using-javascript-33fd01e3c66), but it doesn't get me path with fewest number of line strokes.

Answer 1

You can use a typical BFS graph algorithm, but where nodes are considered neighbors when they are one stroke separated from each other.

Here is one way to code it:

function bfs(grid, start, end) {
    let comeFrom = new Map;
    comeFrom.set(grid[end[0], end[1]], null); // Mark start as visited
    let frontier = [start];
    while (frontier.length) {
        let nextFrontier = [];
        for (let node of frontier) {
            // For each of the 4 directions:
            for (let [dr, dc] of [[-1, 0], [0, -1], [1, 0], [0, 1]]) {
                let [r, c] = [node[0]+dr, node[1]+dc];
                // Continue in that same direction as far as possible
                while (grid[r]?.[c]?.state === "empty" && !comeFrom.has(grid[r][c])) {
                    // Register where we came from
                    comeFrom.set(grid[r][c], node);
                    if (r == end[0] && c == end[1]) { // found the target
                        // Construct the path from the comeFrom information
                        let path = [end];
                        while (r !== start[0] || c !== start[1]) {
                            [r, c] = comeFrom.get(grid[r][c]);
                            path.push([r, c]);
                        }
                        return path.reverse();
                    }
                    nextFrontier.push([r, c]);
                    r += dr;
                    c += dc;
                }
            }
        }
        // We did not find the target yet in this number of strokes. Consider one stroke more:
        frontier = nextFrontier;
    }
}

// Demo
let grid = [
    [{ state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'empty' }],
    [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
    [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }],
    [{ state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
    [{ state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }],
    [{ state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }],
];
let start = [1, 1];
let end = [4,4];

let path = bfs(grid, start, end);
console.log(JSON.stringify(path));

This solution only includes the start/end points of each stroke, omitting the intermediate positions that are crossed by strokes. They can be deducted from the output.

If you want them to be included explicitly, then consider this an exercise. You would need to add a nested loop in the while loop just before the return statement.