Maze path finder using Depth-First Search algorithm

Question

I'm trying to resolve this kata from CodeWars.

Kata exercise

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false otherwise.

Empty positions are marked .. Walls are marked W. Start and exit positions are empty in all test cases.

I made a simple depth first search algorithm to solve the maze and check if there exists an exit.

But I noticed that my code is too slow and so it produces Execution Timed Out error.

I'm quite sure that changing this algorithm to an heuristic one could fix this, but I don't want to do that. I want to solve this using a Deep Search Algorithm. Is possible to improve the performance of this code?

I think the problem may be in the set, which don't have a pop method, so removing an item from them is quite difficult. But using an array would even require more time to check if the item already exists there.

function pathFinder(maze) {
  // Turn maze from string to nested array
  let chart = [];
  for (let c of maze.split("\n")) {
    chart.push([...c]);
  }

  let size = chart.length;

  // Make toVisit frontier
  let toVisit = new Set();
  toVisit.add([0, 0]);

  // Check if we already are in the exit
  let end = size - 1;      
  // Size 1 maze
  if (end == 0)
    return true;
    
  while (toVisit.size > 0) {
    // Pop value from set
    let pos = toVisit.values().next().value;
    toVisit.delete(pos);

    let [x, y] = pos;
    chart[x][y] = "*"; // Mark as visited

    // Iterate over adjancets
    for ([x, y] of [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]) {
      // Check exit
      if (end == x && end == y)
        return true;
      // Check array out of boundary
      if (x < 0 || y < 0 || x >= size || y >= size)
        continue;
      // Check if wall or already visited
      let value = chart[x][y];
      if (value != "W" && value != "*")
        toVisit.add([x, y]);
    }  
  }
  return false;
}

Answer 1

Set makes for a slow stack

Your use of a Set rather than a stack (array) is slowing everything down. The hashing function needed for Set to add delete and check items is expensive compared to pushing and popping from a stack.

JS does not like managing memory, allocations are expensive. If you use a stack you don't need to shrink it, rather just keep a pointer to the current stack position. That way if it shrinks below half its size it does not need relocation. You only get reallocation of the array each time it grows over double its size and never repeated.

Creating complex object, like arrays is far slower than creating primitive types. The for loop you use needs to create a new array for each position moved to. Every time you add to the toVisit set you create a new array. This all adds up.

Even creating the array chart populating it with characters from from the maze string is overly complex and can be avoided.

Example

The example avoids creating anything by basic types in the while loop. Avoids repeated calculations. Uses stackPos to track the size of the stack rather than push and pop from the stack. For quicker indexing the map is a flat array and coordinates are handled as triplets {x, y, idx}

I would guess its about 10 times faster (depending on the maze complexity) I did not have a maze to test it on so I hope it works :)

function pathFinder(maze) {
    const stack = [], rows = maze.split("\n");
    const size = rows.length, size2 = size * 2, exit = size - 1;
    const map = new Array(size * size);
    const checkMove = (x, y, idx) => {
        if (x === exit && y === exit) { return foundExit = true }        
        if (x < 0 || x > exit || y < 0 || y > exit || rows[y][x] === "W") { return false }
        if (map[idx] === undefined) {
            map[idx] = 1;
            stack[stackPos++] = x;
            stack[stackPos++] = y;            
        }
        return false;
    }
    var x, y, idx, stackPos = 0, foundExit = false;

    checkMove(0, 0, 0)
    while (stackPos) {
        y = stack[--stackPos];
        x = stack[--stackPos] + 1;  // add one to check next position
        idx = x + y * size;
        if (checkMove(x, y, idx)) { break }
        x -= 2;
        idx -= 2;
        if (checkMove(x++, y, idx++)) { break }
        y += 1;
        idx += size;
        if (checkMove(x, y, idx)) { break }
        if (checkMove(x, y - 2, idx - size2)) { break }
    }
    return foundExit;
}