maze_search.py

# https://classroom.udacity.com/courses/cs373/lessons/48646841/concepts/487263470923
# ----------
# User Instructions:
# 
# Define a function, search() that returns a list
# in the form of [optimal path length, row, col]. 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]
cost = 1

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

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

def get_candidates(current, grid, visited, cost):
    candidates = []
    for d in delta:
        x, y= d
        g, cx, cy = current
        cx += x
        cy += y
        if 0 <= cx < len(grid) and 0 <= cy < len(grid[0]) and ([cx,cy] not in visited) & (grid[cx][cy]!=1):
            candidates.append([g+cost,cx,cy])
        
    return candidates


def search(grid,init,goal,cost):
    # ----------------------------------------
    # insert code here
    # ----------------------------------------
    visited = []
    visited.append(init)
    init_g = [0, init[0],init[1]]
    candidates = get_candidates(init_g, grid, visited, cost)
    
    while True:
        cand_sorted = sorted(candidates, key=lambda x:x[0], reverse=False)
        # always pick the lowest cose
        cand_pick = cand_sorted[0]
        g, cx,cy = cand_pick
        visited.append([cx,cy])
        #print 'visited', visited
        candidates.remove(cand_pick)
        candidates += get_candidates(cand_pick, grid, visited, cost)
        
        if len(candidates) == 0:
            return 'fail'
            
        for c in candidates:
            g, cx, cy = c
            if goal == [cx, cy]:
                path = [g, cx, cy]
                return path
    
print search(grid, init, goal, cost)