tests = [
{
expected: 'win',
maze: ['.'],
steps: 0
},

{
expected: 'lose',
maze: [
	'.#',
	'#.'
],
steps: 2
},

{
expected: 'win',
maze: [
	'..',
	'#.'
],
steps: 2
},

{
expected: 'win',
maze: [
	'.##',
	'..#',
  '#..'
],
steps: 4
},

{
expected: 'lose',
maze: [
	'..#',
	'#.#',
  '##.'
],
steps: 3
},

{
expected: 'win',
maze: [
	'.#...',
	'...#.',
],
steps: 7
},

{
expected: 'lose',
maze: [
	'.#...',
	'...#.',
],
steps: 6
},

{
expected: 'win',
maze: [
	'.#...',
	'...#.',
  '####.',
  '.....',
  '.#.##',
  '.....'
],
steps: 15
},

{
expected: 'lose',
maze: [
	'.#...',
	'...#.',
  '####.',
  '.....',
  '.####',
  '.....'
],
steps: 15
},

{
expected: 'lose',
maze: [
	'..',
  '#.',
  '..',
  '.#',
],
steps: 5
},

{
expected: 'win',
maze: [
	'..',
  '#.',
  '..',
  '.#',
  '..'
],
steps: 7
},

{
expected: 'win',
maze: [
	'..###########',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '##########..'
],
steps: 23
},

{
expected: 'win',
maze: [
	'..###########',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#..........#',
  '#####.######',
  '...........#',
  '##########..'
],
steps: 35
},

];

function Position(row, col) {
	this.row = row;
  this.col = col;
  this.equals = function(position) {
  	if (position.row == this.row && position.col == this.col) {
    	return true;
    } else {
    	return false;
    }
  };
  this.getRight = function() {
  	return new Position(this.row, this.col+1);
  };
  this.getDown = function() {
  	return new Position(this.row+1, this.col);
  };
  this.getLeft = function() {
  	return new Position(this.row, this.col-1);
  };
  this.getUp = function() {
  	return new Position(this.row-1, this.col);
  };
}


function isValidPosition(history, maze, position) {
	//console.log(2, position);
  // it's negative
  if (position.row < 0 || position.col < 0) {
  	return false;
  }
	// out of bounds
  if (position.row > maze.length-1 || position.col > maze[0].length-1) {
  	return false;
  }
  // it's a hedge
  const row = maze[position.row];
  if (row[position.col] === '#') {
  	return false
  }
  // we've been there before
  const beenThere = history.find(p => position.equals(p)) ? true : false;
  if (beenThere) {
  	return false;
  }

  return true;
}

function go(history, maze, position, steps) {
	//console.log(1, position);
	// can we even go here?
  if (!isValidPosition(history, maze, position)) {
  	return false;
  }
	// is the position the winner? did we take fewer steps?
  const winningPosition = new Position(maze.length-1, maze[0].length-1);
  if (position.equals(winningPosition) && history.length <= steps) {
  	return true;
  }

  const newHistory = [...history, position];

  // go in every direction!
  return (
  	go(newHistory, maze, position.getRight(), steps) ||
  	go(newHistory, maze, position.getDown(), steps) ||
    go(newHistory, maze, position.getLeft(), steps) ||
    go(newHistory, maze, position.getUp(), steps)
  );
}

function solveTheMaze(maze, steps) {
  // you can tred on . but not #
  // you always start in the upper left
  // you have to get to the bottom right in $steps or fewer steps
  // if you can, return 'win', otherwise 'lose'
  // ###############################################################

  const history = new Array();
  const currentPosition = new Position(0,0);
  //console.log(0, currentPosition);

  if (go(history, maze, currentPosition, steps)) {
  	return 'win';
  } else {
  	return 'lose';
  }

	// stub
	//return 'lose';
}

tests.forEach((test, index) => {
	result = solveTheMaze(test.maze, test.steps);
  console.log(index, result === test.expected ? 'pass' : 'fail');
});