Puzzle

> > > Code Competition(1)

    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.

This is input file contents:

    5
    a ab
    ab ba
    baa bab
    ba ab
    bab bcb
    abaaaa
    bcbcbcb

This is output file contents:

    abbaaaa
    babaaaa
    bcbaaaa
    bcbabaa
    bcbcbaa
    bcbcbab
    bcbcbcb

¡¡