maze.py

'''
Created on Jun 3, 2017

@author: john_jimenez
'''
# ----------
# 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, 1],
        [0, 0]]
init = [0, 0]
max_x = len(grid) - 1
max_y = len(grid[0]) - 1
goal = [max_x, max_y]
cost = 1

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

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

def search(grid,init,goal,cost):
    
    def path(node, opens, checkeds):
        
        def is_valid(xy):
            x, y = xy
            def in_grid(): return x >= 0 and y >= 0 and x <= max_x and y <= max_y
            def obstacle(): return grid[x][y]
            return in_grid() and not obstacle() and xy not in checkeds
            
        def expand(delta):
            expansion = add(xy, delta)
            return [[g_val * cost + 1] + expansion] if is_valid(expansion) else []
            
        xy = node[1:3]
        g_val = node[0]
        if xy == goal: return node
        else:
            new_opens = reduce(lambda acc, delta: acc + expand(delta), deltas, opens)
            if len(new_opens) == 0: return 'fail'
            else:
                new_checkeds = checkeds + [xy]
                sorted_opens = sorted(new_opens)
                return path(sorted_opens[0], sorted_opens[1:len(sorted_opens)], new_checkeds)
            
    return path([0] + init, [], [])

def add((x1, y1), (x2, y2)): return [x1 + x2, y1 + y2]

print search(grid,init,goal,cost)