Source

udacity373_code / unit4 / u4-8_firstmaze.py

Full commit
# ----------
# 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 get_neighbors(depth, x, y):
    neighbors = []
    for direction in delta:
        row, col = x + direction[0], y + direction[1]
        if 0 <= row < len(grid)\
        and 0 <= col < len(grid[0])\
        and (grid[row][col] != 1):
            #if neighbor is out of grid,then skip this step
            neighbors.append([depth, row, col])
        
    return neighbors

def  get_next_spot(frontier):
    '''return spot with minimal depth and frontier where result is with removed'''
    spot = min(frontier)
    while spot in frontier:
        frontier.remove(spot) #remove values from frontier
    grid[spot[1]][spot[2]] = 1 #mark as visited
    return frontier, spot
    
def search():
    # ----------------------------------------
    # insert code here and make sure it returns the appropriate result
    # ----------------------------------------
    val = "fail"
    depth = 1
    frontier = get_neighbors(depth, init[0], init[1])
    while len(frontier) != 0:
        frontier, spot = get_next_spot(frontier)
        #print "frontier: ", frontier
        #print "loc: ", spot
        if goal == spot[1:]:
            #print "finish:", spot
            val = spot
            break
     
        new_nodes = get_neighbors(spot[0] + 1, spot[1], spot[2])
        if new_nodes is not None and len(new_nodes) > 0:
            frontier.extend(new_nodes)
        
    return val
    
print search()