G

'''
Created on Oct 4, 2009
'''
import sys
from copy import deepcopy
from threading import Timer

hard_bubble_board = (
           'pbgpbpyggrbpbgr',
           'bgyrbpprgyrgpbb',
           'bgyprypbpbbbrpb',
           'bpprpbpbgrrrgrr',
           'ppbrbpygpryryrb',
           'rgrgpbyyypggrbr',
           'gygrprrybbrrgrr',
           'rgpbpggrbypyryr',
           )

simple_bubble_board = (
                'rgrgpbyyypggrbr',
                'gygrprrybbrrgrr',
                'rgpbpggrbypyryr',
                )

X_VALUE = 5
SPACE_VALUE = 6
NUM_COLORS = 5

SOLVER_COUNT = 0
TOTAL_SOLVER_COUNT = 0
SOLVER_MEMOIZED = 0
USE_MEMOIZED = True
USE_PSYCO = sys.platform == 'win32'
STILL_SOLVING = True
MEMOIZATION = {'': {'t': 0}}

def PrintStats():
    global SOLVER_COUNT, TOTAL_SOLVER_COUNT, STILL_SOLVING
    TOTAL_SOLVER_COUNT += SOLVER_COUNT
    print "TOTAL_SOLVER_COUNT:", TOTAL_SOLVER_COUNT, "SOLVER_COUNT PER 10s:", SOLVER_COUNT, "SOLVER_COUNT PER 1s:", SOLVER_COUNT / 10, "MEMOIZATION SIZE:", len(MEMOIZATION), "MEMOIZATION HIT:", SOLVER_MEMOIZED
    SOLVER_COUNT = 0
    if STILL_SOLVING:
        Timer(10.0, PrintStats).start()

conversion_c2i = {'p':0, 'b':1, 'g':2, 'y':3, 'r':4, 'x':X_VALUE, ' ':SPACE_VALUE}
conversion_i2c = ('p', 'b', 'g', 'y', 'r', 'x', ' ')

i2c_converter = lambda x: conversion_i2c[x]
identity_converter = lambda x: x

# convert to a faster underlying representation of the board
bubble_board = [[conversion_c2i[c] for c in row] for row in simple_bubble_board]

def compute_ball_adjacency(board, color, adjacency_table, adjacency_list, row_idx, col_idx):
    # Check the four bubbles adjacent for the same color value
    #          (x+0,y-1)
    # (x+1,y+0)(x+0,y+0)(x-1, y+0)
    #          (x+0,y+1)

    # Number of bubbles adjacent
    num_bubles_adjacent = 1

    # Check (x+1,y+0) .. first check whether we are in range

    r = row_idx
    c = col_idx + 1
    if c < len(board[0]):
        # if (0 or 1) that means we already figured out the ball count
        # Check whether we scored this one already
        if adjacency_table[r][c] == -1:
            # Make sure it is the same color
            if board[r][c] == color:
                # Same color update our score card
                adjacency_table[r][c] = 1
                adjacency_list.append((r, c))
                # go down the recursive path
                num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
            else:
                # We are not the same color so mark it as a 0
                adjacency_table[r][c] = 0

    # Check (x+0,y-1) .. first check whether we are in range
    r = row_idx - 1
    c = col_idx
    if r >= 0:
        # if (0 or 1) that means we already figured out the ball count
        # Check whether we scored this one already
        if adjacency_table[r][c] == -1:
            # Make sure it is the same color
            if board[r][c] == color:
                # Same color update our score card
                adjacency_table[r][c] = 1
                adjacency_list.append((r, c))
                # go down the recursive path
                num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
            else:
                # We are not the same color so mark it as a 0
                adjacency_table[r][c] = 0

    # Check (x+0,y-1) .. first check whether we are in range
    r = row_idx
    c = col_idx - 1
    if c >= 0:
        # if (0 or 1) that means we already figured out the ball count
        # Check whether we scored this one already
        if adjacency_table[r][c] == -1:
            # Make sure it is the same color
            if board[r][c] == color:
                # Same color
                # update our score card
                adjacency_table[r][c] = 1
                adjacency_list.append((r, c))
                # go down the recursive path
                num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
            else:
                # We are not the same color so mark it as a 0
                adjacency_table[r][c] = 0

    # Check (x+0,y+1) .. first check whether we are in range
    r = row_idx + 1
    c = col_idx
    if r < len(board):
        # if (0 or 1) that means we already figured out the ball count
        # Check whether we scored this one already
        if adjacency_table[r][c] == -1:
            # Make sure it is the same color
            if board[r][c] == color:
                # Same color
                # update our score card
                adjacency_table[r][c] = 1
                adjacency_list.append((r, c))
                # go down the recursive path
                num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
            else:
                # We are not the same color so mark it as a 0
                adjacency_table[r][c] = 0
    return num_bubles_adjacent

