## 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.

## Path Finder Series:
-       [#1: can you reach the exit?](https://www.codewars.com/kata/5765870e190b1472ec0022a2)
-       [#2: shortest path](https://www.codewars.com/kata/57658bfa28ed87ecfa00058a)
-       [#3: the Alpinist](https://www.codewars.com/kata/576986639772456f6f00030c)
-       [#4: where are you?](https://www.codewars.com/kata/5a0573c446d8435b8e00009f)
-       [#5: there's someone here](https://www.codewars.com/kata/5a05969cba2a14e541000129)

Difficulty: interview

Starter code:

def path_finder(maze):
	

Solutions:
def path_finder(maze):
    matrix = list(map(list, maze.splitlines()))
    stack, length = [[0, 0]], len(matrix)
    while len(stack):
      x, y = stack.pop()
      if matrix[x][y] == '.':
        matrix[x][y] = 'x'
        for x, y in (x, y-1), (x, y+1), (x-1, y), (x+1, y):
          if 0 <= x < length and 0 <= y < length:
            stack.append((x, y))
    return matrix[length-1][length-1] == 'x'

def path_finder(maze):
    maze = [list(level) for level in maze.split("\n")]
    N = len(maze)
    Q = [(0, 0)]
    
    while Q:
        x, y = Q.pop(0)        
        if x >= 0 and y >= 0 and x < N and y < N:
            if x == N-1 and y == N-1:
                return True
            if maze[y][x] == '.':
                maze[y][x] = 'W'
                directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                for dx, dy in directions:
                    Q.append((x + dx, y + dy))
    return False


def path_finder(maze):
    g = maze.splitlines()
    end, bag = len(g[0]) -1 + len(g) * 1j - 1j, {0}
    grid = {x + y * 1j for y,l in enumerate(g) for x,c in enumerate(l) if '.' == c}
    while bag:
        if end in bag: return True
        grid -= bag
        bag = grid & set.union(*({z + 1j ** k for k in range(4)} for z in bag))
    return False

def path_finder(maze): # DFS
    # Create a matrix of given stringMaze and add walls around it

    maze = [list("W"+string+"W") for string in maze.split('\n')]
    n = len(maze[0])
    maze = [['W']*n] + maze + [['W']*n]

    #################################################
    
    # Create Visited dict with indexes as keys

    visited = { (i,j):0 for i in range(n) for j in range(n) }
    visited[(1, 1)] = 1

    #################################################

    # Stack to store DFS info as index tuples
    stack = [(1,1)]
    while len(stack) > 0:
        idx1, idx2 = stack.pop()
        
        if idx1 == n-2 and idx2 == n-2: # (ง°ل͜°)ง
            return True
  
        if maze[idx1-1][idx2] == '.' and visited[(idx1-1, idx2)] == 0:
            visited[(idx1-1, idx2)] = 1
            stack.append((idx1-1, idx2))
        
        if maze[idx1][idx2-1] == '.' and visited[(idx1, idx2-1)] == 0:
            visited[(idx1, idx2-1)] = 1
            stack.append((idx1, idx2-1))
        
        if maze[idx1][idx2+1] == '.' and visited[(idx1, idx2+1)] == 0:
            visited[(idx1, idx2+1)] = 1
            stack.append((idx1, idx2+1))
        
        if maze[idx1+1][idx2] == '.' and visited[(idx1+1, idx2)] == 0:
            visited[(idx1+1, idx2)] = 1
            stack.append((idx1+1, idx2))
        
    return False
        
        


def path_finder(maze):
    maze = maze.split('\n')
    home = (len(maze) - 1, len(maze) - 1)
    
    M = {(r, c) for r in range(len(maze)) for c in range(len(maze)) if maze[r][c] == '.'} - {(0,0)} 
       
    P = {(0,0)}
    while P and home not in P:
        P = {(rr, cc) for r, c in P for rr, cc in {(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)}} & M
        M -= P

    return home in P

def path_finder(maze):
    maze_object = Maze(maze)
    if maze_object.maze[maze_object.exit[0]][maze_object.exit[1]] == "W":
        return False
    return maze_object.recursive_path((0,0))

class Maze:
    previous_positions = []
    exit = None
    dimension_maze = None
    maze = None

    def __init__(self,maze):
        self.maze = self.transform(maze)
        self.exit = (len(self.maze) - 1, len(self.maze[0]) - 1)
        self.dimension_maze = (self.exit[0] , self.exit[1] )
        self.previous_positions = []

    def transform(self,maze):
        return [row for row in maze.split("\n")]

    def recursive_path(self,current_position):
        if current_position == self.exit:
            return True
        if current_position[0] > self.dimension_maze[0] or \
                current_position[1] > self.dimension_maze[1] or current_position[0] < 0 or current_position[1] < 0:
            return False
        if self.maze[current_position[0]][current_position[1]] == "W":
            return False


        else:
            down = (current_position[0]+1,current_position[1])
            up = (current_position[0]-1,current_position[1])
            rigth = (current_position[0],current_position[1]+1)
            left = (current_position[0],current_position[1]-1)

            new_positions = [down,up,rigth,left]
            path_find = False

            for position in new_positions:
                if position not in self.previous_positions:
                    self.previous_positions.append(position)
                    path_find = path_find or self.recursive_path(position)


        return path_find

def path_finder(maze):
    maze = maze.split('\n')
    mazeD = { (x,y):1 for x, e in enumerate(maze) for y, _ in enumerate(e) if _ == '.' }
    
    exit, DMap, stack = (len(maze)-1, len(maze[0])-1), {}, [(0, 0)]
    
    while stack:
        x, y = stack.pop()
        if not DMap.get((x,y)):
            DMap[(x,y)] = 1
            for xc, yc in ((x, y-1), (x, y+1), (x-1, y), (x+1, y)):
                if mazeD.get((xc,yc)):
                    stack.append((xc, yc)) 
                    
    return DMap.get(exit, 0)

def path_finder(maze):
    maze = maze.split('\n')
    x_, y_ = len(maze)-1, len(maze[0])-1
    DMap = {(0,0):1}
    exit, chkr = (x_, y_), len(DMap)
    while 1: 
        for x, r in enumerate(maze):
            for y, c in enumerate(r):
                if maze[x][y]=='.' and not DMap.get((x,y)) and any(DMap.get(e) for e in ((x-1,y),(x+1,y),(x,y-1),(x,y+1))):
                    DMap[(x,y)] = 1
        if chkr == len(DMap): break
        chkr = len(DMap) 
    return DMap.get(exit, 0)

def path_finder(maze):

    maze = maze.split('\n')
    n = len(maze) #maze order
    reachable = [[None]*(n+2) for i in range(n+2)] #maze with boundaries
    
    for i in range(n+2): #boundaries are unreachable
        reachable[0][i] = False
        reachable[n+1][i] = False
        reachable[i][0] = False
        reachable[i][n+1] = False
    
    queue = [(1,1)] #start with (1,1)
    
    while queue: #while queue is not empty
        
        i, j = queue.pop(0)
        reachable[i][j] = True
        
        for x, y in (0,1),(0,-1),(-1,0),(1,0): #east-(0,1); west-(0,-1); north-(-1,0); south-(1,0)
            p, q = i+x, j+y
            if reachable[p][q] == None: #spot not visited yet
                if maze[p-1][q-1] == '.': #spot can be visited
                    reachable[p][q] = True
                    queue.append((p,q)) #if spot can be visited look for a path
                else:
                    reachable[p][q] = False #spot can't be visited i.e. wall

    return False if reachable[n][n] == None else reachable[n][n]

def path_finder(maze):
    grid = [list(v) for v in maze.split('\n')]
    n = len(grid)
    end = (n-1, n-1)
    def search(x, y):
        if (x,y) == end:
            return True
        elif grid[x][y] == 'W':
            return False
        elif grid[x][y] == 'V':
            return False

        grid[x][y] = 'V'

        if ((x < n-1 and search(x+1, y))
            or (y > 0 and search(x, y-1))
            or (x > 0 and search(x-1, y))
            or (y < n-1 and search(x, y+1))):

            return True

        return False

    return search(0,0)