Quiz 4-8

gistfile1.py

# ----------
# User Instructions:
# 
# Define a function, search() that takes no input
# and returns a list
# in the form of [optimal path length, x, y]. For
# the grid shown below, your function should output
# [11, 4, 5].
#
# If there is no valid path from the start point
# to the goal, your function should return the string
# 'fail'
# ----------

# Grid format:
#   0 = Navigable space
#   1 = Occupied space

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

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1] # Make sure that the goal definition stays in the function.

delta = [[-1, 0 ], # go up
        [ 0, -1], # go left
        [ 1, 0 ], # go down
        [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>']

cost = 1

def isNavigable(a):
    if grid[a[0]][a[1]] == 0:
        return True
    else:
        return False
        
def legal(a):
    rows = len(grid)
    columns = len(grid[0])
    
    if (a[0] >= 0 and a[0] < rows) and (a[1] >= 0 and a[1] < columns):
        return True
    else:
        return False

def exists(matrice, spot):
    row = spot[0]
    col = spot[1]
    if matrice[row][col] == 1:
        return True
    else:
        return False
    
def search():
    available = []

    checked = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
    

    available.append([0,init[0],init[1]])

    while (available != []):

        # Find smallest movement
        least = 0
        for i in range(len(available)):
            if available[i][0] < available[least][0]:
                least = i 
        
        current = available.pop(least)
        checked[current[1]][current[2]] = 1

        if current[1]== goal[0] and current[2] == goal [1]:
            return current
        
        # Check surrounding locations
        for i in range(len(delta)):

            possible = [current[0]+1,current[1]+delta[i][0],current[2]+delta[i][1]]

            spot = [possible[1],possible[2]]

            if legal(spot) is True:
                if exists(checked,spot) is False:
                    if isNavigable(spot) is True:
                        checked[spot[0]][spot[1]] = 1
                        available.append(possible)
        
    return 'fail'

print search()