colors = [['red', 'green', 'green', 'red' , 'red'],
          ['red', 'red', 'green', 'red', 'red'],
          ['red', 'red', 'green', 'green', 'red'],
          ['red', 'red', 'red', 'red', 'red']]

measurements = ['green', 'green', 'green' ,'green', 'green']


motions = [[0,0],[0,1],[1,0],[1,0],[0,1]]

sensor_right = 0.7

p_move = 0.8

def show(p):
    for i in range(len(p)):
        print p[i]

#DO NOT USE IMPORT
#ENTER CODE BELOW HERE
#ANY CODE ABOVE WILL CAUSE
#HOMEWORK TO BE GRADED
#INCORRECT

#make same structure list as colors list
def duplicateMatrix(l):
    q = []
    for i in range(len(l)):
        q.append([])
        for j in range(len(l[i])):
            q[i].append(0)
    return q
    
# update probabilities on move
def move(m, p):
    q = duplicateMatrix(p)
    for i in range(x):
        for j in range(y):
            s = p[(i - m[0]) % x][(j - m[1]) % y] * p_move
            s += p[i][j] * (1 - p_move)
            q[i][j] = s
    return q

# update probabilities on sense
def sense(m, p):
    q = duplicateMatrix(p)
    total = 0
    for i in range(x):
        for j in range(y):
            hit = (m == colors[i][j])
            q[i][j] = p[i][j] * (hit * sensor_right + (1-hit) * (1-sensor_right))
            total += q[i][j]
    # normalize
    for i in range(x):
        for j in range(y):
            q[i][j] /= total
    
    return q
    
# initialize probabilities list
p = duplicateMatrix(colors)

# get size of list as x and y
(x,y)=(len(colors), len(colors[0]))

# total number of grids
n = x * y

# fill p list with uniform distribution
for i in range(x):
    for j in range(y):
        p[i][j] = 1./n

# execute actions
for i in range(len(motions)):
    p = move(motions[i], p)
    p = sense(measurements[i], p)
    
#Your probability array must be printed 
#with the following code.

show(p)