Population

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.

    B.The problem

    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".)

C.The idea of program

    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().

    D.The major functions

    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

    กก

กก