Kate constantly finds herself in some kind of a maze. Help her to find a way out!.

For a given maze and Kate's position find if there is a way out. Your function should return True or False.

Each maze is defined as a list of strings, where each char stays for a single maze "cell". ' ' (space) can be stepped on, '#' means wall and 'k' stays for Kate's starting position. Note that the maze may not always be square or even rectangular.

Kate can move left, up, right or down only.

There should be only one Kate in a maze. In any other case you have to throw an exception.


Example input
=============
```
['# ##',
 '# k#',
 '####']
```

Example output
==============
True

Example input
=============
```
['####'.
 '# k#',
 '####']
```

Example output
==============
False

Difficulty: interview

Starter code:

def has_exit(maze):
	

Solutions:
MOVES = {(0,1), (0,-1), (1,0), (-1,0)}

def has_exit(maze):
    posSet = {(x,y) for x in range(len(maze)) for y in range(len(maze[x])) if maze[x][y] == 'k'}
    if len(posSet) != 1:
        raise ValueError("There shouldn't be more than one kate")
    
    seen = set(posSet)
    while posSet:
        x,y = posSet.pop()
        if any(not (0 <= x+dx < len(maze) and 0 <= y+dy < len(maze[x+dx])) for dx,dy in MOVES):
            return True
        neighbors = {(x+dx, y+dy) for dx,dy in MOVES if 0 <= x+dx < len(maze) and 0 <= y+dy < len(maze[x+dx])
                                                        and maze[x+dx][y+dy] == ' '
                                                        and (x+dx, y+dy) not in seen}
        posSet |= neighbors
        seen   |= neighbors
    return False

def has_exit(maze):
    W = len(maze[0])                                                    # W = width of the maze
    S = W * len(maze)                                                   # S = total cells in the maze
    frontier, unseen = set(), set()                                     # Declaring sets that we'll use for BFS
    for position, content in enumerate("".join(maze)):                  # Use 1D representation for unique address of each cell
        (frontier.add, unseen.add, id)["k #".index(content)](position)  # Populate our sets: put Kate into frontier, passages into unseen
    assert len(frontier) == 1                                           # Check for one and only one Kate
    while frontier:                                                     # Do we still have any options to move further?
        position = frontier.pop()                                       # Take out one of the options
        if min(position, S - position) < W or -~position % W < 2:       # Is it on the edge?
            return True                                                 # If so, we found an exit! Hurray!
        for way in (position - W,                                       # Look up
                    position + W,                                       # Look down
                    position - 1,                                       # Look left
                    position + 1):                                      # Look right
            if way in unseen:                                           # If there is no wall, there is a way
                frontier.add (way)                                      # Let's add this to our options
                unseen.remove(way)                                      # We've seen it already
    return False                                                        # We are out of options. So saaaad :(

def has_exit(m):
    maze = [[x for x in row] for row in m]
    if not check_edge(maze):
        return False
    if not check_kate(maze):
        raise Exception("There should no be multiple Kates")
    
    kate = find_kate(maze)
    return find_way(maze, kate, kate)


def find_way(maze, position, previous_position, trace = []):
    if is_exit(maze, position):
        return True
        
    possible_ways = find_possible_ways(maze, position, previous_position)
    
    for possible_way in possible_ways:
        if possible_way not in trace:
            new_maze = move_kate(maze, possible_way, position)
            if find_way(new_maze, possible_way, position, trace + [possible_way]):
                return True
        
    return False


def find_possible_ways(maze, position, previous_position):
    r, c = position
    possible_ways = []
    for pr, pc in [(r+1, c), (r, c+1), (r-1, c), (r, c-1)]:
        if pr >= 0 and pr < len(maze) and pc >= 0 and pc < len(maze[0]):
            if maze[pr][pc] == ' ' and (pr, pc) != previous_position:
                possible_ways += [(pr, pc)]
    return possible_ways   


def find_kate(maze):
    for r in range(len(maze)):
        for c in range(len(maze[0])):
            if maze[r][c] == 'k':
                return (r, c)


