Thread: Counting certain characters in recursion

Hey, I'm trying to write a function that uses recursion to count the number of w characters within a group in an array.

wbbwwbww
bbbbwbww
wwwbbwww
wbwbwwbb
wbwwwbwb
wbbbbwww
wbwbbwww
wbwbbwww

For the first group, there is only 1, the second has 3, and etc. I've made a few attempts that either cannot count all of the characters, count the same area twice, or run an infinite loop.

Any help is appreciated.

Post your code.

Code:

int Process(char spaces[][8], int counter, int &group, int x, int y)
{
          if(spaces[x][y] == "w")
          {
               counter++
               if(spaces[x+1][y] == "w")
               {
               spaces[x][y] = "b";
               return Process(spaces[x][y], counter, group, ++x, y);
               }
               if(spaces[x-1][y] == "w")
               {
               spaces[x][y] = "b";
               return Process(spaces[x][y], counter, group, --x, y);
               }
               if(spaces[x][y+1] == "w")
               {
               spaces[x][y] = "b";
               return Process(spaces[x][y], counter, group, x, ++y);
               }
               if(spaces[x][y-1] == "w")
               {
               spaces[x][y] = "b";
               return Process(spaces[x][y], counter, group, ++x, --y);
               }
          }
          
          else if(x == 8)
          {
              ++y;
              x = 0;
              return Process(spaces[x][y], counter, group, x, y);
          }
          
          else if(y == 8)
          {
               return 1;
          }
          
          else
          {
              ++group;
              cout << counter;
              return Process(spaces[++x][y], counter, group, x, y);
          }
}

That's quite a mess, yes.

1) "w" is a (pointer to a) string literal, and anyway can't be compared with ==. The correct literal would be char, eg: 'w'.

2) Break things up into small, well defined functions. Maybe start with:

void update_counters( char* line, size_t length, int& w_counter, int& b_counter );

Note that the function could be either called within a loop or in some recursive function. Point is, the internal logic wouldn't need to change.

3) Why are you jumping both forward and backward into the string? That's just a recipe for disaster. Just move forward (starting at zero, of course) to simplify things.

4) Perform the bounds checking (8, in this case) *before* you actually process the character. Reason being that if the strings are not null terminated (and in this case, they appear not to be) you'll actually wrap around to the next line, which will just botch your results. And anyway, it's just good form to check bounds before anything else.

5) I'm not really clear what your overall tactic here is, but I think it's safe to say that only one recursive call within the function should be sufficient.

As you're using C++, why not use strings and stringstream's? I'm no expert in properly using these but they've been instrumental in processing strings and are far easier to work with than the standard C's string functions like strstr() and strcmp(). They're also a lot safer to use in terms of memory allocations and cleanup not to mention dangling pointers and all kinds of other nasty business involved with pointers.

This, of course, is assuming that your requirements are flexible enough to allow for the use of a different solution to the same problem.

They're also a lot safer to use in terms of memory allocations and cleanup not to mention dangling pointers and all kinds of other nasty business involved with pointers.

That is not a valid argument for using/not using strings or stringstream. C++ programmers should already know how to deal with memory and pointers.

The argument for using strings over arrays is simply ease of use and concatenation. The argument for using stringstream over string is that you can treat the stringstream as any other stream and therefore concatenation and string building becomes a snap. The stringstream can also be converted into a string which can then be converted to a C array-style string so it can be used in functions that require those types.

Beware of stringstream in MSVC 2003 and MSVC 2005. 2005 was known to have a leak in it prior to SP1 and I'm almost positive I have enough evidence to support the claim that 2003 has the same leak.