1
\$\begingroup\$

Task

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:

  1. How to make recursion stop after finding solution
  2. 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.
  3. 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;
 }
}
pacmaninbw
26.2k13 gold badges47 silver badges113 bronze badges
asked Sep 7, 2021 at 11:01
\$\endgroup\$
2
  • \$\begingroup\$ if(userPosition...) { return true } else { ...} The "hard return" makes "else" unnecessary. Just let code fall through. That final return false - instead: return result because Hard coding "false" potentially masks bugs; or creates them. \$\endgroup\$ Commented Sep 7, 2021 at 17:11
  • \$\begingroup\$ thanks very much! I understand. My approach here was that recursion === base case => recursive case order, but definitely this can be changed to make code cleaner. \$\endgroup\$ Commented Sep 9, 2021 at 8:52

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.