def move_kate(maze, new_position, previous_position):
    nr, nc = new_position
    pr, pc = previous_position
    new_m = maze[:pr] + [maze[pr][:pc] + [' '] + maze[pr][pc+1:]] + maze[pr+1:]
    return new_m[:nr] + [new_m[nr][:nc] + ['k'] + new_m[nr][nc+1:]] + new_m[nr+1:]


def check_edge(maze):
    edges = maze[0]+maze[-1]+tr(maze)[0]+tr(maze)[-1]
    if ' ' in edges or 'k' in edges:
        return True
    return False


def check_kate(maze):
    count = 0
    for r in range(len(maze)):
        for c in range(len(maze[0])):
            if maze[r][c] == 'k':
                count += 1
    return count == 1


def is_exit(maze, position):
    width, length = len(maze)-1, len(maze[0])-1
    if width in position or length in position or 0 in position:
        return True
    return False


def tr(mtx):
    return [list(x) for x in zip(*mtx)]


def has_exit(maze):
    vector, w = list("".join(maze)), len(maze[0])                # "vector" is 1D representation of the maze; "w" is the width of a maze row
    assert vector.count("k") == 1                                # checking if there is one and only one Kate in the maze
    while "k" in vector:                                         # cycle that pushes Kate clones into previously unvisited adjacent cells
        for p, cell in enumerate(vector):                        # sweeping the maze...
            if cell == "k":                                      # ...for Kate clones
                if min(p, len(vector) - p) < w or -~p % w < 2:   # Kate clone at edge?
                    return True                                  # exit found!
                for direction in (-w, 1, w, -1):                 # otherwise look at adjacent cells
                    if  vector[p + direction] == " ":            # to see if clone can pass through them
                        vector[p + direction]  = "k"             # clone Kate where there is a passage
                vector[p] = "+"                                  # mark cell as visited
    return False                                                 # There is no exit :(


move = lambda (r, c), maze: [(rr, cc) for rr, cc in [(r,c-1),(r,c+1),(r-1,c),(r+1,c)] if maze[rr][cc] != '#']
done = lambda where, maze: any(r * c == 0 or r == len(maze) - 1 or c == len(maze[0]) - 1 for r, c in where)

def has_exit(maze):  
    where, seen = set([(r, c) for r in range(len(maze)) for c in range(len(maze[0])) if maze[r][c] == 'k']), set()
    if len(where) != 1: raise ValueError('Wrong number of Kates')
    
    while where and not done(where, maze):
        seen |= where
        where = set([p for  a in [move(p, maze) for p in where] for p in a]) - seen
    
    return done(where, maze)

#Approach: A breadth first search from the maze starting position; at each step see if
# we have solved the maze (which is defined as walking out of the boundary of the maze)
from copy import deepcopy
import queue


class MazeSymbols(object):
    START_TILE = 'k'
    WALL_TILE  = '#'
    WALKABLE_TILE = ' '
#---end class

class MazeStatus(object):
    FOUND_EXIT      = 1
    NO_EXIT_EXISTS  = 2
    CONTINUE_SEARCH = 3
    MAZE_VALID = 4
    MAZE_ERROR_NO_START = 5
    MAZE_ERROR_DUPLICATE_START = 6
#---end class


