A.First Edition

This is actually first edition of Code Competition 1. (Click to see the problem)

1。 Basic idea: 

This is from last year of "Code Competition" of "Concordia Computer Science Association"(CCSS)

This is considered to be the most difficult one, so I only do it after all other 3 problems are finished. But

according to the author of solution, he considered that this is not the most difficult one though the code is 

still the longest one. And acutually he coded I think not more than one morning, I guess, but it took me about

two days! It has become my little wish to meet this incredible programmer though he may not regard himself so

great. But to me I think it is quite unimaginable at my standard. 

Indeed it is a breadth-first-search problem again. But after first experience with problem 4, the thought to 

write a class to wrap all algorithm of this kind of problem really push me to think it for almost half day.

Finally I give up, as design both tree class and node class like "Delphi" indeed cost me more than a solvation

of a bunch of problems. I simply don't afford of so much time. The spring break is only a week and I still have 

four assignments of four courses to finish. 

2。 Program design: 

I design a "huge" struct to stand for our nodes. It is after debugging that I realized that I have to prevent 

too many nodes of repeating by checking repeatance before add same node to one level. I thought about possibility

that a node is repeating itself after several levels. It is indeed possible increase the total volume of tree.

But as long as it does not result in looping, who cares?

It is actually quite simple in find next possible sibling of a node at same level. Suppose a king is dying,

according to their strange rule that he must first find candidate among his brothers for his decedant. Then 

he search to see if there is any little brother of his with same father as he has. If not, he has to see, if 

his father has any little brother who has a decedant of same age (same level) of him. If that uncle has not, 

then check if that uncle has an uncle who has a decedant of  same-age as this king. And so on, if no uncle can

be found anymore, the dying king can then be rest assured to tranform crown to the first decedant of younger age

(one level below) who share with him a same very first ancester---root. This is my algorithm.

In this program, I not only use too much recursion, but also use what I hate most---too many global variable and

flags when I am exhaused to add one more parameter to pass a simple bool result back to caller. I have written

too many functions. After I tried function parameter passing in "MASM", I have realized how much cost it took

to finish a simple function call with parameters and local variables. OK. Forget about it. 

3。 Major function：

	A. void findRule(int i)

	int pos(char* str, char* sub, int starting=0);

	This function do exactly find&replace job in a source string with a given substring. It has an internal 

function "pos()" which has similar function in "Delphi" with same name of course. I took a lot of time to try

"strstr" which is the only function I can find in "C++". But it can only find the first position of the substring.

I have to do the calculation of offset, if I want to call repeatedly. I don't understand why in c++, there is 

no such basic function of string operation! Maybe all c++ program write all liberary by their own!? Or would 

they simply use "string" class? I have no idea of "MFC".

This simple pos function cost me a lot in debugging even I am beginning to doubt my coding ability!

     B. bool sameResult(char* str)

	This function is test first to see if a string format is already in the same level to reduce volume of 

tree. As I didn't expect the size of one level, I arbitarily give 200 for each level to store string of one

level in an char* array, it cost me more than one hour to figure out the problem. It is even more than 1000

with only 7 levels! I gave it 5000 at first time when first found the problem for safe. It stores actually 

the string of his son of each node when generated. And when advancing to deeper level, change the counter of 

array to 0 to start new level.

     C. void addRule(int ruleNum, FILE* stream)

	This function read from input file and put both rule and its target into a double-subscript array of char*.

      D.  void addNode(); Node* findNext();  Node* findNext();Node* findCousin(Node* node);

	This is the way to check each node in the tree with all rules to see if there is any more possible 

transformation solution to build the tree. The heart is how to determine next node to build. It should first

find same-level brother, and then found a same-level cousin. But to find a cousin with same level, you need to try

out all small uncles of "yourself". So, recursively call to find an uncle of an uncle until with that uncle,

you can find a decedant of same level of you. If all failed, you have ask your common ancestor--root to find

