Population

DFS---Standardized

    A.Second Edition

    This is second edition of my DFS base class. Like BFS, I standardized all virtual method and correct a couple of

    small mistakes.

    B.The problem

    How many ways are there to travel in xyzw space from the origin (0,0,0,0) to the point (3,2,3,1) 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 depth-first-search

    is one of the simplest way to do it.

    As DFS uses very small memory, I don't need to reduce the size of problem, but the program wrote into my disk with

    a file size of more than 800M until my disk runs out of free space. Then I change the program not to output all

    outcomes, instead only the total number of solutions. However, it runs more than one hour and still there is no

    result!

    There are several significant changes in new Standardized DFS class:

    1. root is no longer a static object, so it is possible to be inherited by overriding virtual function "createSon".

    2. MaxLevel is only a bottom line for DFS to touch down. A bug is corrected so that it will give correct result

    even searching does not touch down.

    3. evaluate method must be implemented by user to justify if result is what he is looking for.

    4. validateOption remains same to be necessary to be implemented by user.

    5. beginCount need one more parameter---nameStr, a char**. So that display method is standardize and no more

    attention is needed. User simply passes the user-defined string array (char**) by second parameter in beginCount.

    6. A member counter solutionCounter is used to count the number of solutions.

    7. setOption still needs to be called before beginCount() to set up the options array.

    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. bool DFS::doGenerate()

    I made a small change in this function: a touchDown check is preceded to all option-check, because this is major

    difference with BFS. User prefers to set up the maximum searching levels.

    3. void DFS::onLeave()

    This method allows you to do specific job when you visit all leaf points which is a solution such as delete node.

    4. DFS* DFS::generate()

    This function is also modified as "evaluate" check becomes the only judgement for return. This makes it possible

    that even searching does not reach maximum searching level, correct results still can be got as long as it justifies

    "evaluate" check.

    #include <iostream>

    using namespace std;

    const int MaxSonCount=8;

    const int MaxLevel =20;

    const int MaxOptions = 10;

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

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

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

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

    class DFS
    {
    private:
    	static DFS* root;
    	static bool findAll;
    	static int level;
    	static int optionArray[MaxOptions];
    	static int optionCount;
    	static int maxLevel;
    	static char** nameString;
    	static int solutionCount;
    	int depth;
    	DFS* parent;
    	DFS* sonArray[MaxSonCount];
    	int data;
    	int sonCount;
    	int sonIndex;
    	void addSon(int sonData);
    	DFS* findBrother();
    	DFS* findUncle();
    	bool hasBrother();
    	DFS* nextBrother();
    	void initialize(DFS* now);
    	bool touchDown();
    	DFS* generate();
    	void setMaxLevel(int max) { maxLevel = max;}
    	bool doGenerate();
    	void setNameStr(char** str){nameString = str;}
    protected:
    	virtual DFS* createSon();
    	virtual bool validateOption(int sonData);
    	virtual void onLeave();
    	virtual bool evaluate();
    	virtual void collectResult();
    public:
    	int getSolutionCount(){ return solutionCount;}
    	void setOptions(int* array, int size);
    	void beginCount(int max, char** str, bool findall=false);
    };

    bool DFS::findAll = false;
    int DFS::maxLevel = 0;
    int DFS::optionCount = 0;
    int DFS::optionArray[MaxOptions] = {0};
    int DFS::level = 0;
    DFS* DFS::root = NULL;
    char** DFS::nameString=NULL;
    int DFS::solutionCount = 0;

    int main()
    {
    	DFS R;
    	R.setOptions(axis, 4);
    	R.beginCount(16, directionString, true);
    	cout<<"Total number is "<<R.getSolutionCount()<<endl;

    	return 0;
    }

    //I don't know what extra work to be for the time being
    bool DFS::evaluate()
    {
    	return depth == 9;
    }

    bool DFS::touchDown()
    {
    	return depth==maxLevel;
    }

    void DFS::onLeave()
    {
    	DFS* ptr =this;
    	delete ptr;
    }

    //a stack
    void DFS::collectResult()
    {
    	int temp[MaxLevel] = {0};
    	DFS* 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<<nameString[temp[i]]<<", ";
    	}
    	cout<<"It is number:"<<solutionCount++;
    	cout<<endl;
    }

    void DFS::setOptions(int *array, int size)
    {
    	optionCount = size;
    	for (int i=0; i<size; i++)
    	{
    		optionArray[i] = *(array+i);
    	}
    }

    bool DFS::doGenerate()
    {
    	bool result = false;
    	if (touchDown())
    	{
    		return false;
    	}

    	for (int i=0; i< optionCount; i++)
    	{
    		if (validateOption(optionArray[i]))
    		{
    			addSon(optionArray[i]);
    			result = true;
    		}
    	}
    	if (result)
    	{
    		level++;
    	}
    	return result;
    }

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

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

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

    DFS* DFS::findBrother()
    {
    	DFS* ptr= this;
    	DFS* dummy=ptr;
    	while (!(ptr->hasBrother()))
    	{
    		dummy = ptr; //keep the clue
    		ptr = ptr->parent;
    		level--;   //???
    		if (dummy!=root)
    		{
    			dummy->onLeave(); //clear
    		}
    		if (ptr==NULL)
    		{
    			return NULL;
    		}
    	}
    	dummy = ptr;  //keep clue
    	ptr = ptr->nextBrother();
    	dummy->onLeave(); //clear
    	return ptr;
    }

    void DFS::beginCount(int max, char** str, bool findall)
    {
    	setNameStr(str);
    	DFS* ptr = this;
    	setMaxLevel(max);
    	findAll = findall; //setup if want all result
    	initialize(this);
    	while (true)
    	{
    		ptr = ptr->generate();
    		if (ptr==NULL)
    		{
    			if (solutionCount==0)
    			{
    				cout<<"No solution!";
    			}
    			break;
    		}
    		if (ptr->evaluate())
    		{
    			ptr->collectResult();
    			if (!findAll)
    			{
    				break;
    			}
    		}
    		ptr = ptr->findBrother();
    		if (ptr==NULL)
    		{

    			if (solutionCount==0)
    			{
    				cout<<"No solution!";
    			}
    			break;
    		}
    	}
    }

    DFS* DFS::generate()
    {
    	DFS* ptr= this;

    	while (!ptr->evaluate())
    	{
    		if (!ptr->doGenerate())
    		{
    			ptr=ptr->findBrother();
    			if (ptr==NULL)
    			{
    				break;
    			}
    		}
    		else
    		{
    			ptr = ptr->sonArray[0];
    		}
    	}

    	return ptr;
    }

    DFS* DFS::createSon()
    {
    	DFS* ptr = new DFS;
    	return ptr;
    }

    void DFS::addSon(int sonData)
    {
    	if (sonCount+1<MaxSonCount)
    	{
    		DFS* ptr = createSon();
    		ptr->data = sonData;
    		ptr->sonCount = 0;
    		ptr->parent = this;
    		ptr->depth = depth+1;
    		sonArray[sonCount] = ptr;
    		ptr->sonIndex = sonCount;
    		sonCount++;
    	}
    	else
    	{
    		cout<<"Exceed max of sons!";
    	}
    }

    void DFS::initialize(DFS* now)
    {
    	root = now;
    	root->depth = 0;
    	root->sonCount = 0;
    	root->sonIndex = -1;
    	root->parent = NULL;
    	root->data = 0;
    	level = 0;
    }

    bool DFS::hasBrother()
    {
    	if (parent!=NULL)
    	{
    		if (parent->sonCount > sonIndex+1)//has little brother
    		{
    			return true;
    		}
    	}
    	return false;
    }

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

    The result is 5040

กก