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] orfalse
otherwise.Empty positions are marked
.
. Walls are markedW
. 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;
}