def push_right (grid):
    """merges grid values right"""
    #moves values to the right
    old_grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    while util.grid_equal(grid,old_grid) == False:
        old_grid = util.copy_grid(grid)
        for row in range(3,-1,-1):
            for col in range(3,0,-1):
                if grid[row][col] == 0 and grid[row][col-1] != 0:
                    grid[row][col] = grid[row][col-1]
                    grid[row][col-1] = 0
    #merges values to the right
    for row in range (3,-1,-1):
        for col in range(3,0,-1):
            if grid[row][col] == grid[row][col-1]:
                grid[row][col] += grid[row][col-1]
                grid[row][col-1] = 0
    #moves values to the right
    for row in range(3,-1,-1):
        for col in range(3,0,-1):
            if grid[row][col] == 0 and grid[row][col-1] != 0:
                grid[row][col] = grid[row][col-1]
                grid[row][col-1] = 0    
                
    return grid

def play ():
    
    grid = []
    util.create_grid (grid)
    add_block (grid)
    add_block (grid)
    won_message = False
    while (True):
        util.print_grid (grid)
        key = input ("Enter a direction:\n")
        if (key in ['x', 'u', 'd', 'l', 'r']):
            saved_grid = util.copy_grid (grid)
            if (key == 'x'):
                return
            elif (key == 'u'):
                push.push_up (grid)
            elif (key == 'd'):
                push.push_down (grid)
            elif (key == 'r'):
                push.push_right (grid)
            elif (key == 'l'):
                push.push_left (grid)
            if util.check_lost (grid):
                print ("Game Over!")
                return
            elif util.check_won (grid) and not won_message:
                print ("Won!")
                won_message = True  
            if not util.grid_equal (saved_grid, grid):
                add_block (grid)

def push_up (grid):
    """merges grid values upwards"""
    #moves values upwards
    old_grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    while util.grid_equal(grid,old_grid) == False:
        old_grid = util.copy_grid(grid)
        for row in range(3):
            for col in range(4):
                if grid[row][col] == 0 and grid[row+1][col] != 0:
                    grid[row][col] = grid[row+1][col]
                    grid[row+1][col] = 0
    #merges like values upwards    
    for row in range (3):
        for col in range(4):
            if grid[row][col] == grid[row+1][col]:
                grid[row][col] += grid[row+1][col]
                grid[row+1][col] = 0
    #moves values upwards
    for row in range(3):
        for col in range(4):
            if grid[row][col] == 0 and grid[row+1][col] != 0:
                grid[row][col] = grid[row+1][col]
                grid[row+1][col] = 0
                
    return grid

def push_down (grid):
    """merge grid values downwards"""
 
    grid_copy=[]
    grid_copy=util.create_grid(grid_copy)
    
    while grid!=grid_copy:
        grid_copy=util.copy_grid(grid)
        
        for y in range(3,0,-1):
            for x in range(4):
                if grid[y][x]==0:
                    grid[y][x]=grid[y-1][x]
                    grid[y-1][x]=0

                    
        for x in range(4):    
            if grid[y][x]==grid[y-1][x]:
                grid[y][x]= grid[y][x]+grid[y-1][x]
                grid[y-1][x]=0
    for y in range(3,0,-1):
        for x in range(4):
            if grid[y][x]==0:
                grid[y][x]=grid[y-1][x]
                grid[y-1][x]=0 
    return grid    

def push_left (grid):
    """merge grid values left"""
    newGrid = util.copy_grid (grid)
    
    for Row in range(4):
        ListRow = []
        for Column in range(4):
    
            ListRow.append(grid[Row][Column])      
        for p in range(3):    
            for Column in range(4):
                if (Column!=3 and ListRow[Column]==0):
                    
                    for i in range(Column, 3):
                        ListRow[i]=ListRow[i+1]
                        ListRow[i+1]=0
        for Column in range(4):            
            if (Column!=3 and ListRow[Column]==ListRow[Column+1]):
                ListRow[Column]+=ListRow[Column+1]
                ListRow[Column+1]=0
                for i in range(Column+1, 3):
                    ListRow[i]=ListRow[i+1]
                    ListRow[i+1]=0                
                        
         
            for Column in range(4):
                grid[Row][Column]=ListRow[Column]