zume interview 2nd round

karat.py

# Given a board and an end position for the player, write a function to determine if it is possible to travel from every open cell on the board to the given end position.

board1 = [
    [ 0,  0,  0, 0, -1 ],
    [ 0, -1, -1, 0,  0 ],
    [ 0,  0,  0, 0,  0 ],
    [ 0, -1,  0, 0,  0 ],
    [ 0,  0,  0, 0,  0 ],
    [ 0,  0,  0, 0,  0 ],
]

board2 = [
    [  0,  0,  0, 0, -1 ],
    [  0, -1, -1, 0,  0 ],
    [  0,  0,  0, 0,  0 ],
    [ -1, -1,  0, 0,  0 ],
    [  0, -1,  0, 0,  0 ],
    [  0, -1,  0, 0,  0 ],
]

# end = (0, 0)

# Expected output:
# board1, end -> True
# board2, end -> False

from collections import deque 
def reachable(board, starting_pos):
    pass

def bfs(board, start, end):
    queue, visited = deque(start), [] 
    while len(queue) > 0:
        cur_pos = queue.popleft()
        next_moves = findLegalMoves(board, cur_pos) 
        for pos in next_moves:
            if pos not in visited:
                queue.append(pos)
                visited.append(pos)
            if pos == end:
                return True 
    return False 


def findLegalMoves(board, starting_position):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    board_height, board_width = len(board), len(board[0])
    valid_moves = []
    for dx, dy in directions:
        new_x = starting_position[0]+dx
        new_y = starting_position[1]+dy
        if 0 <= new_x < board_height and 0 <= new_y < board_width:
            if board[new_x][new_y] != -1:
                valid_moves.append((new_x, new_y))
    return valid_moves

print(bfs(board1,(0, 0), (len(board1)-1, len(board1[0])-1)))  

# print(findLegalMoves(board, (3, 1))) 
# print(findLegalMoves(board, (5, 3)))
# print(findLegalMoves(board, (6, 0)))
# print(findLegalMoves(board, (0, 0)))
# print(findLegalMoves(board, (2, 2)))
# print(findLegalMoves(board, (6, 4)))
        
    
    

    
    
    
    
    
    
    
    
    
# def findLegalMoves(board, starting_position):
#     directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
#     board_height, board_width = len(board), len(board[0])
#     valid_moves = []
#     for dx, dy in directions:
#         new_x = starting_position[0]+dx
#         new_y = starting_position[1]+dy
#         if 0 <= new_x < board_height and 0 <= new_y < board_width:
#             if board[new_x][new_y] != -1:
#                 valid_moves.append((new_x, new_y))
#     return valid_moves

# print(findLegalMoves(board, (3, 1))) 
# print(findLegalMoves(board, (5, 3)))
# print(findLegalMoves(board, (6, 0)))
# print(findLegalMoves(board, (0, 0)))
# print(findLegalMoves(board, (2, 2)))
# print(findLegalMoves(board, (6, 4)))