def print_board(board, msg, converter=i2c_converter):
    print msg
    print ' |' + ''.join(['%3d ' % i for i in xrange(len(board[0]))])
    print ' +' + ('----' * (len(board[0])))
    for row in xrange(len(board)):
        print str(row) + '|',
        for col in xrange(len(board[0])):
             sys.stdout.write('%3s ' % converter(board[row][col]))
        print

def mark_bubble_group(board, adj_count_list, row_idx, col_idx,
                      X_VALUE=X_VALUE):
    # Go through the adj_count_list and exchange all the bubbles with a count > 0 with Xs
    for row, col in adj_count_list:
        assert board[row][col] != X_VALUE
        # convert to an x
        board[row][col] = X_VALUE

def pick_bubble_group(bubbles_board, adj_count_list, row_idx, col_idx,
                      X_VALUE=X_VALUE, SPACE_VALUE=SPACE_VALUE, mark_bubble_group=mark_bubble_group):

    # Make a copy of our bubbles, we are going to return this reduced board
    board = [[c for c in r] for r in bubbles_board]
    #print_board(board, "Bubbles: Before Updating Board")

    # Go through the adj_count_list and exchange all the bubbles with a count > 0 with Xs
    mark_bubble_group(board, adj_count_list, row_idx, col_idx)
    #print_board(board, "Bubbles: After marking with Xs picking (row,col)=(%d,%d)" % (row_idx, col_idx))
    #print

    # Determine the rows with a bubble we are going to remove
    rows_with_x = []
    # Determine the columns with a bubble we are going to remove
    cols_with_x = []

    # keep track of the last row and last column
    first_row = 0
    first_col = 0
    last_row = adj_count_list[0][0]
    last_col = adj_count_list[0][1]

    for row, col in adj_count_list:
        if row > last_row:
            last_row = row
        if col > last_col:
            last_col = col
        if row < first_row:
            first_row = row
        if col < first_col:
            first_col = col
        if not row in rows_with_x:
            rows_with_x.append(row)
        if not col in cols_with_x:
            cols_with_x.append(col)

    # make some extra copies
    last_row_copy, first_row_copy, last_col_copy, first_col_copy = last_row, first_row, last_col, first_col

    ####################
    # Shift down phase
    ####################

    while 1:
        ## Now go through from the last row to the first column and move any balls down into X spaces
        found_x = False

        # Go through from the last row to the first row we know will have xs
        for row in xrange(last_row, first_row - 1, -1):
            for col in cols_with_x:
                if board[row][col] == X_VALUE:
                    found_x = True
                    # copy columns down: row-1..0
                    for row_copy in xrange(row, first_row, -1):
                        board[row_copy][col] = board[row_copy - 1][col]

                    # Clear top row
                    board[first_row][col] = SPACE_VALUE

        # We know the first row will not have xs anymore as we have shifted down
        first_row += 1

        if not found_x:
            break

    #print_board(board, "Bubbles: After shift down")
    #print
    ####################
    # Shift right phase
    ####################
    while 1:
        found_hole = False
        for row in xrange(last_row, -1, -1):
            for col in xrange(last_col, first_col - 1, -1):
                assert board[row][col] != X_VALUE
                # if we did not hit a space we can continue
                if board[row][col] != SPACE_VALUE:
                    continue
                # Search to the left to see if there are any columns that have a ball
                for col_search in xrange(col - 1, first_col - 1, -1):
                    if board[row][col_search] != SPACE_VALUE:
                        found_hole = True
                        # shift right from this point to the first column
                        for col_copy in xrange(col_search, -1, -1):
                            board[row][col + col_copy - col_search] = board[row][col_copy]

                        # Where we shifted we need to fill in with empty spaces
                        for col_fill in xrange(col - col_search - 1, -1, -1):
                            board[row][col_fill] = SPACE_VALUE

                        # end our search
                        break
        last_col -= 1
        first_col += 1
        if not found_hole:
            break

    #print_board(board, "Bubbles: After shift right")
    #print 'p',

    # Find any empty rows
    empty_row = -1
    for row in xrange(last_row_copy, -1, -1):
        for col in xrange(len(board[0])):
            if board[row][col] != SPACE_VALUE:
                break
        else:
            empty_row = row
            break

    # Find any empty columns
    empty_col = -1
    for col in xrange(last_col_copy, -1, -1):
        for row in xrange(len(board) - 1, -1, -1):
            if board[row][col] != SPACE_VALUE:
                break
        else:
            empty_col = col
            break

    #Prune our table of empty rows and columns
    for row in xrange(empty_row + 1):
        board.pop(0)

    for col in xrange(empty_col + 1):
        for row in xrange(len(board)):
            board[row].pop(0)

    #print_board(board, "Bubbles: After pruning")
    #print 'p',

    return board

def pick_color(color, color_map, color_list, SPACE_VALUE=SPACE_VALUE):
    # Space 'color' must always return as space
    if color == SPACE_VALUE:
        return ' '

    # Otherwise if we have not picked a color yet than we pop one of our list
    if color_map[color] is None:
        color_map[color] = color_list.pop()
    return color_map[color]

