how to validate boolean array

[Beju]

Hello,

I have an array of n booleans. I want to make sure that the array consitsts of two continuous "blocks" of zeros and ones, i.e.:

bool ar = { 1, 1, 0, 0, 0 }; // this is ok
bool ar = { 1, 0, 0, 1, 1 }; // this is ok
bool ar = { 1, 0, 1, 0, 1 }; // this is NOT ok 

Thanks in advance.

[Duthomhas]

How would you do it by hand?

(Take the time to get out a piece of paper and a pencil and draw it. This will move you closer to the answer.)

[kempofighter]

Why is the second one okay?

[Duthomhas]

It has at least two consecutive zeros, and at least two consecutive ones.

[Beju]

Duoas: not quite. The "blocks" in the second example are continuous, because they can wrap around n, so for example first and nth element are consecutive.

I tried to do than on a piece of paper, I found some solutions but none of them is satisfying me or is too complex to implement (too much resources used). So I thought I ask here and maybe someone will suggest me some clever way to do that:)

[bongv]

how about doing like this:

boolean validateBooleanArray(boolean[] ar) {
   boolean ok = false;

   int ar_size = sizeof(ar)/ar[0];
   for (int i =0; i < ar_size; i++) {
      if (!ok && i > 3) {

           ok = ( (ar[i] == ar[i-1]) && (ar[i-1] != ar[i-2]) && (ar[i-2] == ar[i-3]) );
           if (ok)
              return ok;

      } 

   }

   return ok;
}

[Beju]

This will not work for the simplest

arr[] = {0,0,0,0,1};
//or
arr[]= {1,0,0,0,0};

not mentioning more complex

arr[] = {1,0,0,0,1};

;)

EDIT:
Wow, you changed it, but it still desn't work. But that's one hell of a code:D why are you checking exectly 3 elements back?;)

[Duthomhas]

Ah, I understand better now.

If you split your array up into collections of consecutive zeros and ones, do you have one of the following conditions satisified:

  1. There are exactly two sections.
  2. There are exactly three sections, and the first and last section have the same value.

Since splitting it up that way you must have either 0 1 0 or 1 0 1 to get three sections, you can combine those conditions to read:

  1. There are exactly two or exactly three sections.

The trick now is making a list of sections.

1   1 | 0   0   0 --> exactly two sections
1 | 0   0 | 1   1 --> exactly three sections
1 | 0 | 1 | 0 | 1 --> five is neither two nor three sections
0   0   0   0   0 --> one is neither two nor three sections

Hope this helps.

[bongv]

@Beju. Hi, kindly note that I did not compile my code. I just typed it directly to this site. So there might be some compilation errors. And the idea provided is in its simplest form. Further improvements should be done, if it is to be implemented.


I am checking 3 elements back, plus the current element => Meaning I am checking 4 continuous elements. My understanding of 2 continuous zeroes and ones, is that they should be in adjancent elements. That, is "..1100.." or "..0011..".

But my interpretation/understanding can be wrong also.

[Duthomhas]

Yes, you are misunderstanding.
Also, you are trying to simply give an answer.

Given a circular list of boolean values, show that it:
  - has at least one 1
  - has at least one 0
  - all 1s are adjacent and all 0s are adjacent

Finally, I have learned from experience that it is always worth my time to compile code I post before posting, so as to avoid embarrassment.

I have already solved this problem two different ways. Hence, I consider myself qualified to help Beju solve his problem himself. This is the essence of learning.

Hope this helps. (BTW, welcome to the forum!)

[Beju]

Thanks, Duoas! :)

I was able to figure out a satisfying solution, which is simple and doesn't consume too much resources. I'll post it here, maybe someone will find it useful. Also, if you have any suggestions on how to improove it or maybe you see a mistake here, please let me know:)

#include <iostream>


const uint32_t arraySize = 8;

bool validate(const bool (&array)[arraySize])
{
	uint8_t blockCntr = 0;

	for(int32_t idx = 0; idx < arraySize; idx++)
	{
		if((array[idx] == true) && (array[(idx + 1) % arraySize] == false))
		{
			++blockCntr;
		}
	}

	if(blockCntr == 1)
	{
		return true;
	}
	return false;

}



int main(int argc, char * argv[])
{

	bool testData[][arraySize] = 
	{
		{0, 0, 0, 0, 0, 0, 0, 0},//invalid
		{1, 1, 1, 1, 1, 1, 1, 1},//invalid
		{0, 1, 0, 1, 0, 1, 0, 1},//invalid
		{1, 1, 0, 1, 1, 1, 0, 1},//invalid
		{0, 0, 0, 0, 1, 1, 1, 0},//valid
		{1, 0, 0, 0, 0, 0, 0, 0},//valid
		{0, 0, 0, 0, 0, 0, 0, 1},//valid
		{1, 0, 0, 0, 0, 0, 0, 1},//valid
		{1, 1, 1, 0, 1, 1, 1, 1}//valid
	};
	
	uint8_t testDataSize = sizeof(testData) / sizeof(testData[0]);
	
	std::cout << std::boolalpha;

	for(int32_t idx = 0; idx < testDataSize; idx++)
	{
		std::cout << "test case " << idx + 1 << ": " 
				  << validate(testData[idx]) 
				  << std::endl;
	}

	return 0;
}

The program output is:

test case 1: false
test case 2: false
test case 3: false
test case 4: false
test case 5: true
test case 6: true
test case 7: true
test case 8: true
test case 9: true

Thanks for help!:)

[Duthomhas]

Very nice. As for improvements, I can help. :-)

Don't use a fixed-size array; pass its length. Also, you can get rid of the remainder operation -- it doesn't serve anything. Finally, you don't need to test against true and false directly, or branch to separate boolean returns based upon a condition. Oh, the name "array" is a horrible variable name -- you are asking for trouble on that one, JSYK.

bool validate( const bool* bs, unsigned len )
{
	if (len < 2) return false;
	unsigned btCount = 0;  // block transition count
	for (unsigned n = 1; n < len; ++n)
	{
		if (bs[ n ] != bs[ n - 1 ])
			++btCount;
	}
	return (btCount < 3);  // 1 or 2 transitions == 2 or 3 blocks
}

Glad to have been of help!

[Beju]

That's a very nice idea:) Thanks a lot! I didn't thought about simply counting the "changes" in the array :)

[Duthomhas]

Actually, that's exactly what you did, only your "blockCount" variable relied upon that modulo operator, and the new loop eliminates it. So in order to keep the return condition (line 10) simple, instead of something like (blockCount == 2) || (blockCount == 3) and starting the blockCount with a value of one, I reconsidered what to name the variable. Since you were counting "changes", that is, transitions, I renamed it as such.
:-)