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;
  }
}
\$\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\$
    – radarbob
    Sep 7 '21 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\$ Sep 9 '21 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.