__init__.py

__init__.py

# ----------
# User Instructions:
# 
# Create a function compute_value() which returns
# a grid of values. Value is defined as the minimum
# number of moves required to get from a cell to the
# goal. 
#
# If it is impossible to reach the goal from a cell
# you should assign that cell a value of 99.

# ----------

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

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1]

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

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

cost_step = 1 # the cost associated with moving from a cell to an adjacent one.

# ----------------------------------------
# insert code below
# ----------------------------------------

def weightGridCell(weight,gridCell,value,opened,closed):
    if(not gridCell):
        return value
    for i in gridCell:
        value[i[0]][i[1]] = weight
        closed.append(i)
        toDiscover = list()
        for delt in delta:
            xp = delt[0] + i[0];
            yp = delt[1] + i[1];
            if(xp >= 0 and yp >=0 and xp < len(grid) and yp < len(grid[0]) and grid[xp][yp]!=1 and [xp,yp] not in closed):
                toDiscover.append([xp,yp])
    weightGridCell(weight+cost_step, toDiscover, value, opened, closed)


def weightGridCell_iter(value):
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if(grid[i][j] != 1):
                value[i][j] = calcDist([i,j], goal)
        
def calcDist(p1,p2):
    Q = list()
    Q.append(p1)
    count = 0
    closed = list()
    while(Q):
        item = Q.pop()
        closed.append(item)
        if(item == p2):
            return count
        for delt in delta:
            xp = delt[0] + item[0]
            yp = delt[1] + item[1]
            if(xp >= 0 and yp >=0 and xp < len(grid) and yp < len(grid[0]) and grid[xp][yp]!=1 and [xp,yp] not in closed) :
                Q.append([xp,yp])
        count += cost_step
    return None
        

def compute_value():
    value = [[99 for i in range(len(grid[0]))] for j in range(len(grid))]
#     weightGridCell(0, root,value,opened,closed)
    weightGridCell_iter(value)
    return value #make sure your function returns a grid of values as demonstrated in the previous video.

for i in compute_value():
    print i