\$\begingroup\$
\$\endgroup\$
2
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 know this exist already, but my solution is a bit different, so...
It is very cool and i see that people struggle a lot because of performance (tests are big). I had 3 problems here:
- How to make recursion stop after finding solution
- Before adding "visited" array, i modificated maze array on each turn: maze = maze.slice(0, pos) + 'p' + maze.slice(pos + 1). Adding space complexity ("visited" array) SOLVED A LOT.
- Converting [x, y] <=> userPosition, as initially maze is by pure string. I found out that it's not even needed to do this convert (division, modulus). Does this improvement means something?
Solution:
"use strict";
function pathFinder(maze) {
const size = maze.split("\n")[0].length;
const visited = new Array((size + 1) * size);
return solveMaze(maze, visited, size, 0);
}
function solveMaze(maze, visited, size, userPosition){
if (userPosition === maze.length - 1) {
return true;
} else {
let result;
visited[userPosition] = true;
const allSteps = [userPosition - (size + 1), //up
userPosition + 1, //right
userPosition + (size + 1), //down
userPosition - 1]; //left
const possibleSteps = allSteps.filter(pos => pos > 0 &&
pos < maze.length &&
maze[pos] !== 'W' &&
!visited[pos] &&
maze[pos] !== '\n');
for (const step of possibleSteps) {
result = solveMaze(maze, visited, size, step);
if (result) return result;
}
return false;
}
}
default
if(userPosition...) { return true } else { ...}
The "hard return" makes "else" unnecessary. Just let code fall through. That finalreturn false
- instead:return result
because Hard coding "false" potentially masks bugs; or creates them. \$\endgroup\$