Return to Revisions

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;
}