the first available decedant of one more level than you. That is going to deeper level.	

4。 Further improvement：

	A. I use too many recursive calls which may require too much memory.	

	B. I forgot to delete all tree when program ended.

#include <iostream>
#include <fstream>
#include <ctime>

using namespace std;

const MaxSonNum = 10;

const MaxRuleNum = 10;

const MaxStep = 100;

const Return = 10;

const Space = 32;

int ruleCount=0;

int level = 0;

char* rules[2][MaxRuleNum];

char target[10];

char* words[3000];

int wordCount = 0;

struct Node
{
	char* data;
	Node* parent;
	Node* children[MaxSonNum];
	int childCount;
	int level;
	int index;
};

Node* result = NULL;

Node root;

Node* current;

Node* steps[MaxStep];

void startRule();

Node* findCousin(Node* node);

bool sameResult(char* str);

void inputFile(char* fileName);

void outputFile(char* fileName);

bool testResult();

void addNode();

Node* findUncle(Node* node);

Node* findFirstSon(Node* node);

Node* findBrother(Node* node);

void addNew(char* str);

void addRoute();

int main()
{
	long now;
	now = time(0);
	inputFile("c:\\nickInput.txt");
	outputFile("c:\\nickOutput.txt");
	cout<<time(0) - now;
	return 0;
}

void outputFile(char* fileName)
{
	ofstream f;
	f.open(fileName);
	for (int i=0; i< result->level; i++)
	{
		f<<steps[i]->data;
		f<<'\n';
	

	}
}

void addRoute()
{
	Node* ptr = result;
	for (int i=ptr->level-1; i>=0; i--)
	{
		steps[i] = ptr;
		ptr = ptr->parent;
	}
}

void addNew(char * str)
{
	Node* ptr = new Node;
	ptr->data = (char*)malloc(strlen(str)+1);
	strcpy(ptr->data, str);
	ptr->parent = current;
	ptr->childCount = 0;
	current->children[current->childCount] = ptr;
	current->childCount++;
	ptr->level = current->level+1;
	ptr->index = current->index + current->childCount;
	words[wordCount] = ptr->data;
	wordCount++;
	if (strcmp(target, str)==0)
	{
		result = ptr;
	}

}

bool testResult()
{
	return result!=NULL;
}

int pos(char* str, char* sub, int starting)
{
	char* p = str + starting, *q=sub;
	int count =0, result=0;

	while(*p!='\0')
	{		
		q = sub;
		result = count;
		while (*p==*q&&*q!='\0'&&*p!='\0')
		{
			p++;
			q++;
			count++;			
		}
		if (*q=='\0')
		{
			return result;
		}
		if (*p=='\0')
		{
			return -1;
		}
		count++;
		p++;
	}
	return -1;
}

void findRule(int i)
{
	int pos(char* str, char* sub, int starting=0);

	char* pSrc=NULL;
	char* pSub = NULL;
	char* pTarget = NULL;
	char* ptr =NULL;
	char buffer[30];
	int lenS = 0, offset=0, lenT, starting =0 ;

	pSrc = current->data;
	pSub = rules[0][i];
	pTarget = rules[1][i];
	lenS = strlen(pSub);
	lenT = strlen(pTarget);

	offset = pos(pSrc, pSub, starting);
	while(offset!=-1)
	{		
		starting += offset + lenS;
		strncpy(buffer, pSrc, starting -lenS);
		

		strncpy(buffer+starting - lenS, pTarget, lenT);
		buffer[starting - lenS + lenT] = '\0';
		strcat(buffer, pSrc+ starting);
	

		if (!sameResult(buffer))
			addNew(buffer);
		

		
		offset = pos(pSrc, pSub, starting);
	}
}

Node* findBrother(Node* node)
{
	if (node==NULL)
	{
		return NULL;
	}
	else
	{
		if (node->parent==NULL)
		{
			return NULL;
		}
		else
		{
			for (int i=0; i< node->parent->childCount; i++)
			{
				if (i<node->parent->childCount - 1 && node==node->parent->children[i])
				{
					return node->parent->children[i+1];
				}
			}
		}
	}
	return NULL;
}