#Maze solver must deal with non-valid mazes, which constitute: No Start Position provided, 
# or multiple start positions found
class MazeSolver(object):


    def __init__(self, mazeBoard):
        self.mazeBoard = deepcopy(mazeBoard)
        self.numRows   = len( self.mazeBoard    )
        self.numCols   = len( self.mazeBoard[0] )
        validStatus, startRow, startCol = self.__validateMaze__(self.mazeBoard)

        if validStatus == MazeStatus.MAZE_VALID:
            self.validMaze = True
        else:
            self.validMaze = False

        self.startRow = startRow
        self.startCol = startCol
    #---end constructor



    def isValidMaze(self):
        return self.validMaze
    #---end function


    def attemptSolve(self):
        nR = self.numRows
        nC = self.numCols

        hasVisited = [ [ False for _ in range(nC) ] for _ in range(nR) ]

        mazeWalkResult =  self.__walkMaze__( self.mazeBoard, hasVisited, 
                                             nR, nC, self.startRow, self.startCol)
        return mazeWalkResult
    #---end function


    def __validateMaze__(self, mazeBoard):

        startPos = self.__findStartPosition__(mazeBoard)
        if not startPos:
            return MazeStatus.MAZE_ERROR_NO_START, -1, -1
        elif len(startPos)>=2:
            return MazeStatus.MAZE_ERROR_DUPLICATE_START, -1, -1
        else:
            startRow = startPos[0][0]
            startCol = startPos[0][1]
            return MazeStatus.MAZE_VALID, startRow, startCol
    #---end function

    #Find every possible start position in the maze
    def __findStartPosition__(self, mazeBoard):
        startPos = []
        for i in range(self.numRows):
            for j in range(self.numCols):
                if self.mazeBoard[i][j] == MazeSymbols.START_TILE:
                    startPos.append( [i, j])
        return startPos   #Board does not have a start position
    #---end function


    #part of the logic to find all connected shapes
    def __inImage__(self, i,j, nR, nC):
        if 0<=i and i<nR  and 0<=j and j<nC:
            return True
        else:
            return False
    #-----end function


    #part of the logic to find all connected shapes
    #  A desired cell is one that is a ship symbol and has not been visited yet
    def __isDesiredCell__(self, img, hasVisited, i, j):
        if img[i][j] == MazeSymbols.WALKABLE_TILE   and   not hasVisited[i][j]:
            return True
        else:
            return False
    #---end function


    #part of the logic to find all connected shapes
    def __markCellAsVisited__(self, hasVisited, i, j):
        hasVisited[i][j] = True
    #end function


    def __foundExit__(self, curR, curC, nR, nC):
        upStep    = curR - 1
        downStep  = curR + 1
        leftStep  = curC - 1
        rightStep = curC + 1

        if not self.__inImage__(upStep, curC, nR, nC):
            return True
        elif not self.__inImage__(downStep, curC, nR, nC):
            return True
        elif not self.__inImage__(curR, leftStep, nR, nC):
            return True
        elif not self.__inImage__(curR, rightStep, nR, nC):
            return True
        else:
            return False
    #---end function


    #Note: This function is never called at the start of the maze
    def __foundDuplicateStartPos__( self, img, curR, curC):
        if img[curR][curC] == MazeSymbols.START_TILE:
            return True
        else:
            return False
    #---end function


    #Check if we have found a duplicae start point, or we can exit the maze
    def __checkMazeStatus__(self, img, curR, curC, nR, nC):
        if self.__foundExit__(curR, curC, nR, nC):
            return MazeStatus.FOUND_EXIT
        elif self.__foundDuplicateStartPos__( img, curR, curC):
            return MazeStatus.MAZE_ERROR_DUPLICATE_START
        else:
            return MazeStatus.CONTINUE_SEARCH
    #---end function
        

    #We search only on the four cardinal directions for the Maze
    #X is up and down, y is left and right
    def __walkMaze__(self, img, hasVisited, nR, nC, iRoot, jRoot):
        #dx and dy specify the directions we are going to search dx=0 dy=1 means 
        #search north (one cell above), dx=1 dy=-1 is one to right and one down
        di = [0,  0, 1, -1]
        dj = [1, -1, 0,  0]
        numSearchDirs = len(di)     #I do not like literal values

        #x,y are lists that are going to hold the nodes conneced to the provided root (i,j) 
        iConnected, jConnected = [], []
        q = queue.Queue()

        #Begining the start of or breadth first search, starting at the provided root.
        # Note that the root is always the starting location, and therefore should not
        # be cheked for duplicate start position (but should be checked if we can exit)
        q.put((iRoot, jRoot))
        self.__markCellAsVisited__(hasVisited, iRoot, jRoot)
        if self.__foundExit__(iRoot, jRoot, nR, nC):
            return MazeStatus.FOUND_EXIT


        #Now we search for all connections along the allowed (four) directions
        while q.empty() == False:

            u, v = q.get()
            iConnected.append(u)
            jConnected.append(v)
            
            #from the current position (u,v), search in the four cardinal directions
            for s in range(numSearchDirs):
                iNew = u + di[s]
                jNew = v + dj[s]

                #if we're in the image and found a desired cell, add it to the queue
                if self.__inImage__(iNew, jNew, nR, nC)    and   \
                   self.__isDesiredCell__(img, hasVisited, iNew, jNew):
                    self.__markCellAsVisited__(hasVisited, iNew, jNew)
                    q.put((iNew, jNew))
                    currentStatus  =  self.__checkMazeStatus__(img, iNew, jNew, nR, nC)
                    if currentStatus != MazeStatus.CONTINUE_SEARCH:
                        return currentStatus

        #Should we get to this point, there does not exist a way to an exit of the maze 
        # from the starting location (path to exit: list(zip(xConnected, yConnected)))
        return MazeStatus.NO_EXIT_EXISTS
    #---end function
