3-in-a-row or more logic

Question

This is a bit more difficult than it seems and the one other post on here isn't sufficient. You have a row of n items, and each item could be any one of 5 colors. You need to find if there are any runs of 3 or more items together of the same color and destroy them.

Yellow, Red, Blue, Green, Red, Red - destroy nothing

Red, Red, Red, Green, Yellow, Red - destroy the first set of 3 Red, but not the 6th red

Red, Purple, Red, Red, Red, Red - destroy only the set of 4 Red

You can't simply check each item to see if the item previous to it has the same color, and destroy them when that happens twice in a row (meaning 3 matching items), because then you are not accounting for the fact that there could be 4 or more in a row. Are there any robust algorithms out there for this?

Answer 1

This is a very simple programming problem.

Here's a straight forward solution.

For every piece

1. check if previous two pieces are same color
2. if true, destroy those three pieces.
3. for every piece after that, if current color == destroyed color, destroy it. If not, break out of the loop.

If it's possible to have more than one set of three at once in a single row (e.g. 3 reds then 3 blues), you'll have to run the loop multiple times until it doesn't destroy anything.

Answer 2

I think this can be done amazingly easy with regular expressions (provided you can provide the gameboard as string).

Once you have the board in stringform, use the following regex:

(\w)         //capture any letter
(\1{2,})     //capture that letter again twice or more.

The beauty of this is that it works on any number of items, and any amount of different items/colours.

Answer 3

Use two nested loops. The outer one will loop over the array and will be treated as the beginning position for a possible run. The inner will look for the end of the run by starting at the current beginning position and iterating as far as it can on the same color.

for (int i = 0; i < n;)
    int j = i+1;
    for (; j < n; ++j)
        if (color[j] != color[i])
            break;
    // at this point, there is a run of size j - i from element i to j - 1
    if (j - i >= 3)
        // mark elements for destruction
    // start looking for more runs at the end of the current run
    i = j;

This should find all the runs of 3 or more. I wrote "mark elements for destruction" rather than "destroy elements" because it's simpler to find multiple runs this way, since you don't have to worry about the loop indices changing due to destroying a bunch of elements in the middle of iteration. You can go back through in a second pass and actually destroy them.

Answer 4

While I basically agree with Nathan's answer, I wanted to emphasize that (a) another reason to find all the matches at once is for presentation purposes: it just looks better to blow them all up together — and in the more-than-one-dimensional case, it can be relevant because not all matches will stay matches after partial destruction (think of a plus shape on a 2d match-3), and (b) if this is like most match-3s, you'll probably need an outer-outer loop for handling the 'nested' matches that appear (imagine a situation like RGGGRR). What's more, in the 1d case you can actually get by with a single loop through the interior and some careful tests. My structure would look something like this:

bool bMatchesFound;
matchList.clear();
do {
  bMatchesFound = false;
  eColor matchColor = gameBoard[0].color;
  int startPos = 0;
  for ( int curPos=1; curPos < gameBoard.len(); curPos++ ) {
    if ( gameBoard[curPos].color != matchColor ) {
      // we've ended a run; now check to see if it was long enough
      if ( curPos-startPos >= 3 ) {
        // It was - go ahead and add it to our list of matches
        matchList.add(Match(startPos, curPos-1, matchColor));
        bMatchesFound = true;
      }
      // now, regardless, make sure we start a new match-run here
      startPos = curPos;
      matchColor = gameBoard[curPos].color;
    }
  }
  // Finally, check for a match at the end - if our 'last' startPos
  // was far enough back.
  if ( startPos <= gameBoard.len()-3 ) {
    matchList.add(Match(startPos, gameBoard.len()-1, matchColor);
    bMatchesFound = true;
  }
  // 'destroy' all our matches (with suitable pyrotechnics)
  destroyMatches(matchList);
  // and keep doing this until we run out of matches
} while ( bMatchesFound );