SameGame

SameGame is a game with a grid of colored blocks. If there are two or more blocks of the same color, all of which are connected, these form a group. More formally, a group is a set of 2 or more blocks, each of which has the same color, in which all pairs of blocks are connected by a sequence of horizontal or vertical steps, each of which moves to a block in the group. A group may be removed only if it is not a subset of some larger group. When a group is removed, all of the blocks above the removed blocks "fall down", meaning that any blocks that are immediately above an empty space move down until they are resting in the bottom row, or immediately above another block. If any entirely empty columns are created then columns to the right of the empty columns shift to the left until all of the empty columns are on the right side. As blocks are removed, points are accumulated based on the number of blocks removed each time. Each time a group of blocks is removed, the point total is increased by n*(n-1)/2 where n is the number of blocks in the group. Additionally, if every single block has been removed from the grid by the end of the game, the final score is multiplied by 4.

The input will be formatted as a String[], board, where each element represents a row of blocks, and each character tells which color a given block is.

For example, {"RBB","RRR","RBB"} represents:

        RBB
        RRR
        RBB

Where 'R' and 'B' are the only two colors present.

One possible sequence of moves would be to first remove the five 'R's, which are all connected and form a group. This would give us 10 points (5*4/2) and make the board look as follows: (where '-' represents empty space):

        -BB
        ---
        -BB

Now the pieces fall down and shift to the left, giving:

        ---
        BB-
        BB-

If we then remove the group of 4 B's, we get an additional 6 points. This removes all of the blocks so we multiply the total (16) by 4, and our final score is 64.

If the board is small enough, we can simply use brute force to find the optimal sequence of groups to remove to obtain the highest score. However, as the number of blocks grows, brute force quickly becomes infeasible. Thus, in order to write a program that plays well, we must use some intelligent technique to remove pieces - albeit a sub-optimal one. One important observation to make in trying to come up with a good strategy is that the number of points grows non-linearly, and we get more points per block if we remove larger groups. This suggests that we should save one color for last, and remove smaller groups first. Your task is to implement the following strategy:

You will be given a String, order, defining an ordering on the colors. You should always remove groups whose color appears earlier in order. So, if order were "RB", we would never remove a group of 'B's if there were a group of 'R's we could remove. When there are many groups of the same color, remove groups with less blocks in them first. If there is a tie, remove the group which extends into (has at least one character in) the lower indexed element of the board. If there is still a tie, remove the group which contains the lower indexed character in the lowest indexed element that both groups extend into. Using this method, continue removing groups until there are none left and then return the final score.