Node* findUncle(Node* node)
{
	Node* pNode = node;
	Node* ptr = NULL;
	while (true)
	{
		if (pNode->level == 0)
			break;
		ptr = findBrother(pNode);
		if (ptr!=NULL)
			break;
		pNode = pNode->parent;
		

	}
	return ptr;
}

Node* findFirstSon(Node* node)
{
	Node* ptr = NULL;
	Node* pNode = node;
	int i=0;

	if (node==NULL)
	{
		return NULL;
	}
	else
	{
		if (node->level == level)
		{
			return node;
		}
	}

	while (ptr == NULL)
	{
		if (i==pNode->childCount)
		{
			break;
		}
		ptr = findFirstSon(pNode->children[i]);
		i++;
	}
	return ptr;
}

Node* findCousin(Node* node)
{
	Node* ptr = node;
	Node* dummy=NULL;
	

	while (dummy==NULL)
	{
		ptr = findUncle(ptr);
		if (ptr==NULL)
		{
			break;
		}
		dummy = findFirstSon(ptr);
	}

	return dummy;
}

bool sameResult(char* str)
{

	for (int i =0; i< wordCount; i++)
	{
		if (strcmp(str, words[i])==0)
		{
			return true;
		}
	}
	return false;
}

Node* findNext()
{
	Node* ptr= NULL;
	ptr = findCousin(current);
	if (ptr==NULL)
	{
		ptr = &root;
		level++;
		

		ptr = findFirstSon(ptr);
	

		wordCount = 0; 
		

	}
	return ptr;	
}

void addNode()
{
	void findRule(int i);

	for (int i=0; i<ruleCount; i++)
	{
		findRule(i);
	}
	current = findNext();
}

void startRule()
{
	root.index = 0;
	root.level = 0;
	root.parent = NULL;
	root.childCount = 0;
	current = &root;
	do 
	{
		addNode();
		

	}
	while (!testResult());
	addRoute();
}

int getNum(FILE* stream)
{
	char ch;
	int result =0;
	ch = fgetc(stream);
	while (isdigit(ch))
	{
		result = result*10 + atoi(&ch);
		ch = fgetc(stream);
	}
	return result;
}

void readStr(FILE* stream, char* buffer)
{
	char ch;
	char * ptr = buffer;
	ch = fgetc(stream);
	while (ch != Return && ch!= Space&&!feof(stream))
	{
		*ptr = ch;
		ptr++;
		ch = fgetc(stream);
	}
	*ptr = '\0';
}

void addRule(int ruleNum, FILE* stream)
{
	void readStr(FILE* stream, char* buffer);

	char buffer[30];
	for (int i=0; i< ruleNum; i++)
	{
		readStr(stream, buffer);
		rules[0][i] = (char*)malloc(strlen(buffer)+1);
		strcpy(rules[0][i], buffer);
		readStr(stream, buffer);
		rules[1][i] = (char*)malloc(strlen(buffer)+1);
		strcpy(rules[1][i], buffer);
	}
	readStr(stream, buffer);
	root.data = (char*)malloc(strlen(buffer) +1);
	strcpy(root.data, buffer);
	readStr(stream, target);
}

void inputFile(char* fileName)
{
	int getNum(FILE* stream);
	void addRule(int ruleNum, FILE* stream);

	int ruleNum =0;
	FILE* stream;
	stream = fopen(fileName, "r");
	ruleNum = getNum(stream);
	ruleCount = ruleNum;
	addRule(ruleNum, stream);
	startRule();
}




I omit the first test result. And quite to my surprise, it only cost me 6seconds and the author of solution said his program

runs about 20 seconds. Maybe his computer is very old. Of course he wrote the program so fast, the efficiency is not the first

consideration.