Minimum steps to reach the end of game

Question

I am programming a very simple game.

• Given n bricks with k colors place in a circle
• If a brick removed, the brick which to be adjacent to it and have same color will be remove.
• For each step, player can remove only one brick (but if there are exist a brick adjacent to it and have the same color, the step will not count)
• The game end iff all the bricks have been removed

How can I get the minimum steps required to reach the end of game ? (My current solution is backtracking, I am thinking about dynamic programming)

EXAMPLE:

4 bricks with 3 colors R, G, B place like this:
R G B B G R B G B R R G (R) (let number it 0, 1, 2, ...)

Remove 2 -> 3 will be removed (step = 0)
R G <B> <B> G R B G B R R G

Remove 0 (step = 1)
<R> G * * G R B G B R R G

Remove 4 -> 1, 11 will be removed (step = 1)
* <G> * * <G> R B G B R R <G>

Remove 10 -> 9, 5 will be removed (step = 1)
* * * * * <R> B G B <R> <R> *

Remove 7 (step = 2)
* * * * * * B <G> B * * *

Remove 8 -> 6 removed -> end game, step = 2, minimal
* * * * * * <B> * <B> * * *

Really sorry for my English

Answer 1

Where is a solution with O(N³) complexity.

A dynamic programing. To understand how it works, and that it does, consider some sequence removing all the blocks. Now let us mark all the consequent blocks, removed together at single step. We will mark them on the initial circle. Each step can be marked as a segment of blocks of the same color (with all different blocks inside removed earlier). Below is such picture for your example:

initial: RGBBGRBGBRRG
step 1:    BB
step 2:  R
step 3:  -G--G      G
step 4:  -----R   RR-
step 5:  ------B B---
step 6:         G

Each of 'segments' are either not intersecting, or earlier one is completely inside later one. Thus, there is a way to break circle at some point. In your example it can be done between blocks 5 and 6 (or 6 and 7 also).

Now you can see the structure of solution - we must know the minimum number of steps to completely remove some continuous segment of blocks, not the circle of blocks. To do so we will have a dynamic programming F(i,j)="minumum number of steps needed to completely remove blocks from i to j". Note, that there may be j < i, which means that segment goes over the edge in the initial blocks (like step 5 on the picture above). If we can calculate F the answer will be minimum from all F(i, (i+n-1)%n) for i=0..n-1.

The base is quite obvious, empty segment (j == i-1) requires 0 steps, one block segment (i==j) requires 1 step.

The rest is harder. Consider the first block in the segment. It is a beginning of some segment of blocks removed at some step. It must end somewhere at the block of the same color. Thus, we have:

F(i,j) = min{G(i,t)+F(t+1,j) },  i<=t <= j, blocks t and i have the same color

Here, G(i,j) is another dynamic programming, giving answer to "how many steps are required to remove all blocks from i to j, removing blocks i and j together at the last step". Remember, blocks are in line, not in circle here.

We try t as the end of segment, and thus we need G(i,t) steps to remove all these blocks. And we need another F(t+1,j) steps to remove all other blocks.

G has the same base, as F. Now look back at the picture above. The last step in the segment may consist not only of two blocks i and j (like step 3). It may have some intermediate blocks. And we will try every possible intermediate block:

G(i,j) = min{F(i+1, t-1)+G(t, j)}, i < t <= j, blocks t and i have the same color.

What is happening here? We consider block t to be the next in the line of last removed blocks. To do so, we first have to completely remove all blocks between i and t. It requires F(i+1, t-1) steps. Then we will count, how many steps we will need to remove all blocks from t to j, while corner blocks are removed last. It requires G(t, j) steps. Now block i can be removed for free, because it is adjacent to block t, and can be removed together with it at the last step. Note, how t may be equal to the j. Thus we can cover moves with only two removed blocks.

This solution requires O(N²) memory and O(N³) time. Easiest way to implement it would be lazy dynamic programming (using recursive functions with memorization of an answer).

If you need also the sequence of steps, it is a bit harder. Each function F and G should also store the intermediate variable t value, which gives the minimum answer. Then you can reconstruct the steps using another recursive function, which will mirror F and G computation using only stored value of 't'. This way you will get all the segments, now you can output them from smallest to largest.

Edit:

Note, because j can be less than i inside F and G, you should be careful. It is not that i <= t <= j it is what t starts from i and increases until it reaches j (it may run over the end and turn to 0 from n-1). The similar for i < t <= j.

Also there is no way to pass an empty segment for the function, therefore there should not be base for j==i-1. Instead you should not call F and G in case if there is no blocks there to remove.