Population

Space Walker--Application of BFS

    A.First Edition

    This is actually an application of my BFS class, or you can call it second edition of counting model, whatever.

    The base framework are exactly same as Counting problem. Originally I planned to let derived class to implement

    some "protected virtual" method to do their own job. But unfortunately the "static" member root destroy the

    ability of multimorphiness of C++. I have to copy the code and rewrite those virtual function without inheriting.

    B.The problem

    How many ways are there to trave in xyzw space from the origin (0,0,0,0) to the point (4,3,5,4) by taking steps

    one unit in the positive x, positive y, positive z, or positive w direction?

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.

    As I mentioned I cannot inheritate from CountTree, I have to rewrite it. And the problem is 16-level BFS with each

    level at most 4 options. I found out my laptop cannot go beyond 11 level which is roughly 4,194,304 nodes alone.

    So, I simplify the question a bit to point (1,3,2,4) which is 10-level question. And the output file is 420k with

    12600 solutions.

    D.The major functions

    1. virtual bool validateOption(int sonData);

    This is the place where user-defined methods are implemented to determine if the data (integer)	will be verified

    to be able to be added.

    2. virtual void doGenerate();

    This is user-defined way that cases are generated. Method validateOptions will be combined with it to determine

    which cases should be added.

    3. void CountTree::traverse();

    This method allows you to traverse all leaf points.

    4. virtual void onVisit();

    This is user-defined method like outputing all outcomes.

    กก

    #include <iostream>

    using namespace std;

    const int MaxSonCount =8;

    enum AxisName
    {X, Y, Z, W};

    int limit[4] = {1,3,2,4};

    char* directionString[4] = {"X", "Y", "Z", "W"};

    int axis[4] = {X,Y,Z,W};

    class CountTree
    {
    private:
    	static CountTree root;
    	static int level;
    	int depth;
    	CountTree* parent;
    	CountTree* sonArray[MaxSonCount];
    	int data;
    	int sonCount;
    	int sonIndex;
    	void addSon(int sonData);
    	CountTree* findBrother();
    	CountTree* findUncle();
    	bool hasBrother();
    	CountTree* nextBrother();
    	CountTree* diving();
    	void initialize();
    	bool touchDown();
    	bool canDive();
    	bool generate();
    	void traverse();
    protected:
    	virtual bool lastChance();
    	virtual void doGenerate();
    	virtual bool validateOption(int sonData);
    	virtual void onVisit();
    	virtual bool lastlast();
    public:
    	void beginCount();
    };

    int CountTree::level = 0;
    CountTree CountTree::root;

    int main()
    {
    	CountTree R;
    	R.beginCount();

    	return 0;
    }

    bool CountTree::lastlast()
    {
    	return level==4;
    }

    void CountTree::onVisit()
    {
    	int temp[16] = {0};
    	CountTree* 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++)
    	{
    		cout<<directionString[temp[i]]<<", ";
    	}
    	cout<<endl;
    }

    bool CountTree::validateOption(int sonData)
    {
    	int counter[4]={0}; //count all axis advances
    	CountTree* ptr= this;

    	while (ptr->parent!=NULL)
    	{
    		counter[ptr->data]++; //data is axis
    		ptr = ptr->parent;
    	}

    	return counter[sonData]<limit[sonData];
    }

    void CountTree::doGenerate()
    {
    	for (int i=0; i<4; i++)
    	{
    		if (validateOption(axis[i]))
    		{
    			addSon(axis[i]);
    		}
    	}
    }

    bool CountTree::lastChance()
    {
    	return level==9;
    }

    void CountTree::traverse()
    {
    	int counter=0;
    	CountTree* ptr= &root;
    	while (ptr!=NULL)
    	{
    		while(ptr->canDive())
    		{
    			ptr= ptr->sonArray[0];
    		}
    		cout<<"now it is:"<<++counter;
    		ptr->onVisit();

    		if (ptr->hasBrother())
    		{
    			ptr= ptr->nextBrother();
    		}
    		else
    		{
    			ptr=ptr->findUncle();
    		}
    	}
    	cout<<"The total number is :"<<counter<<endl;
    }

    void CountTree::beginCount()
    {
    	initialize();
    	while (generate())
    	{
    		if (!lastChance()) //true to keep go on
    		{
    			level++;
    			cout<<"Now is level:"<<level<<endl;
    		}
    		else
    		{
    			break;
    		}
    	}
    	traverse();
    }

    bool CountTree::generate()
    {
    	CountTree* ptr= this;
    	ptr = root.diving();
    	if (ptr==NULL)
    	{
    		return false;
    	}
    	while (ptr!=NULL)
    	{
    		ptr->doGenerate();
    		ptr = ptr->findBrother();
    	}

    	return true;
    }

    bool CountTree::touchDown()
    {
    	return depth ==level;
    }

    bool CountTree::canDive()
    {
    	return sonCount>0;
    }

    void CountTree::initialize()
    {
    	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
    CountTree* CountTree::diving()
    {
    	CountTree* 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 CountTree::hasBrother()
    {
    	if (parent!=NULL)
    	{
    		if (parent->sonCount > sonIndex+1)//has little brother
    		{
    			return true;
    		}
    	}
    	return false;
    }

    CountTree* CountTree::nextBrother()
    {
    	if (parent!=NULL)
    	{
    		if (parent->sonCount > sonIndex+1)//has little brother
    		{
    			return parent->sonArray[sonIndex+1]; //next little brother
    		}
    	}
    	return NULL;
    }

    CountTree* CountTree::findUncle()
    {
    	CountTree* ptr= this;
    	while (!(ptr->hasBrother()))
    	{
    		ptr = ptr->parent;
    		if (ptr==NULL)
    		{
    			return NULL;
    		}
    	}
    	return ptr->nextBrother();

    }

    CountTree* CountTree::findBrother()
    {
    	CountTree* ptr = this;
    	if (ptr->hasBrother())
    	{
    		return ptr->nextBrother();
    	}
    	else
    	{
    		ptr = ptr->findUncle();
    		if (ptr==NULL)
    		{
    			return NULL;
    		}
    		else
    		{
    			return ptr->diving();
    		}
    	}
    }

    void CountTree::addSon(int sonData)
    {
    	if (sonCount+1<MaxSonCount)
    	{
    		CountTree* ptr = new CountTree;
    		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:12567The route is:W, W, W, W, Y, Y, Z, Z, X, Y,
    now it is:12568The route is:W, W, W, W, Y, Y, Z, Z, Y, X,
    now it is:12569The route is:W, W, W, W, Y, Z, X, Y, Y, Z,
    now it is:12570The route is:W, W, W, W, Y, Z, X, Y, Z, Y,
    now it is:12571The route is:W, W, W, W, Y, Z, X, Z, Y, Y,
    now it is:12572The route is:W, W, W, W, Y, Z, Y, X, Y, Z,
    now it is:12573The route is:W, W, W, W, Y, Z, Y, X, Z, Y,
    now it is:12574The route is:W, W, W, W, Y, Z, Y, Y, X, Z,
    now it is:12575The route is:W, W, W, W, Y, Z, Y, Y, Z, X,
    now it is:12576The route is:W, W, W, W, Y, Z, Y, Z, X, Y,
    now it is:12577The route is:W, W, W, W, Y, Z, Y, Z, Y, X,
    now it is:12578The route is:W, W, W, W, Y, Z, Z, X, Y, Y,
    now it is:12579The route is:W, W, W, W, Y, Z, Z, Y, X, Y,
    now it is:12580The route is:W, W, W, W, Y, Z, Z, Y, Y, X,
    now it is:12581The route is:W, W, W, W, Z, X, Y, Y, Y, Z,
    now it is:12582The route is:W, W, W, W, Z, X, Y, Y, Z, Y,
    now it is:12583The route is:W, W, W, W, Z, X, Y, Z, Y, Y,
    now it is:12584The route is:W, W, W, W, Z, X, Z, Y, Y, Y,
    now it is:12585The route is:W, W, W, W, Z, Y, X, Y, Y, Z,
    now it is:12586The route is:W, W, W, W, Z, Y, X, Y, Z, Y,
    now it is:12587The route is:W, W, W, W, Z, Y, X, Z, Y, Y,
    now it is:12588The route is:W, W, W, W, Z, Y, Y, X, Y, Z,
    now it is:12589The route is:W, W, W, W, Z, Y, Y, X, Z, Y,
    now it is:12590The route is:W, W, W, W, Z, Y, Y, Y, X, Z,
    now it is:12591The route is:W, W, W, W, Z, Y, Y, Y, Z, X,
    now it is:12592The route is:W, W, W, W, Z, Y, Y, Z, X, Y,
    now it is:12593The route is:W, W, W, W, Z, Y, Y, Z, Y, X,
    now it is:12594The route is:W, W, W, W, Z, Y, Z, X, Y, Y,
    now it is:12595The route is:W, W, W, W, Z, Y, Z, Y, X, Y,
    now it is:12596The route is:W, W, W, W, Z, Y, Z, Y, Y, X,
    now it is:12597The route is:W, W, W, W, Z, Z, X, Y, Y, Y,
    now it is:12598The route is:W, W, W, W, Z, Z, Y, X, Y, Y,
    now it is:12599The route is:W, W, W, W, Z, Z, Y, Y, X, Y,
    now it is:12600The route is:W, W, W, W, Z, Z, Y, Y, Y, X,
    The total number is :12600

กก

กก