Consecutive 0's--Application of BFS
A.First Edition
This is actually another application of my BFS class, or you can call it fourth edition of BFS class, whatever.
The base framework are exactly same as Counting problem except that I standardize my BFS class once more. I made
it similar possible to inheriting! As I mentioned before, I use a static private BFS object for "root" which
destroy the OO as we cannot override a static object which is declared as BFS. All its derived class is impossible
to override it. Now the problem solved by declaring it only as a pointer of BFS. And when the derived class is
created, he call the initialize() method and pass its own pointer as parameter. Then the root is pointing to this
object itself! In order all his descendants to be sure of same class, programmer need to override method
"createSon" which simply create a new object of descendant class.
A string that contains 0s,1s and 2s is called a ternary string. Find the number of ternary strings that contain
consecutive 0s.(This is the exact complement problem of "countNumber".)
No matter how complicated a problem may become, we can divide and conquer it by counting! And breadth-first-search
is one of the simplest way to do it. This is an application of my BFS class which allow user to override several
key method to do the BFS. In this case, user need to override two method: createSon() and validateOption().
1. bool Isomorphic::validateOption(int sonData)
This is always the application specific method. In this case, you have to only take care the last two level. As you
know, if it has consecutive 0's, it either ended with consecutive 0's. Or it has consecutive 0's at previous part.
And if it doesnot have 2 consecutive 0's, then the creating of last two level is vital. It must be 0,0. Otherwise
it would be impossible to have 2 consecutive 0's. I used a boolean switch like "amZero" to indicate if it prevous
part has two 0's.
2. BFS* Isomorphic::createSon()
You must override this virtual function! Otherwise there will be no inheritation!
3. void BFS::initialize(BFS* now)
I modified this method by adding a parameter. Then when the object is to begin searching, it will pass itself to
this method and make itself the root. Then I avoid using static object!
กก
#include <iostream>
using namespace std;
const int MaxSonCount =8;
const int MaxLevel = 20;
const int MaxOptionCount = 10;
enum BitName
{Zero, One, Two};
char* BitString[3] = {"0", "1", "2"};
int bitOption[3] = {Zero, One, Two};
class BFS
{
protected:
static BFS *root;
static int level;
static int optionArray[MaxOptionCount];
static int optionCount;
static int maxLevel;
int depth;
BFS* parent;
BFS* sonArray[MaxSonCount];
int data;
int sonCount;
int sonIndex;
void addSon(int sonData);
BFS* findBrother();
BFS* findUncle();
bool hasBrother();
BFS* nextBrother();
BFS* diving();
void initialize(BFS* now);
bool touchDown();
bool canDive();
bool generate();
void traverse();
void setMaxLevel(int max) { maxLevel = max;}
void assignString(char** nameString);
virtual BFS* createSon();
virtual bool lastChance();
virtual void doGenerate();
virtual bool validateOption(int sonData);
virtual void onVisit(int& counter);
public:
int getData(){return data;}
BFS* getParent() { return parent;}
void setOptionArray(int* array, int arraySize);
void beginCount(int max);
};
int BFS::level = 0;
BFS* BFS::root;
int BFS::optionArray[MaxOptionCount] = {0};
int BFS::optionCount = 0;
int BFS::maxLevel = 0;
class Isomorphic: public BFS
{
protected:
BFS* createSon();
bool validateOption(int sonData);
};
int main()
{
Isomorphic R;
R.setOptionArray(bitOption, 3);
R.beginCount(5);
return 0;
}
BFS* Isomorphic::createSon()
{
BFS* ptr = new Isomorphic;
return ptr;
}
bool Isomorphic::validateOption(int sonData)
{
BFS* ptr;
bool amZero = false;
if (depth>=maxLevel-2)
{
if (sonData==0&&getData() ==0)
{
return true;
}
else
{
//it has the potential
if (sonData==0)
{
return true;
}
//the following is to find consecutive 0's
ptr = this;
amZero = false; //initialize
while (ptr!=NULL)
{
if (ptr->getParent()==NULL)
{
break;
}
if (amZero) //
{
if (ptr->getData()==0)//means the son is 0
{
return true;
}
else
{
amZero = false; //reset
}
}
else
{
if (ptr->getData() ==0) //give you a chance to replay the game
{
amZero = true;
}
}
ptr = ptr->getParent();//next generation
}
return false; //ended with no consecutive 0's
}
}
return true;//if not the last last chance, why matters?
}
void BFS::setOptionArray(int *array, int arraySize)
{
optionCount = arraySize;
for (int i=0; i< optionCount; i++)
{
optionArray[i] = array[i];
}
}
BFS* BFS::createSon()
{
BFS* ptr = new BFS;
return ptr;
}
void BFS::assignString(char** nameString)
{
int temp[MaxLevel] = {0};
BFS* ptr = this;
while (ptr->parent!=NULL)
{
temp[ptr->depth-1] = ptr->data;
ptr = ptr->parent;
}
cout<<" The route is:";
for (int i=0; i<depth; i++)//depth is one more than level!!!!!!
{
cout<<nameString[temp[i]]<<", ";
}
cout<<endl;
}
void BFS::onVisit(int& counter)
{
cout<<"now it is:"<<++counter;
assignString(BitString);
}
bool BFS::validateOption(int sonData)
{
if (sonData==Zero)
{
if (parent!=NULL)
{
if (data==Zero)
{
return false;
}
}
}
return true;
}
void BFS::doGenerate()
{
for (int i=0; i<optionCount; i++)
{
if (validateOption(optionArray[i]))
{
addSon(optionArray[i]);
}
}
}
bool BFS::lastChance()
{
return level==maxLevel-1;
}
void BFS::traverse()
{
int counter=0;
BFS* ptr= root;
while (ptr!=NULL)
{
while(ptr->canDive())
{
ptr= ptr->sonArray[0];
}
ptr->onVisit(counter);
if (ptr->hasBrother())
{
ptr= ptr->nextBrother();
}
else
{
ptr=ptr->findUncle();
}
}
cout<<"The total number is :"<<counter<<endl;
}
void BFS::beginCount(int max)
{
setMaxLevel(max);
initialize(this);
while (generate())
{
if (!lastChance()) //true to keep go on
{
level++;
}
else
{
break;
}
}
traverse();
}
bool BFS::generate()
{
BFS* ptr= this;
ptr = root->diving();
if (ptr==NULL)
{
return false;
}
while (ptr!=NULL)
{
ptr->doGenerate();
ptr = ptr->findBrother();
}
return true;
}
bool BFS::touchDown()
{
return depth ==level;
}
bool BFS::canDive()
{
return sonCount>0;
}
void BFS::initialize(BFS* now)
{
root = now;
root->depth = 0;
root->sonCount = 0;
root->sonIndex = -1;
root->parent = NULL;
root->data = 0;
level = 0;
}
//NULL only when there is no more brother
BFS* BFS::diving()
{
BFS* ptr = this;
while (!ptr->touchDown())
{
if (ptr->canDive())
{
ptr = ptr->sonArray[0];
}
else
{
if (ptr->hasBrother())
{
ptr = ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
}
}
if (ptr==NULL)
{
break; //no more way to dive
}
}
return ptr;
}
bool BFS::hasBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
BFS* BFS::nextBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return parent->sonArray[sonIndex+1]; //next little brother
}
}
return NULL;
}
BFS* BFS::findUncle()
{
BFS* ptr= this;
while (!(ptr->hasBrother()))
{
ptr = ptr->parent;
if (ptr==NULL)
{
return NULL;
}
}
return ptr->nextBrother();
}
BFS* BFS::findBrother()
{
BFS* ptr = this;
if (ptr->hasBrother())
{
return ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
if (ptr==NULL)
{
return NULL;
}
else
{
return ptr->diving();
}
}
}
void BFS::addSon(int sonData)
{
BFS* ptr;
if (sonCount+1<MaxSonCount)
{
ptr = createSon();
ptr->data = sonData;
ptr->sonCount = 0;
ptr->parent = this;
ptr->depth = level+1;
sonArray[sonCount] = ptr;
ptr->sonIndex = sonCount;
sonCount++;
}
else
{
cout<<"Exceed max of sons!";
}
}
The following is result of program: (the result is too much even with reduced searching levels)
now it is:1 The route is:0, 0, 0, 0, 0, now it is:2 The route is:0, 0, 0, 0, 1, now it is:3 The route is:0, 0, 0, 0, 2, now it is:4 The route is:0, 0, 0, 1, 0, now it is:5 The route is:0, 0, 0, 1, 1, now it is:6 The route is:0, 0, 0, 1, 2, now it is:7 The route is:0, 0, 0, 2, 0, now it is:8 The route is:0, 0, 0, 2, 1, now it is:9 The route is:0, 0, 0, 2, 2, now it is:10 The route is:0, 0, 1, 0, 0, now it is:11 The route is:0, 0, 1, 0, 1, now it is:12 The route is:0, 0, 1, 0, 2, now it is:13 The route is:0, 0, 1, 1, 0, now it is:14 The route is:0, 0, 1, 1, 1, now it is:15 The route is:0, 0, 1, 1, 2, now it is:16 The route is:0, 0, 1, 2, 0, now it is:17 The route is:0, 0, 1, 2, 1, now it is:18 The route is:0, 0, 1, 2, 2, now it is:19 The route is:0, 0, 2, 0, 0, now it is:20 The route is:0, 0, 2, 0, 1, now it is:21 The route is:0, 0, 2, 0, 2, now it is:22 The route is:0, 0, 2, 1, 0, now it is:23 The route is:0, 0, 2, 1, 1, now it is:24 The route is:0, 0, 2, 1, 2, now it is:25 The route is:0, 0, 2, 2, 0, now it is:26 The route is:0, 0, 2, 2, 1, now it is:27 The route is:0, 0, 2, 2, 2, now it is:28 The route is:0, 1, 0, 0, 0, now it is:29 The route is:0, 1, 0, 0, 1, now it is:30 The route is:0, 1, 0, 0, 2, now it is:31 The route is:0, 1, 1, 0, 0, now it is:32 The route is:0, 1, 2, 0, 0, now it is:33 The route is:0, 2, 0, 0, 0, now it is:34 The route is:0, 2, 0, 0, 1, now it is:35 The route is:0, 2, 0, 0, 2, now it is:36 The route is:0, 2, 1, 0, 0, now it is:37 The route is:0, 2, 2, 0, 0, now it is:38 The route is:1, 0, 0, 0, 0, now it is:39 The route is:1, 0, 0, 0, 1, now it is:40 The route is:1, 0, 0, 0, 2, now it is:41 The route is:1, 0, 0, 1, 0, now it is:42 The route is:1, 0, 0, 1, 1, now it is:43 The route is:1, 0, 0, 1, 2, now it is:44 The route is:1, 0, 0, 2, 0, now it is:45 The route is:1, 0, 0, 2, 1, now it is:46 The route is:1, 0, 0, 2, 2, now it is:47 The route is:1, 0, 1, 0, 0, now it is:48 The route is:1, 0, 2, 0, 0, now it is:49 The route is:1, 1, 0, 0, 0, now it is:50 The route is:1, 1, 0, 0, 1, now it is:51 The route is:1, 1, 0, 0, 2, now it is:52 The route is:1, 1, 1, 0, 0, now it is:53 The route is:1, 1, 2, 0, 0, now it is:54 The route is:1, 2, 0, 0, 0, now it is:55 The route is:1, 2, 0, 0, 1, now it is:56 The route is:1, 2, 0, 0, 2, now it is:57 The route is:1, 2, 1, 0, 0, now it is:58 The route is:1, 2, 2, 0, 0, now it is:59 The route is:2, 0, 0, 0, 0, now it is:60 The route is:2, 0, 0, 0, 1, now it is:61 The route is:2, 0, 0, 0, 2, now it is:62 The route is:2, 0, 0, 1, 0, now it is:63 The route is:2, 0, 0, 1, 1, now it is:64 The route is:2, 0, 0, 1, 2, now it is:65 The route is:2, 0, 0, 2, 0, now it is:66 The route is:2, 0, 0, 2, 1, now it is:67 The route is:2, 0, 0, 2, 2, now it is:68 The route is:2, 0, 1, 0, 0, now it is:69 The route is:2, 0, 2, 0, 0, now it is:70 The route is:2, 1, 0, 0, 0, now it is:71 The route is:2, 1, 0, 0, 1, now it is:72 The route is:2, 1, 0, 0, 2, now it is:73 The route is:2, 1, 1, 0, 0, now it is:74 The route is:2, 1, 2, 0, 0, now it is:75 The route is:2, 2, 0, 0, 0, now it is:76 The route is:2, 2, 0, 0, 1, now it is:77 The route is:2, 2, 0, 0, 2, now it is:78 The route is:2, 2, 1, 0, 0, now it is:79 The route is:2, 2, 2, 0, 0, The total number is :79 Press any key to continue
กก
กก