def normalized_hasher(board, NUM_COLORS=NUM_COLORS, pick_color=pick_color):
    """
    Since there are many combinations of boards that yield the same score we need to optimize the hasher to only
    store one version of the combinations. So we exchange the colors such that the colors are always ordered.
    The first ball(s) is color1, the second balls(s) is color2, etc..
    """
    color_map = [None] * NUM_COLORS
    color_list = ['p', 'b', 'g', 'y', 'r']

    # We add '|' as the salt between rows, so a board X x Y doesn't memoize as Y x X
    return '|'.join(''.join([pick_color(col_x, color_map, color_list) for col_x in rows]) for rows in board)

def print_solver_best(best):

    num_rows = best['r']
    num_cols = best['c']

    uncompressed_board = [[conversion_c2i[best['b'][row_x * num_cols + col_x]] for col_x in range(num_cols)] for row_x in range(num_rows)]

    print_board(uncompressed_board, "Bubbles: Best Pick(row,col) = (%(y)d, %(x)d) TotalScore = %(t)d PickScore = %(p)d" % best)
    if best['s']:
        print
        print_solver_best(best['s'])

def solver(board,
           conversion_i2c=conversion_i2c, normalized_hasher=normalized_hasher,
           USE_MEMOIZED=USE_MEMOIZED, MEMOIZATION=MEMOIZATION):
    global SOLVER_COUNT, SOLVER_MEMOIZED

    SOLVER_COUNT += 1
    if USE_MEMOIZED:
        hashed_board = normalized_hasher(board)
        has_best = MEMOIZATION.get(hashed_board, None)

        if has_best is not None:
            SOLVER_MEMOIZED += 1
            return has_best

    # best score for the current board
    # t = Total Score
    # p = The score for the picked bubble group
    # x = The column position of the picked bubble group
    # y = The row position of the picked bubble group
    # b = a compressed version of the board
    # r = number of rows in our board
    # c = number of columns in our board
    # s = solved board
    best = {'t': 0, 'p': 0, 'x': 0, 'y': 0, 's': None}

    # keep track of bubble groups we already picked so we don't go down that path again
    tried_board = [[c for c in row] for row in board]

    #print_board(board, "Bubbles: Before solver()")
    #score_card = [[0] * len(board[0]) for x in xrange(len(board))]

    for row_idx in xrange(len(board)):
        for col_idx in xrange(len(board[0])):
             # if we have already attempted this bubble group. Skip it
            if tried_board[row_idx][col_idx] == X_VALUE:
                continue
            # if empty space. Skip it
            if board[row_idx][col_idx] == SPACE_VALUE:
                continue

            # Create a adjacency count table with x,y set as 1 all others as -1
            adj_count_table = [[-1] * len(board[0]) for x in xrange(len(board))]
            adj_count_table[row_idx][col_idx] = 1
            adj_count_list = [(row_idx, col_idx)]
            color = board[row_idx][col_idx]

            n = compute_ball_adjacency(board, color, adj_count_table, adj_count_list, row_idx, col_idx)
            score = n * (n - 1)

            #score_card[row_idx][col_idx] = score
            #print_board(adj_count_table, "Color: %s Score(%d,%d)=%d Adjacent Balls(%d,%d)=%d Adjacency Table:" % \
            #    (conversion_i2c[color], row_idx, col_idx, score, row_idx, col_idx, n),
            #    converter=identity_converter)

            if score > 0:

                # mark down in our tried board that we attempted this bubble group
                mark_bubble_group(tried_board, adj_count_list, row_idx, col_idx)

                solved = solver(pick_bubble_group(board, adj_count_list, row_idx, col_idx))

                # If picking this bubble group leads to no points
                if solved['t'] == 0 and score > best['t']:
                    # then our best score is just picking this bubble group
                    best['t'] = score
                    best['x'] = col_idx
                    best['y'] = row_idx
                    best['s'] = None
                    best['p'] = score
                    #best['a'] = tuple(adj_count_list)

                # If picking this bubble group leads to a score then add the bubble group score plus the solved board score
                if (solved['t'] + score) > best['t']:
                    # We found a better score
                    best['t'] = solved['t'] + score
                    best['x'] = col_idx
                    best['y'] = row_idx
                    best['s'] = solved
                    best['p'] = score
                    #best['a'] = tuple(adj_count_list)

    #print_board(score_card, "Score Card:", converter=identity_converter)
    #print 's',
    if USE_MEMOIZED:
        # Store board if
        if best['t'] > 0:
            best['b'] = ''.join(''.join([conversion_i2c[col_x] for col_x in row]) for row in board)
            best['r'] = len(board)
            best['c'] = len(board[0])
            MEMOIZATION[hashed_board] = best
    return best

if __name__ == '__main__':
    PrintStats()
    if USE_PSYCO:
        import psyco
        psyco.full()

    best = solver(bubble_board)
    print_solver_best(best)
    global STILL_SOLVING
    STILL_SOLVING = False