cassidoo challenge 27-08-2018

cassidoo challenge 27-08-2018

/*
Given a a 2D matrix that represents a maze (with 1s as walls and 0s as path).
Find a path from one corner to another, backtracking should be allowed.
Return an array of steps taken in order.
 */

function included(lista, elem) { 
   var res=false;
   var i=0;
   var stringElem=JSON.stringify(elem);
   while ((i<lista.length) && (!res)) {
      res = JSON.stringify(lista[i++]) === stringElem;
   }
   return (res);
}

function way(maze, partialRes, index) {
    // Precondition: maze not empty.
    // Index represents the starting position
    // It will find the way out, if there is one, from anywhere in the maze to
    // the bottom right corner.
    // This is a recursive function.
    var dims = {x: maze.length, y: maze[0].length};

    if ((index.x<0) || (index.x>=dims.x) || (index.y<0) || (index.y>=dims.y)) {
      // out of bounds
      console.log("Out of bounds");
      console.log(index);
      return({isViable: false , path:[]});
   }
   else if (maze[index.x][index.y]) { // the current position is a wall, cannot go there
      console.log("I hit a wall.");
      console.log(index);
      return({isViable: false,  path:[]});
   }
   else if ((index.x===dims.x-1) && (index.y===dims.y-1)) { // end of the maze!
      console.log("¡Fin del laberinto! Yisss!");
      console.log(index);
      return({isViable:true,path: partialRes.push(index)});
   }

   else if (included(partialRes,index)) { // already visited
      console.log("Casilla ya visitada.");
      console.log(index);
      return({isViable: false,  path:[]});
   }
   else { // recursive calls
      partialRes.push(index);
      if ((index.x-1>=0) && way(maze, partialRes, {x:index.x-1, y: index.y}).isViable) {
         console.log("Viable x-1");
         console.log(index);
         return({isViable: true, path: partialRes});
      }
      else if ((index.x+1<dims.x) && way(maze, partialRes, {x:index.x+1, y: index.y}).isViable) {
         console.log("Viable x+1");
         console.log(index);
         return({isViable: true, path: partialRes});
      }
      else if ((index.y-1>=0) && way(maze, partialRes, {x: index.x, y: index.y-1}).isViable){
         console.log("Viable y-1");
         console.log(index);
         return({isViable: true, path: partialRes});
      }
      else if ((index.y+1<dims.y) && way(maze, partialRes, {x: index.x, y: index.y+1}).isViable) {
         console.log("Viable y+1");
         console.log(index);
         return({isViable: true, path: partialRes});
      }
      else {
         console.log("No llego a nada: ni arriba, ni abajo, ni izquierda, ni derecha.");
         console.log(index);
         partialRes.pop();
         return({isViable: false, partialRes});
      }
   }
} // function

var matriz = [[0,0,1],[1,0,1],[0,0,0]]; // good maze

if (typeof matriz !== 'undefined' && matriz.length > 0){
   var resultado=way(matriz,[],{x:0,y:0});
   console.log(resultado); // good maze
}

console.log("\n====================\n");
var matriz2 = [[0,0,1],[1,0,1],[0,0,1]]; // maze with no solution
if (typeof matriz2 !== 'undefined' && matriz2.length > 0){
   var resultado=way(matriz2,[],{x:0,y:0});
   console.log(resultado); // maze with no solution
}