#---end class


#True: Maze solvable
#False: Maze has no exit
#Error Thrown: Either no start provided, or more than one start position found
def has_exit(maze):
    
    m = MazeSolver(maze)
    if not m.isValidMaze():
        raise ValueError('Maze Not Valid')
    else:
        resultSolve = m.attemptSolve()

        if resultSolve == MazeStatus.FOUND_EXIT:
            return True
        elif resultSolve == MazeStatus.NO_EXIT_EXISTS:
            return False
#---end function



def has_exit(maze):
    start = [[i, maze[i].find('k')] for i in range(len(maze)) if maze[i].find('k') != -1]
    if len(start) != 1: raise Exception("There should no be multiple Kates")
    if backtracking(maze, start[0][0], start[0][1], set()):
        return True
    return False


def backtracking(maze, y, x, explored):
    if maze[y][x] == '#':
        explored.add((y, x))
        return False
    if (y, x) in explored:
        return False
    if x in {0, len(maze[0])-1} or y in {0, len(maze)-1}:
        return True
    explored.add((y, x))
    found = backtracking(maze, y-1, x, explored) or\
            backtracking(maze, y, x+1, explored) or\
            backtracking(maze, y+1, x, explored) or\
            backtracking(maze, y, x-1, explored)
    return found

def has_exit(board):
    def make(i, j, visited=None):
        if not visited : visited = []
        if [i, j] in visited or not (0 <= i < len(board) and 0 <= j < len(board[0])) or board[i][j] == "#" : return False
        visited.append([i, j])
        if i == 0 or j == 0 or i == len(board) - 1 or j == len(board[0]) - 1 : return True
        return any([make(i + 1, j, visited),
                    make(i - 1, j, visited),
                    make(i, j + 1, visited),
                    make(i, j - 1, visited)])
    li = [[i, k] for i, j in enumerate(board) for k, l in enumerate(j) if l == 'k']
    if len(li)>1 : raise 
    return make(li[0][0],li[0][1])

def has_exit(maze):
    def rec(i, j):
        if not i in range(len(maze)): return True
        if not j in range(len(maze[i])): return True
        if maze[i][j] == '#': return False
        maze[i][j] = '#'
        return any(rec(i+k, j+l) for k in (-1, 0, 1) for l in (-1, 0, 1) if bool(k) != bool(l))

    pos = None
    for i,line in enumerate(maze):
        for j,c in enumerate(line):
            if c == 'k':
                if pos:
                    raise Exception("There should not be multiple Kates")
                else:
                    pos = (i, j)
    if not pos:
        raise Exception("There should be a Kate")
    maze = list(map(list, maze))
    return rec(*pos)

def has_exit(maze):
    N, M = len(maze)+2, len(maze[0])+2
    maze = ['b'*M] + ['b'+row+'b' for row in maze] + ['b'*M]
    q = [(i,j) for i,row in enumerate(maze) for j,c in enumerate(row) if c == 'k']
    if len(q) != 1: raise Exception('Wrong number of Kates')
    v = set(q)
    while q:
        i,j = q.pop()
        nbs = [(i+a,j+b,maze[i+a][j+b]) for a in range(-1,2) for b in range(-1,2) if bool(a) != bool(b)]
        for ni,nj,nv in nbs:
            if nv == 'b': return True
            if nv == '#' or (ni,nj) in v: continue
            q.append((ni,nj)) or v.add((ni,nj))
    return False