## 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 the minimal number of steps to exit position `[N-1, N-1]` *if* it is possible to reach the exit from the starting position.  Otherwise, return `false` in **JavaScript**/**Python** and `-1` in **C++**/**C#**/**Java**.

Empty positions are marked `.`.  Walls are marked `W`.  Start and exit positions are guaranteed to be 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):
    lst  = maze.split('\n')
    X, Y = len(lst)-1, len(lst[0])-1
    seen = {(x,y) for x,row in enumerate(lst) for y,c in enumerate(row) if c=='W'} | {(0,0)}
    end, bag, turn = (X,Y), {(0,0)}, 0
    
    while bag and end not in bag:
        bag = { (a,b) for a,b in {(x+dx,y+dy) for x,y in bag for dx,dy in ((0,1), (0,-1), (1,0), (-1,0))}
                      if 0 <= a <= X and 0 <= b <= Y} - seen
        seen |= bag
        turn += 1
    
    return bool(bag) and turn

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


def path_finder(maze):
    maze_arr = maze_str_to_array(maze)
    n = len(maze_arr)
    start, goal = (0, 0), (n - 1, n - 1)
    return ai_star(maze_arr, start, goal)


def bfs(maze_arr, start, goal):
    """
    Implementation of breadth first search algorithm for solving maze problem
    :param maze_arr: search space
    :param start: starting node
    :param goal: goal node
    :return: True if goal can be reached
    """
    from queue import Queue
    to_be_expanded = Queue()
    to_be_expanded.put(start)
    tree = set()

    while not to_be_expanded.empty():
        node = to_be_expanded.get()
        if node == goal:
            return True
        tree.add(node)
        neighbors = get_node_neighbors(maze_arr, node)
        for neighbor in neighbors:
            if neighbor not in tree:
                to_be_expanded.put(neighbor)
    return False


def ai_star(maze_arr, start, goal):
    """
    Implementation of A* algorithm for solving maze problem. Heap is used. The value passed to
    a heap is a tuple containing priority (estimated cost) and cell coordinates.
    :param maze_arr: search space
    :param start: starting node
    :param goal: goal node
    :return: True if goal can be reached
    """
    from heapq import heappush, heappop
    to_be_expanded = []
    heappush(to_be_expanded, (manhattan_distance(start, goal), 0, 0, start))
    tree = set()

    while to_be_expanded:
        _, cost, real_cost, node = heappop(to_be_expanded)
        if node == goal:
            return real_cost
        tree.add(node)
        neighbors = get_node_neighbors(maze_arr, node)
        for neighbor in neighbors:
            if neighbor not in tree:
                heappush(to_be_expanded, (cost + manhattan_distance(neighbor, goal), cost + 0.99, real_cost + 1, neighbor))
    return False


def manhattan_distance(cell, goal):
    """
    Computes manhattan distance from some cell to the goal.
    :param cell: cell from where the distance is measured
    :param goal: goal node
    :return: absolute integer value of a manhattan distance
    """
    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])


def euclidean_distance(cell, goal):
    """
    Computes euclidean distance from some cell to the goal.
    :param cell: cell from where the distance is measured
    :param goal: goal node
    :return: absolute float value of a euclidean distance
    """
    from math import sqrt
    return sqrt((cell[0] - goal[0])**2 + (cell[1] - goal[1])**2)


def maze_str_to_array(maze):
    """
    Function to convert string representation of a maze into multidimensional list. One (1) represents empty
    field, zero (0) represents a wall (impenetrable field)
    :param maze: string representation of a maze
    :return: list representation of a maze.
    """
    return [[1 if char == '.' else 0 for char in row] for row in maze.split('\n')]


def get_node_neighbors(maze_arr, parent_node):
    """
    Computes a list of SearchNodes with all valid neighbors (except walls and cells out of board)
    :param maze_arr: a multidim list containing the maze
    :param parent_node: a node for with neighbors are calculated
    :return a list containing all possible neighbors
    """
    n = len(maze_arr)
    neighbors = []
    x_0, y_0 = parent_node
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        x_1 = x_0 + dx
        y_1 = y_0 + dy
        if 0 <= x_1 < n and 0 <= y_1 < n and maze_arr[y_1][x_1] == 1:
            neighbors.append((x_1, y_1))
    return neighbors


from math import hypot
from heapq import *

MOVES = ((0,1), (0,-1), (1,0), (-1,0))

def path_finder(maze):
    maze = list(map(list, maze.split()))
    X,Y  = end = len(maze)-1, len(maze[0])-1
    q    = [(0,0,0,(0,0))]                    # (heuristic, isEnd, n steps, x, y)
    
    while q and not q[0][1]:
        _,_,c,(x,y) = heappop(q)
        c+=1
        for dx,dy in MOVES:
            pos = a,b = x+dx, y+dy
            if 0<=a<=X and 0<=b<=Y and maze[a][b] != 'W':
                maze[a][b] = 'W'
                heappush(q, (c+X-a+Y-b, pos==end, c, pos))
    
    return q and q[0][1] and q[0][2] or 0

def path_finder(maze):
    matrix = list(map(list, maze.splitlines()))
    n = len(matrix)-1
    lst, lst2, count = [(0,0)], [], 0
    while lst:
        count += 1
        while lst:
            a, b = lst.pop()
            matrix[a][b] = "X"
            for i, j in (a+1,b),(a-1,b),(a,b+1),(a,b-1):
                if 0 <= i <= n and 0 <= j <= n and matrix[i][j] == '.':
                    if i == n and j == n:
                        return count
                    lst2.append((i,j))
        lst, lst2 = list(set(lst2)), []
    return False

