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.
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?
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.
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
กก
กก