Start to End

2022-05-23.py

question = """

Given an n x m matrix where all of the units are 0s except for an 1
for “start”, a 2 for “end”, and 3s for walls, find the shortest paths 
that you can take to get from 1 to 2, while working around 3s.

Example:

let grid = [
[1,0,0],
[0,0,2]
]

let grid2 = [
[1,3,0],
[0,0,2]
]

$ startToEnd(grid)
$ [['right', 'right', 'down'], ['right', 'down', 'right'], ['down', 'right', 'right']]

$ startToEnd(grid2)
$ [['down', 'right', 'right']]


"""

def canMoveTo(grid, there):
    i, j = there
    if i >= 0 and i < len(grid):
        if j >= 0 and j < len(grid[0]):

            if grid[i][j] != 3:
                return True
            else:
                return False

def startToEnd(grid, moves, start, end, here):
    while here != end:
        i, j = here
        if canMoveTo(grid, [i+1, j]) and canMoveTo(grid, [i, j+1]):
            moving_down = []
            for move in moves:
                moving_down.append(move)
            moving_down.append('down')
            here = [i+1, j]
            startToEnd(grid, moving_down, start, end, here)
            moving_right = []
            for move in moves:
                moving_right.append(move)
            moving_right.append('right')
            here = [i, j+1]
            startToEnd(grid, moving_right, start, end, here)
        if canMoveTo(grid, [i+1, j]):
            moves.append('down')
            here = [i+1, j]
        elif canMoveTo(grid, [i, j+1]):
            moves.append('right')
            here = [i, j+1]
    # print(moves)
    all_moves[str(moves)] = 1

grid = [
[1,0,0],
[0,0,2]
]

grid2 = [
[1,3,0],
[0,0,2]
]

# find start and end
start = []
end = []
here = []

for i in range(0, len(grid)):
    for j in range(0, len(grid[0])):
        if grid[i][j] == 1:
            start = [i, j]
        if grid[i][j] == 2:
            end = [i, j]

here = start

all_moves = {}
moves = []
startToEnd(grid, moves, start, end, here)
print(list(all_moves.keys()))

all_moves = {}
moves = []
startToEnd(grid2, moves, start, end, here)
print(list(all_moves.keys()))