# ----------
# User Instructions:
# 
# Create a function compute_value which returns
# a grid of values. The value of a cell is the minimum
# number of moves required to get from the cell to the goal. 
#
# If a cell is a wall or it is impossible to reach the goal from a cell,
# assign that cell a value of 99.
# ----------

grid = [[0, 1, 0, 1, 0, 0],
        [0, 1, 0, 1, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 1, 0, 0],
        [0, 0, 0, 1, 0, 0]]
goal = [len(grid)-1, len(grid[0])-1]
cost = 1 # the cost associated with moving from a cell to an adjacent one

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

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

def compute_value(grid,goal,cost):
    # ----------------------------------------
    # insert code below
    # ----------------------------------------
    
    # make sure your function returns a grid of values as 
    # demonstrated in the previous video.
    value = [[99 for col in range(len(grid[0]))] for row in range(len(grid))]
    closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]

    # initialization
    value[goal[0]][goal[1]] = 0
    closed[goal[0]][goal[1]] = 1
    
    lst = [goal]
    for e in lst:
        x = e[0]
        y = e[1]
        step = value[x][y] + cost
        for i in range(len(delta)):
            x2 = x + delta[i][0]
            y2 = y + delta[i][1]
            if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):                    
                if closed[x2][y2] == 0 and grid[x2][y2] == 0:
                    value[x2][y2] = step
                    lst.append([x2,y2])
                    closed[x2][y2] = 1

    return value 

result = compute_value(grid, goal, cost)
for row in result:
    print(row)
@@ -36,12 +36,11 @@
  %0A# 
-Crea
+Wri
 te a
@@ -53,260 +53,422 @@
 ion 
-compute_value which returns%0A# a grid of values. The value of a cell is the minimum%0A# number of moves required to get from the cell to the goal. 
+optimum_policy that returns%0A# a grid which shows the optimum policy for robot%0A# motion. This means there should be an optimum%0A# direction associated with each navigable cell from%0A# which the goal can be reached.
 %0A#
+ 
 %0A# 
-If a
+Unnavigable
  cell
- i
 s a
+s
  w
-all or it is impossible to reach the goal from a cell,%0A# assign that cell a value of 99
+ell as cells from which %0A# the goal cannot be reached should have a string %0A# containing a single space (' '), as shown in the %0A# previous video. The goal cell should have '*'
 .%0A# 
@@ -619,16 +619,164 @@
  0, 0%5D%5D%0A
+grid = %5B%5B0, 1, 0, 0, 0, 0%5D,%0A        %5B0, 1, 1, 0, 1, 0%5D,%0A        %5B0, 0, 0, 0, 1, 0%5D,%0A        %5B0, 1, 1, 1, 1, 0%5D,%0A        %5B0, 1, 0, 1, 1, 0%5D%5D        %0A
 goal = %5B
@@ -1034,29 +1034,30 @@
 '%5D%0A%0Adef 
-compute_value
+optimum_policy
 (grid,go
@@ -1445,16 +1445,96 @@
 (grid))%5D
+%0A    policy = %5B%5B' ' for col in range(len(grid%5B0%5D))%5D for row in range(len(grid))%5D
 %0A%0A    # 
@@ -1613,16 +1613,51 @@
 1%5D%5D = 1%0A
+    policy%5Bgoal%5B0%5D%5D%5Bgoal%5B1%5D%5D = '*'%0A
     %0A   
@@ -2135,16 +2135,73 @@
 %5By2%5D = 1
+%0A                    policy%5Bx2%5D%5By2%5D = delta_name%5B(i+2)%254%5D
 %0A%0A    re
@@ -2205,22 +2205,22 @@
  return 
-value 
+policy
 %0A%0Aresult
@@ -2226,21 +2226,22 @@
 t = 
-compute_value
+optimum_policy
 (gri

write my solution to optimum_policy.py