javascript – Codewars: Path Finder

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