#! /usr/bin/env python

from heapq import *

'''
legend
w = wall
r = red shape / fruit
g = green shape / fruit
b = blue shape
x = cross shape
p = pink fruit
y = yellow fruit
l = lightning tile
space = empty tile
'''

b_width, b_height = [10, 12]
start_board = ("wwww      "
               "www       "
               "ww        "
               "w         "
               "          "
               "          "
               "ypppg     "
               "ygypy     "
               "yyrpg     "
               "ypppr     "
               "rgggyw    "
               "rgrrr     ")


def match(color, other):
    return True if (color == 'l' or other == 'l') else color == other


def is_clear(line):
    # Remove spaces
    line = filter(lambda x: x not in ' ', line)
    if len(line) == 0:
        return True, ' '
    if len(line) == line.count(line[0]):
        # All elements are the same
        return True, line[0]
    return False, None


def lightning_reachable(board):
    coord = None
    # Find coordinates for lightning tile
    for i, line in enumerate(board):
        if 'l' in line:
            coord = (i, line.index('l'))
    if coord is None:
        # No lightning found, not visible
        return False
    for i in range(coord[0]):
        # For lines above lightning, need a wall one tile to the left
        if coord[1] > 0 and board[i][coord[1]-1] != 'w':
            continue
        # Check if line is clear or has only one element
        line = board[i][coord[1]:]
        clear, base = is_clear(line)
        if clear:
            # All elements below need to be either space or same as base
            col = [board[k][coord[1]] for k in range(i, coord[0])]
            col = filter(lambda x: x not in " w", col)
            if len(col) == 0:
                # All spaces / wall
                return True
            if len(col) == col.count(col[0]) and (base in [col[0], ' ']):
                return True
    # For lightning's line, simply check if line is clear
    line = board[coord[0]][coord[1]+1:]
    return is_clear(line)[0]


def gravity(board):
    for i, line in enumerate(board[::-1]):
        i = b_height - 1 - i
        if i == 0:
            continue
        for j, tile in enumerate(line):
            if tile == ' ':
                for k in range(i)[::-1]:
                    if board[k][j] == ' ':
                        continue
                    elif board[k][j] in "rgbxypl":
                        board[i][j] = board[k][j]
                        board[k][j] = ' '
                        break
                    else:
                        break


def throw(color, height, board):
    new_board = [line[:] for line in board]
    valid = False

    line = new_board[height]
    for i, tile in enumerate(line[::-1]):
        if tile == ' ':
            # Empty tile, continue movement
            continue
        elif tile in "w":
            # Collide with wall or pipe, fall
            return fall(color, height, b_width - i, new_board, valid)
        elif match(color, tile):
            # Mark as a valid move
            valid = True
            # Lightning tile changes color to whatever it touched
            if (color == 'l' and tile != 'l'):
                color = tile
            # Erase matched tile
            line[b_width - 1 - i] = ' '
            continue
        elif valid:
            # Was a valid move, no more matches
            # Swap thrown color for current touching color and return
            ret_color = tile
            line[b_width - 1 - i] = color
            # Apply gravity to board
            gravity(new_board)
            return ret_color, new_board
        else:
            # Invalid move
            return None, None
    # Reached left boundary, fall from there
    return fall(color, height, 0, new_board, valid)


def fall(color, height, column, board, valid):
    line = [row[column] for row in board]
    for i, tile in enumerate(line):
        if i < height or tile in ' w':
            # Skip to starting height, empty tile, continue movement
            continue
        elif match(color, tile):
            # Mark as a valid move
            valid = True
            # Lightning tile changes color to whatever it touched
            # Passing through lightning tile does not change color
            if (color == 'l' and tile != 'l'):
                color = tile
            # Erase matched tile
            board[i][column] = ' '
            continue
        elif valid:
            # Was a valid move, no more matches
            # Swap thrown color for current touching color and return
            ret_color = tile
            board[i][column] = color
            # Apply gravity to board
            gravity(board)
            return ret_color, board
        else:
            # Invalid move
            return None, None
    # Reached bottom of board, check if valid move
    if valid:
        # Apply gravity to board
        gravity(board)
        # Return color is the same as thrown color
        return color, board
    else:
        return None, None


def grade(board):
    # We want to minimize number of tiles in play, so we use that as score
    score = 0
    for line in board:
        for tile in line:
            if tile in "rgbxypl":
                score += 1
    return score

if __name__ == '__main__':

    board = [list(start_board)[(i*10):((i+1)*10)] for i in range(12)]
    lightning = 'l' in start_board
    light = 999 if 'l' in start_board else 0

    score = grade(board)
    states = []
    iterations = 0
    best = (light, score, 0, [], 'l', board)
    heappush(states, (light, score, 0, [], 'l', board))

    while states and iterations < 1000000:
        iterations += 1
        light, score, count, moves, tile, board = heappop(states)
        if lightning:
            # If lightning is in field, check if it's accessible
            visible = lightning_reachable(board)
        if score < best[1] or (score == best[1] and light < best[0]):
            # Current state is better than previou8s best state, store it
            best = (light, score, count, moves, tile, board)
            if lightning:
                print score, count, moves, light
            else:
                print score, count, moves

        for i in range(b_height):
            # For each possible move, check result
            nt, new_board = throw(tile, i, board)
            if nt is None:
                # Invalid move
                continue
            score = grade(new_board)
            if lightning:
                if visible:
                    # If lighting was visible before move, check if it still is
                    still_visible = False
                    for line in new_board:
                        if 'l' in line:
                            still_visible = True
                            break
                    if still_visible:
                        lrm = 999
                    else:
                        lrm = count + 1
                else:
                    # If there was lightning, keep previous light removal
                    lrm = light
            else:
                lrm = 0
            # Push new valid state
            heappush(states, (lrm, score, count+1, moves+[i], nt, new_board))

    print "=================="
    print "Iterations:", iterations
    print len(states), "states left in queue"
    light, score, count, moves, tile, board = best
    print score, count, moves, tile, light