Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

G

By: a guest on Oct 8th, 2009  |  syntax: Python  |  size: 15.90 KB  |  views: 275  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. '''
  2. Created on Oct 4, 2009
  3. '''
  4. import sys
  5. from copy import deepcopy
  6. from threading import Timer
  7.  
  8. hard_bubble_board = (
  9.            'pbgpbpyggrbpbgr',
  10.            'bgyrbpprgyrgpbb',
  11.            'bgyprypbpbbbrpb',
  12.            'bpprpbpbgrrrgrr',
  13.            'ppbrbpygpryryrb',
  14.            'rgrgpbyyypggrbr',
  15.            'gygrprrybbrrgrr',
  16.            'rgpbpggrbypyryr',
  17.            )
  18.  
  19. simple_bubble_board = (
  20.                 'rgrgpbyyypggrbr',
  21.                 'gygrprrybbrrgrr',
  22.                 'rgpbpggrbypyryr',
  23.                 )
  24.  
  25. X_VALUE = 5
  26. SPACE_VALUE = 6
  27. NUM_COLORS = 5
  28.  
  29. SOLVER_COUNT = 0
  30. TOTAL_SOLVER_COUNT = 0
  31. SOLVER_MEMOIZED = 0
  32. USE_MEMOIZED = True
  33. USE_PSYCO = sys.platform == 'win32'
  34. STILL_SOLVING = True
  35. MEMOIZATION = {'': {'t': 0}}
  36.  
  37. def PrintStats():
  38.     global SOLVER_COUNT, TOTAL_SOLVER_COUNT, STILL_SOLVING
  39.     TOTAL_SOLVER_COUNT += SOLVER_COUNT
  40.     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
  41.     SOLVER_COUNT = 0
  42.     if STILL_SOLVING:
  43.         Timer(10.0, PrintStats).start()
  44.  
  45. conversion_c2i = {'p':0, 'b':1, 'g':2, 'y':3, 'r':4, 'x':X_VALUE, ' ':SPACE_VALUE}
  46. conversion_i2c = ('p', 'b', 'g', 'y', 'r', 'x', ' ')
  47.  
  48. i2c_converter = lambda x: conversion_i2c[x]
  49. identity_converter = lambda x: x
  50.  
  51. # convert to a faster underlying representation of the board
  52. bubble_board = [[conversion_c2i[c] for c in row] for row in simple_bubble_board]
  53.  
  54. def compute_ball_adjacency(board, color, adjacency_table, adjacency_list, row_idx, col_idx):
  55.     # Check the four bubbles adjacent for the same color value
  56.     #          (x+0,y-1)
  57.     # (x+1,y+0)(x+0,y+0)(x-1, y+0)
  58.     #          (x+0,y+1)
  59.  
  60.     # Number of bubbles adjacent
  61.     num_bubles_adjacent = 1
  62.  
  63.     # Check (x+1,y+0) .. first check whether we are in range
  64.  
  65.     r = row_idx
  66.     c = col_idx + 1
  67.     if c < len(board[0]):
  68.         # if (0 or 1) that means we already figured out the ball count
  69.         # Check whether we scored this one already
  70.         if adjacency_table[r][c] == -1:
  71.             # Make sure it is the same color
  72.             if board[r][c] == color:
  73.                 # Same color update our score card
  74.                 adjacency_table[r][c] = 1
  75.                 adjacency_list.append((r, c))
  76.                 # go down the recursive path
  77.                 num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
  78.             else:
  79.                 # We are not the same color so mark it as a 0
  80.                 adjacency_table[r][c] = 0
  81.  
  82.     # Check (x+0,y-1) .. first check whether we are in range
  83.     r = row_idx - 1
  84.     c = col_idx
  85.     if r >= 0:
  86.         # if (0 or 1) that means we already figured out the ball count
  87.         # Check whether we scored this one already
  88.         if adjacency_table[r][c] == -1:
  89.             # Make sure it is the same color
  90.             if board[r][c] == color:
  91.                 # Same color update our score card
  92.                 adjacency_table[r][c] = 1
  93.                 adjacency_list.append((r, c))
  94.                 # go down the recursive path
  95.                 num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
  96.             else:
  97.                 # We are not the same color so mark it as a 0
  98.                 adjacency_table[r][c] = 0
  99.  
  100.     # Check (x+0,y-1) .. first check whether we are in range
  101.     r = row_idx
  102.     c = col_idx - 1
  103.     if c >= 0:
  104.         # if (0 or 1) that means we already figured out the ball count
  105.         # Check whether we scored this one already
  106.         if adjacency_table[r][c] == -1:
  107.             # Make sure it is the same color
  108.             if board[r][c] == color:
  109.                 # Same color
  110.                 # update our score card
  111.                 adjacency_table[r][c] = 1
  112.                 adjacency_list.append((r, c))
  113.                 # go down the recursive path
  114.                 num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
  115.             else:
  116.                 # We are not the same color so mark it as a 0
  117.                 adjacency_table[r][c] = 0
  118.  
  119.     # Check (x+0,y+1) .. first check whether we are in range
  120.     r = row_idx + 1
  121.     c = col_idx
  122.     if r < len(board):
  123.         # if (0 or 1) that means we already figured out the ball count
  124.         # Check whether we scored this one already
  125.         if adjacency_table[r][c] == -1:
  126.             # Make sure it is the same color
  127.             if board[r][c] == color:
  128.                 # Same color
  129.                 # update our score card
  130.                 adjacency_table[r][c] = 1
  131.                 adjacency_list.append((r, c))
  132.                 # go down the recursive path
  133.                 num_bubles_adjacent += compute_ball_adjacency(board, color, adjacency_table, adjacency_list, r, c)
  134.             else:
  135.                 # We are not the same color so mark it as a 0
  136.                 adjacency_table[r][c] = 0
  137.     return num_bubles_adjacent
  138.  
  139. def print_board(board, msg, converter=i2c_converter):
  140.     print msg
  141.     print ' |' + ''.join(['%3d ' % i for i in xrange(len(board[0]))])
  142.     print ' +' + ('----' * (len(board[0])))
  143.     for row in xrange(len(board)):
  144.         print str(row) + '|',
  145.         for col in xrange(len(board[0])):
  146.              sys.stdout.write('%3s ' % converter(board[row][col]))
  147.         print
  148.  
  149. def mark_bubble_group(board, adj_count_list, row_idx, col_idx,
  150.                       X_VALUE=X_VALUE):
  151.     # Go through the adj_count_list and exchange all the bubbles with a count > 0 with Xs
  152.     for row, col in adj_count_list:
  153.         assert board[row][col] != X_VALUE
  154.         # convert to an x
  155.         board[row][col] = X_VALUE
  156.  
  157. def pick_bubble_group(bubbles_board, adj_count_list, row_idx, col_idx,
  158.                       X_VALUE=X_VALUE, SPACE_VALUE=SPACE_VALUE, mark_bubble_group=mark_bubble_group):
  159.  
  160.     # Make a copy of our bubbles, we are going to return this reduced board
  161.     board = [[c for c in r] for r in bubbles_board]
  162.     #print_board(board, "Bubbles: Before Updating Board")
  163.  
  164.     # Go through the adj_count_list and exchange all the bubbles with a count > 0 with Xs
  165.     mark_bubble_group(board, adj_count_list, row_idx, col_idx)
  166.     #print_board(board, "Bubbles: After marking with Xs picking (row,col)=(%d,%d)" % (row_idx, col_idx))
  167.     #print
  168.  
  169.     # Determine the rows with a bubble we are going to remove
  170.     rows_with_x = []
  171.     # Determine the columns with a bubble we are going to remove
  172.     cols_with_x = []
  173.  
  174.     # keep track of the last row and last column
  175.     first_row = 0
  176.     first_col = 0
  177.     last_row = adj_count_list[0][0]
  178.     last_col = adj_count_list[0][1]
  179.  
  180.     for row, col in adj_count_list:
  181.         if row > last_row:
  182.             last_row = row
  183.         if col > last_col:
  184.             last_col = col
  185.         if row < first_row:
  186.             first_row = row
  187.         if col < first_col:
  188.             first_col = col
  189.         if not row in rows_with_x:
  190.             rows_with_x.append(row)
  191.         if not col in cols_with_x:
  192.             cols_with_x.append(col)
  193.  
  194.     # make some extra copies
  195.     last_row_copy, first_row_copy, last_col_copy, first_col_copy = last_row, first_row, last_col, first_col
  196.  
  197.     ####################
  198.     # Shift down phase
  199.     ####################
  200.  
  201.     while 1:
  202.         ## Now go through from the last row to the first column and move any balls down into X spaces
  203.         found_x = False
  204.  
  205.         # Go through from the last row to the first row we know will have xs
  206.         for row in xrange(last_row, first_row - 1, -1):
  207.             for col in cols_with_x:
  208.                 if board[row][col] == X_VALUE:
  209.                     found_x = True
  210.                     # copy columns down: row-1..0
  211.                     for row_copy in xrange(row, first_row, -1):
  212.                         board[row_copy][col] = board[row_copy - 1][col]
  213.  
  214.                     # Clear top row
  215.                     board[first_row][col] = SPACE_VALUE
  216.  
  217.         # We know the first row will not have xs anymore as we have shifted down
  218.         first_row += 1
  219.  
  220.         if not found_x:
  221.             break
  222.  
  223.     #print_board(board, "Bubbles: After shift down")
  224.     #print
  225.     ####################
  226.     # Shift right phase
  227.     ####################
  228.     while 1:
  229.         found_hole = False
  230.         for row in xrange(last_row, -1, -1):
  231.             for col in xrange(last_col, first_col - 1, -1):
  232.                 assert board[row][col] != X_VALUE
  233.                 # if we did not hit a space we can continue
  234.                 if board[row][col] != SPACE_VALUE:
  235.                     continue
  236.                 # Search to the left to see if there are any columns that have a ball
  237.                 for col_search in xrange(col - 1, first_col - 1, -1):
  238.                     if board[row][col_search] != SPACE_VALUE:
  239.                         found_hole = True
  240.                         # shift right from this point to the first column
  241.                         for col_copy in xrange(col_search, -1, -1):
  242.                             board[row][col + col_copy - col_search] = board[row][col_copy]
  243.  
  244.                         # Where we shifted we need to fill in with empty spaces
  245.                         for col_fill in xrange(col - col_search - 1, -1, -1):
  246.                             board[row][col_fill] = SPACE_VALUE
  247.  
  248.                         # end our search
  249.                         break
  250.         last_col -= 1
  251.         first_col += 1
  252.         if not found_hole:
  253.             break
  254.  
  255.     #print_board(board, "Bubbles: After shift right")
  256.     #print 'p',
  257.  
  258.     # Find any empty rows
  259.     empty_row = -1
  260.     for row in xrange(last_row_copy, -1, -1):
  261.         for col in xrange(len(board[0])):
  262.             if board[row][col] != SPACE_VALUE:
  263.                 break
  264.         else:
  265.             empty_row = row
  266.             break
  267.  
  268.     # Find any empty columns
  269.     empty_col = -1
  270.     for col in xrange(last_col_copy, -1, -1):
  271.         for row in xrange(len(board) - 1, -1, -1):
  272.             if board[row][col] != SPACE_VALUE:
  273.                 break
  274.         else:
  275.             empty_col = col
  276.             break
  277.  
  278.     #Prune our table of empty rows and columns
  279.     for row in xrange(empty_row + 1):
  280.         board.pop(0)
  281.  
  282.     for col in xrange(empty_col + 1):
  283.         for row in xrange(len(board)):
  284.             board[row].pop(0)
  285.  
  286.     #print_board(board, "Bubbles: After pruning")
  287.     #print 'p',
  288.  
  289.     return board
  290.  
  291. def pick_color(color, color_map, color_list, SPACE_VALUE=SPACE_VALUE):
  292.     # Space 'color' must always return as space
  293.     if color == SPACE_VALUE:
  294.         return ' '
  295.  
  296.     # Otherwise if we have not picked a color yet than we pop one of our list
  297.     if color_map[color] is None:
  298.         color_map[color] = color_list.pop()
  299.     return color_map[color]
  300.  
  301. def normalized_hasher(board, NUM_COLORS=NUM_COLORS, pick_color=pick_color):
  302.     """
  303.    Since there are many combinations of boards that yield the same score we need to optimize the hasher to only
  304.    store one version of the combinations. So we exchange the colors such that the colors are always ordered.
  305.    The first ball(s) is color1, the second balls(s) is color2, etc..
  306.    """
  307.     color_map = [None] * NUM_COLORS
  308.     color_list = ['p', 'b', 'g', 'y', 'r']
  309.  
  310.     # We add '|' as the salt between rows, so a board X x Y doesn't memoize as Y x X
  311.     return '|'.join(''.join([pick_color(col_x, color_map, color_list) for col_x in rows]) for rows in board)
  312.  
  313. def print_solver_best(best):
  314.  
  315.     num_rows = best['r']
  316.     num_cols = best['c']
  317.  
  318.     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)]
  319.  
  320.     print_board(uncompressed_board, "Bubbles: Best Pick(row,col) = (%(y)d, %(x)d) TotalScore = %(t)d PickScore = %(p)d" % best)
  321.     if best['s']:
  322.         print
  323.         print_solver_best(best['s'])
  324.  
  325. def solver(board,
  326.            conversion_i2c=conversion_i2c, normalized_hasher=normalized_hasher,
  327.            USE_MEMOIZED=USE_MEMOIZED, MEMOIZATION=MEMOIZATION):
  328.     global SOLVER_COUNT, SOLVER_MEMOIZED
  329.  
  330.     SOLVER_COUNT += 1
  331.     if USE_MEMOIZED:
  332.         hashed_board = normalized_hasher(board)
  333.         has_best = MEMOIZATION.get(hashed_board, None)
  334.  
  335.         if has_best is not None:
  336.             SOLVER_MEMOIZED += 1
  337.             return has_best
  338.  
  339.     # best score for the current board
  340.     # t = Total Score
  341.     # p = The score for the picked bubble group
  342.     # x = The column position of the picked bubble group
  343.     # y = The row position of the picked bubble group
  344.     # b = a compressed version of the board
  345.     # r = number of rows in our board
  346.     # c = number of columns in our board
  347.     # s = solved board
  348.     best = {'t': 0, 'p': 0, 'x': 0, 'y': 0, 's': None}
  349.  
  350.     # keep track of bubble groups we already picked so we don't go down that path again
  351.     tried_board = [[c for c in row] for row in board]
  352.  
  353.     #print_board(board, "Bubbles: Before solver()")
  354.     #score_card = [[0] * len(board[0]) for x in xrange(len(board))]
  355.  
  356.     for row_idx in xrange(len(board)):
  357.         for col_idx in xrange(len(board[0])):
  358.              # if we have already attempted this bubble group. Skip it
  359.             if tried_board[row_idx][col_idx] == X_VALUE:
  360.                 continue
  361.             # if empty space. Skip it
  362.             if board[row_idx][col_idx] == SPACE_VALUE:
  363.                 continue
  364.  
  365.             # Create a adjacency count table with x,y set as 1 all others as -1
  366.             adj_count_table = [[-1] * len(board[0]) for x in xrange(len(board))]
  367.             adj_count_table[row_idx][col_idx] = 1
  368.             adj_count_list = [(row_idx, col_idx)]
  369.             color = board[row_idx][col_idx]
  370.  
  371.             n = compute_ball_adjacency(board, color, adj_count_table, adj_count_list, row_idx, col_idx)
  372.             score = n * (n - 1)
  373.  
  374.             #score_card[row_idx][col_idx] = score
  375.             #print_board(adj_count_table, "Color: %s Score(%d,%d)=%d Adjacent Balls(%d,%d)=%d Adjacency Table:" % \
  376.             #    (conversion_i2c[color], row_idx, col_idx, score, row_idx, col_idx, n),
  377.             #    converter=identity_converter)
  378.  
  379.             if score > 0:
  380.  
  381.                 # mark down in our tried board that we attempted this bubble group
  382.                 mark_bubble_group(tried_board, adj_count_list, row_idx, col_idx)
  383.  
  384.                 solved = solver(pick_bubble_group(board, adj_count_list, row_idx, col_idx))
  385.  
  386.                 # If picking this bubble group leads to no points
  387.                 if solved['t'] == 0 and score > best['t']:
  388.                     # then our best score is just picking this bubble group
  389.                     best['t'] = score
  390.                     best['x'] = col_idx
  391.                     best['y'] = row_idx
  392.                     best['s'] = None
  393.                     best['p'] = score
  394.                     #best['a'] = tuple(adj_count_list)
  395.  
  396.                 # If picking this bubble group leads to a score then add the bubble group score plus the solved board score
  397.                 if (solved['t'] + score) > best['t']:
  398.                     # We found a better score
  399.                     best['t'] = solved['t'] + score
  400.                     best['x'] = col_idx
  401.                     best['y'] = row_idx
  402.                     best['s'] = solved
  403.                     best['p'] = score
  404.                     #best['a'] = tuple(adj_count_list)
  405.  
  406.     #print_board(score_card, "Score Card:", converter=identity_converter)
  407.     #print 's',
  408.     if USE_MEMOIZED:
  409.         # Store board if
  410.         if best['t'] > 0:
  411.             best['b'] = ''.join(''.join([conversion_i2c[col_x] for col_x in row]) for row in board)
  412.             best['r'] = len(board)
  413.             best['c'] = len(board[0])
  414.             MEMOIZATION[hashed_board] = best
  415.     return best
  416.  
  417. if __name__ == '__main__':
  418.     PrintStats()
  419.     if USE_PSYCO:
  420.         import psyco
  421.         psyco.full()
  422.  
  423.     best = solver(bubble_board)
  424.     print_solver_best(best)
  425.     global STILL_SOLVING
  426.     STILL_SOLVING = False