def path_finder(maze):
    maze = list(map(list, maze.splitlines()))
    lenmaze_y, lenmaze_x = len(maze), len(maze[0])
    queue = [(0, 0, 0)]
    
    while queue:
        y,x,cnt = queue.pop(0)        
        if x >= 0 and y >= 0 and x < lenmaze_x and y < lenmaze_y:
            if maze[y][x] == '.':
                maze[y][x] = cnt
                directions = [(1, 0),(0, 1),(-1, 0),(0, -1)]
                for direction_y, direction_x in directions:
                    queue.append((y + direction_y, x + direction_x, cnt+1))
            if x == lenmaze_x-1 and y == lenmaze_y-1:
                return maze[y][x]
            
    return False

def path_finder(maze):
    grid = maze.splitlines()
    end = h, w = len(grid) - 1, len(grid[0]) - 1
    bag, seen = {(0, 0): 0}, set()
    while bag:
        x, y = min(bag, key=bag.get)
        rounds = bag.pop((x, y))
        seen.add((x, y))
        if (x, y) == end: return rounds
        for u, v in (-1, 0), (0, 1), (1, 0), (0, -1):
            m, n = x + u, y + v
            if (m, n) in seen or not (0 <= m <= h and 0 <= n <= w) or grid[m][n] != '.': continue
            new_rounds = rounds + 1
            if new_rounds < bag.get((m, n), float('inf')): bag[m, n] = new_rounds
    return False

def path_finder(maze): #IMPLEMENTING BFS ALGORITHM
    mtx = list(map(list, maze.splitlines())) #convert string to 2d array
    R = len(mtx[0]) #number of rows or size of te mtx
    mtx[R-1][R-1] = 'E' #define the exit as 'E'
    sr, sc = 0, 0 #starting node
    rq, cq = [], [] #empty queue for row and column
    prev = [[' ']*(R) for x in range(R)]
    
    move_count = 0 
    nodes_left_in_layer = 1
    nodes_in_next_layer = 0
    
    reached_end = False # variable used to know if exit is reached
    
    visited = [[False]*(R) for x in range(R)] # Mtx to know if node visited 
    
    dr = [-1, 1, 0, 0] # North, South, West direction vectors
    dc = [0, 0, 1, -1] # North, South, West direction vectors
    
    rq.append(sr)
    cq.append(sc)

    visited[sr][sc] = True
    while len(rq):
        r = rq.pop(0)
        c = cq.pop(0)

        if mtx[r][c] == 'E':
            reached_end = True #The end has been reached
            return move_count

        for i in range(4): #     explore_neighbours
            rr = r + dr[i]
            cc = c + dc[i]

            if rr < 0 or cc< 0: continue
            if rr >= R or cc >= R: continue
            
            if visited[rr][cc]: continue
            if mtx[rr][cc] == 'W': continue
            
            rq.append(rr)
            cq.append(cc)
            visited[rr][cc] = True
            prev[rr][cc] = [r,c] # keep track of the parent 
            nodes_in_next_layer += 1
        nodes_left_in_layer -= 1
        if nodes_left_in_layer == 0:
            nodes_left_in_layer = nodes_in_next_layer
            nodes_in_next_layer = 0
            move_count += 1
    if reached_end:
        return move_count
    else:
        return False

class Path:
    
    def __init__(self, maze, start, exit = None, pos = '.' ):
        self.maze = maze
        self.MAPd = {start:1}
        self.exit = (exit or (len(maze)-1, len(maze[0])-1))
        self.grow = None
        self.pos  = pos
        
    def run_maze(self):
        self.grow = self.len_
        for x, floor in enumerate(self.maze):
            for y, _ in enumerate(floor):
                if self.maze[x][y]==self.pos and not self.MAPd.get((x,y)): self.mover(x,y, [])
    
    def mover(self, x, y, ways = []):
        [not self.MAPd.get(e) or ways.append(self.MAPd[e]) for e in ((x-1,y),(x+1,y),(x,y-1),(x,y+1))]  
        if ways: self.MAPd[(x,y)] = min(ways) + 1

    @property
    def len_(self): return len(self.MAPd)
    
    @property
    def new_way_exist(self): return self.grow != self.len_
        
    @property
    def get_exit(self): return self.MAPd.get(self.exit, 1) - 1
        
    
def path_finder(maze):
    mazer = Path(maze.split('\n'), (0,0))
    
    while mazer.new_way_exist:
        mazer.run_maze()
        
    return mazer.get_exit

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

    return DMap.get(exit, 1) - 1 


def path_finder(maze):
    
    maze = maze.split('\n')
    inf = 2147483647 #infinity
    n = len(maze) #maze order
    distance_table = [[-1]*(n+2) for i in range(n+2)] #distance table with boundaries
    
    for i in range(n+2): #mark boundary
        distance_table[0][i] = inf
        distance_table[n+1][i] = inf
        distance_table[i][0] = inf
        distance_table[i][n+1] = inf
        
    distance_table[1][1] = 0 #start position
    
    queue = [(1,1)] #start with (1,1)
    while queue: #while queue is not empty
        i, j = queue.pop(0)
        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 distance_table[p][q] < inf: #if its not boundary or a wall
                if maze[p-1][q-1] == 'W': #if its a wall
                    distance_table[p][q] = inf
                elif distance_table[p][q] == -1 or distance_table[p][q] > distance_table[i][j]+1: #if the path is not visited or the path have longer distance
                    distance_table[p][q] = distance_table[i][j]+1
                    queue.append((p, q))
    return False if distance_table[n][n] == -1 else distance_table[n][n]