Population

String Searching

    A. First Edition

    This is second edition of code competition problem 1 which I try to use my DFSArray class to solve. So, it is

    also an improved edition of my DFS class. (How many editions have been made for DFS? I don't remember.)

    B.The problem

Code Competition Problem 1.
””
””
C.The idea of program

    It is the same old trick--To setup a series of options and at each node test these options. However, I thought

    I run into unsolvable obstacles at first. You see, "abcdab", for example, there are two "ab" at different postion.

    Then it means for option "ab", there exists two result! But my "validateOptions" function only return true or false.

    How can I recognize there are actually TWO different results derived from same option---"ab"? It seems a contradictive

    to TURING Machine---for one input there should be one definite output. However, there is a way to solve it! Because

    there is different state inside class. See the pointer is at different positions of string, so, it means a different

    states can be tracked. I add an internal data member--state to indicate the position of pointer in string. When

    the positions are different, we must traverse all choices again.

    D.The major functions

    1. void StrSearching::trackString()

    This is quite like the old "backTrack" function and save "curString" instead of "choices" in an array.

    2. bool StrSearching::validateOption(int sonData)

    First you should make sure there is an matching choice, then try to make sure there is no repeating result in

    upper nodes. (Note that different choices may lead to same result, but we only care about results instead of

    "choices" here.£©

    £³£®void StrSearching::readFile(const char* fileName)

    This function read rules into a 2-dimension array, and initial string and target string also at end of this array.

    4. bool DFS::beginCount(int max, bool findall)

    This function was changed a little bit to fix the logic loophole: I should always evaluate first for any node

    before trying to generate new nodes from it. And whenever a node touch down, it should return to try next node.

    5. char* StrSearching::replaceStr(char* source, char* target, int start, int size)

    A utility function to insert a target string into source with starting position at start and replaced string length

    is size. Do you understand? Surely it is easy to read code.

    E.Further improvement

    1. The change in this version of DFS is considered to be a rather big one. Should I standardize it as lib? I doubt it.

    ””

    //file DFS.h

    #ifndef DFS_H
    #define DFS_H
    #include <iostream>

    using namespace std;

    const int MaxSonCount=8;

    const int MaxLevel = 120;

    const int MaxOptions = 16;

    const int MaxNodeCount = 300;

    class DFS
    {
    private:
    	void initialize(DFS* now);
    	static bool initialized;
    	static DFS* nodeList[MaxNodeCount];
    	static bool findAll;
    	static int optionArray[MaxOptions];
    	static int optionCount;
    	static char** nameString;
    	static int solutionCount;
    	static int maxLevel;
    	void addSon(int sonData);
    	bool touchDown();
    	void setMaxLevel(int max) { maxLevel = max;}
    	DFS* upDate();
    	static int domino;
    	bool hasBrother();
    	DFS* nextBrother();
    	bool generate();
    	DFS* findNext();
    	void putNode(int theIndex) { nodeList[theIndex] = this;}
    protected:
    	int state;
    	int stateCount;
    	int parent;
    	int sonCount;
    	int sonIndex;
    	int son;
    	int depth;
    	int index;//index in nodeList
    	int data;
    	static int trackRecord[MaxLevel];
    	void backTrack();
    	DFS* getNode(int theIndex){return nodeList[theIndex];}
    	DFS* getParent(){return getNode(parent);}
    	bool hasParent(){return parent!=-1;}
    	virtual void setStateCount();
    	virtual void onAfterAdded();
    	virtual void onGenerate();
    	virtual void onBeginSearch();
    	virtual DFS* createSon() = 0;
    	virtual bool validateOption(int sonData) =0;	//made it pure virtual
    	virtual void onLeave();
    	virtual bool evaluate() = 0;
    	virtual void collectResult();
    public:
    	int getSolutionCount(){ return solutionCount;}
    	void setOptions(int* array, int size);
    	void setNameStr(char** str){nameString = str;}
    	bool beginCount(int max, bool findall=false);
    	virtual ~DFS();//virtual destructor
    };

    #endif

    ””

    //file DFS.cpp

    #include <iostream>
    #include "DFS.h"

    using namespace std;

    int DFS::domino = 0;
    bool DFS::findAll = false;
    bool DFS::initialized = false;
    int DFS::maxLevel = 0;
    int DFS::optionArray[MaxOptions] = {0};
    char** DFS::nameString=NULL;
    int DFS::solutionCount = 0;
    int DFS::optionCount = 0;
    DFS* DFS::nodeList[MaxNodeCount] = {NULL};
    int DFS::trackRecord[MaxLevel]= {0};

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

    void DFS::onBeginSearch()
    {
    	//programmer may need do some initializing job here!
    }

    //user can synchronize sonNode and fatherNode
    void DFS::onAfterAdded()
    {
    	//programmer may need do something for his own purpose
    }

    void DFS::onLeave()
    {
    	DFS* ptr =this;
    	if (ptr->hasParent())
    	{
    		DFS* father = ptr->getParent();
    		domino -= father->sonCount;
    		father->sonCount = 0;
    		father->son = -1;
    	}
    }

    void DFS::backTrack()
    {
    	DFS* ptr = this;

    	while (ptr->hasParent())
    	{
    		trackRecord[ptr->depth-1] = ptr->data;
    		ptr = ptr->getParent();
    	}
    }

    //a stack
    void DFS::collectResult()
    {
    	backTrack();
    	cout<<"The route is:\n";
    	for (int i=0; i<depth; i++)
    	{
    		cout<<nameString[trackRecord[i]]<<", ";
    	}
    	cout<<"\nIt 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);
    	}
    }

    DFS::~DFS()
    {
    	if (initialized)
    	{
    		for (int i=1; i<MaxNodeCount; i++)//the i=0 is root which is not dynamic allocated!
    		{
    			delete nodeList[i];
    		}
    		domino =0;
    		initialized=false;
    	}
    }

    void DFS::onGenerate()
    {
    	//programmer may need to initialize at this stage
    }

    bool DFS::beginCount(int max, bool findall)
    {
    	DFS* ptr = this;
    	setMaxLevel(max);
    	findAll = findall; //setup if want all result
    	initialize(this);
    	onBeginSearch();//this is done from root!

    	while (ptr!=NULL)
    	{
    		if (ptr->evaluate())
    		{
    			ptr->collectResult();
    			if (!findAll)
    			{
    				break;
    			}
    			else
    			{
    				ptr = ptr->findNext();

    			}
    		}
    		if (ptr->touchDown())//for a new son
    		{
    			ptr=ptr->findNext();

    		}
    		//programmer may need to initialize at this stage
    		ptr->onGenerate();
    		if (ptr->generate())
    		{
    			ptr = ptr->upDate();//move to first son
    		}
    		else
    		{
    			ptr = ptr->findNext();//for a new son

    		}
    	}
    	if (solutionCount==0)
    	{
    		cout<<"no solution!";
    		return false;
    	}
    	else
    	{
    		cout<<"Total solution is "<<solutionCount<<endl;
    		return true;
    	}

    }

    DFS* DFS::findNext()
    {
    	DFS* ptr = this;
    	DFS* dummy;
    	while (ptr!=NULL)
    	{
    		if (ptr->hasBrother())
    		{
    			ptr = getNode(ptr->index+1);//next brother

    			return ptr;
    		}
    		else
    		{
    			if (ptr->hasParent())
    			{
    				dummy = ptr;
    				ptr = ptr->getParent(); //if
    				dummy->onLeave(); //only clear when go up one level
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    	return NULL;
    }
    void DFS::setStateCount()
    {
    	//user should specify here what kind of internal state number it is.
    }

    bool DFS::generate()
    {
    	bool result = false;

    	if (touchDown())
    	{
    		return false;
    	}
    	stateCount =1;
    	setStateCount();

    	for (state =0; state<stateCount; state++)
    	{
    		//this is preorder and I don't bother to
    		//give choices for midorder or postorder
    		for (int i=0; i< optionCount; i++)
    		{
    			if (validateOption(optionArray[i]))
    			{
    				addSon(optionArray[i]);
    				result = true;
    			}
    		}
    	}
    	return result;
    }

    DFS* DFS::upDate()
    {
    	//return first son
    	return getNode(son);
    }

    void DFS::addSon(int sonData)
    {
    	if (sonCount+1<MaxSonCount)
    	{
    		if (domino==MaxNodeCount)
    		{
    			cout<<"Exceeds limit of node list"<<endl;
    			return;
    		}
    		//DFS* ptr = createSon();
    		DFS* ptr = nodeList[domino];
    		ptr->index = domino;//
    		//ptr->putNode(domino);

    		if (sonCount==0)//if it is the first son
    		{
    			son = domino;//first son
    		}
    		domino++;
    		ptr->state = state;
    		ptr->stateCount = stateCount;
    		ptr->data = sonData;
    		ptr->sonCount = 0;
    		ptr->son = -1;//temporarily
    		ptr->parent = index;
    		ptr->depth = depth+1;
    		ptr->sonIndex = sonCount;
    		sonCount++;
    		ptr->onAfterAdded();
    	}
    	else
    	{
    		cout<<"Exceed max of sons!";
    	}
    }

    void DFS::initialize(DFS* now)
    {
    	now->index =0;
    	now->depth = 0;
    	now->sonCount = 0;
    	now->sonIndex = -1;
    	now->parent = -1;
    	now->data = 0;
    	now->son = -1;
    	now->putNode(0); //put in list

    	if (!initialized)
    	{
    		for (int i=1; i<MaxNodeCount; i++)
    		{
    			nodeList[i] = createSon();
    		}
    		initialized = true;
    	}
    	domino++;
    }

    bool DFS::hasBrother()
    {
    	if (hasParent())
    	{
    		if (getParent()->sonCount > sonIndex+1)//has little brother
    		{
    			return true;
    		}
    	}
    	return false;
    }

    //file StringSearch.cpp

    #include <iostream>
    #include "DFS.h"
    #include <fstream>

    using namespace std;

    const int MaxRuleNum=10;

    class StrSearching: public DFS
    {
    private:
    	static int ruleNum;
    	static char* ruleString[2][MaxRuleNum];
    	static char* records[MaxLevel];
    	char* createString(const char* input);
    	char* curString;
    	static int options[MaxRuleNum];
    	char* replaceStr(char* source, char* target, int start, int size);
    	void trackString();

    protected:
    	virtual bool validateOption(int sonData);
    	virtual DFS* createSon();
    	virtual void setStateCount();
    	virtual bool evaluate();
    	virtual void collectResult();
    	virtual void onBeginSearch();
    	virtual void onAfterAdded();
    	virtual void onLeave();

    public:
    	void readFile(const char* fileName);
    	virtual ~StrSearching();
    };

    char* StrSearching::records[MaxLevel];
    int StrSearching::ruleNum = 0;
    char* StrSearching::ruleString[2][MaxRuleNum];
    int StrSearching::options[MaxRuleNum]={0};

    int main()
    {
    	StrSearching S;
    	S.readFile("c:\\strSearch.txt");
    	S.beginCount(20, true);
    	return 0;
    }

    void StrSearching::trackString()
    {
    	StrSearching* ptr = this;
    	while(ptr!=NULL)
    	{
    		records[ptr->depth] = ptr->curString;
    		if (ptr->hasParent())
    		{
    			ptr = (StrSearching*)ptr->getParent();
    		}
    		else
    		{
    			break;
    		}
    	}
    }

    StrSearching::~StrSearching()
    {
    //	delete []curString;
    }

    char* StrSearching::replaceStr(char* source, char* target, int start, int size)
    {
    	int targetSize = strlen(target);
    	int newSize = strlen(source) + targetSize -size;
    	char* result = new char[newSize+1];
    	for (int i=0; i<=newSize; i++)//copy null
    	{
    		if (i<start)
    		{
    			result[i]= source[i];
    		}
    		else
    		{
    			if (i<start+targetSize)
    			{
    				result[i] = target[i-start];
    			}
    			else
    			{
    				result[i] = source[i-targetSize+size];
    			}
    		}
    	}
    	return result;
    }

    void StrSearching::onLeave()
    {
    	StrSearching* ptr = (StrSearching*)getParent();
    	StrSearching* sonPtr;
    	if (ptr!=NULL)
    	{
    		for (int i=0; i< ptr->sonCount; i++)
    		{
    			sonPtr = (StrSearching*)(getNode(ptr->son+i));
    			delete []sonPtr->curString;
    		}
    	}
    	DFS::onLeave();
    }

    bool StrSearching::validateOption(int sonData)
    {
    	char* pStr;
    	StrSearching* ptr = this;
    	if (strncmp(curString+state, ruleString[0][sonData], strlen(ruleString[0][sonData]))==0)
    	{
    		pStr = replaceStr(curString, ruleString[1][data], state, strlen(ruleString[0][data]));
    		trackString();
    		for (int i=0; i<=depth; i++)
    		{
    			if (strcmp(records[i], pStr)==0)
    			{
    				delete []pStr;
    				return false;
    			}
    		}
    		delete []pStr;
    		return true;
    	}
    	return false;
    }

    void StrSearching::onAfterAdded()
    {
    	curString = replaceStr(((StrSearching*)(getParent()))->curString, ruleString[1][data],
    		state, strlen(ruleString[0][data]));
    }

    void StrSearching::onBeginSearch()
    {
    	curString = createString(ruleString[0][ruleNum]);
    }

    bool StrSearching::evaluate()
    {
    	return strcmp(curString, ruleString[1][ruleNum])==0;
    }

    void StrSearching::collectResult()
    {
    	cout<<"A solution\n";
    	trackString();
    	for (int i=0; i<=depth; i++)
    	{
    		cout<<records[i]<<endl;
    	}
    }

    void StrSearching::readFile(const char* fileName)
    {
    	ifstream in(fileName, ios::in);
    	char buffer[2][20];
    	in>>ruleNum;
    	for (int i=0; i< ruleNum+1; i++)
    	{
    		in>>buffer[0]>>buffer[1];
    		ruleString[0][i] = createString(buffer[0]);
    		ruleString[1][i] = createString(buffer[1]);
    		options[i] = i;//0,1,2...
    	}
    	setOptions(options, ruleNum);
    }

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

    char* StrSearching::createString(const char* input)
    {
    	char* result = new char[strlen(input)+1];
    	if (result==NULL)
    	{
    		cout<<"Unable allocate memory!\n";
    	}
    	else
    	{
    		strcpy(result, input);
    	}
    	return result;
    }

    void StrSearching::setStateCount()
    {
    	stateCount = strlen(curString);
    }

    ””

    Running result of program:

    You may notice in the solution of Code Competition 1, that "big master" suggest a breadth-first-search, cause it

    will give you shortest answer for sure. Indeed, but a "max level" restricted "depth-first-search" will give you same

    result as expected. And you can see there is one more solutions!

    A solution
    abab
    baab
    babcd
    bbcdcd
    bbad
    bbabb
    bbbab
    bbbba
    A solution
    abab
    baab
    babcd
    bbcdcd
    bbcdcbb
    bbabb
    bbbab
    bbbba
    A solution
    abab
    baab
    babcd
    babcbb
    bbcdcbb
    bbabb
    bbbab
    bbbba
    A solution
    abab
    abbcd
    babcd
    bbcdcd
    bbad
    bbabb
    bbbab
    bbbba
    A solution
    abab
    abbcd
    babcd
    bbcdcd
    bbcdcbb
    bbabb
    bbbab
    bbbba
    A solution
    abab
    abbcd
    babcd
    babcbb
    bbcdcbb
    bbabb
    bbbab
    bbbba
    A solution
    abab
    abbcd
    abbcbb
    babcbb
    bbcdcbb
    bbabb
    bbbab
    bbbba