Source

udacity373_code / unit4 / u4-17_value.py

Full commit
# ----------
# User Instructions:
# a grid of values. Value is defined as the minimum
# number of moves required to get from a cell t
# 
# Create a function compute_value() which returnso 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 init_grid(grid, init_val = 99):
    new_grid = []
    for row in grid:
        new_grid.append([init_val for i in row])
    return grid
    
def compute_value():
    value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))]

    change = True
    while change:
        change = False
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                #if we are in goal cell
                if goal[0] == x and goal[1] == y:
                    if value[x][y] > 0:
                        value[x][y] = 0
                        change = True
                        
                elif grid[x][y] == 0:
                    for a in range(len(delta)):
                        x2 = x + delta[a][0]
                        y2 = y + delta[a][1]

                        if 0 <= x2 < len(grid) and 0<= y2 < len(grid[0])\
                            and grid[x2][y2] == 0:
                            v2 = value[x2][y2] + cost_step
                            #if new value 
                            if v2 < value[x][y]:
                                change =  True
                                value[x][y] = v2
    for row in value:
        print row
                   
    return value #make sure your function returns a grid of values as demonstrated in the previous video.


compute_value()