Puzzle

> > > Code Competition(3)

    A.First Edition

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

    1¡£ Basic idea:

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

    This is the second simplest one among 4 problems.(I guess that as I browse the result and most of them only

    figour out this one and the no 2 problem.) It is actually a common job in data structure courses. I finished

    after more then 3 hours. I guess I won't become the winning team as I think I am not the kind of coding fast.

    2¡£ Program design:

    Actually it is not a very difficult problem compared with "Baggles" which I coded with Delphi in Toronto which

    is the assignment of "University York". It is also said to be originally from "MIT" or "Standford" or somewhere.

    That problem is actually a small project which involes "lexico", "depth first search", and other data structure

    skills. I only finished these two parts. Stop this!

    Let's talk about something of problem. The input quite cost a lot of job. I made a mistake when reading number

    with more than 1 digit. I used a recursive function "doSearch()" which move to new position by original "direction"

    and "word" with first letter "missing". I just move the pointer of "word" by 1. The recursive function doSearch

    return write a "Pos" struct to a "Pos*" array when it find out the "word" is only one letter left.

    3¡£ Major function£º

         A. void inputFile(char* fileName)

    	This function is quite long as I didn't expect to add so many parts in together. First it read in the "dimention" of

    array which give some trouble as I only expect one digit number. Then it just read the length of a word first then read in the

    word until read 0;

         B. void searchWord(char* word)

    	This function first find the pos match the first char of "word" and then call "scanWord".

    	C.  void scanWord(int i, int j, char* word)

    	   void doSearch(int i, int j, char* pWord, Direction dir);

    	within "scanWord" there is the recursive function of "doSearch" which "move" from current co-ordinate(i,j) to next position

    calculated by "Direction"---dir. The function "testDir" test next position also return next destination co-ordinate. Then

    the function just pass new co-ordinate, original direction, and "word" with first char "missing"(move the pointer by 1) to

    recursive call itself. "doSearch" stop to add new struct of "Pos" to a list when he found the "word" is only one char.

    	D. bool testDir(int& row, int& col, Direction dir)

    	A standard moving test function. I think it is exactly same as my old "Delphi" function which I lost when my old laptop

    choose to suitcide.

    4¡£ Further improvement£º

    	A. This simple program cost me almost 3 hours.

    	B. I forgot to delete dynamically allocated memory at end of execution.

    #include <iostream>
    #include <fstream>

    using namespace std;

    enum Direction
    {LeftUp, Up, RightUp, Right, RightDown, Down, LeftDown, Left};

    const MaxDim = 100;

    const MaxWordCount = 100;

    const MaxRec = 200;

    struct Pos
    {
    	char* word;
    	int startRow;
    	int startCol;
    	int endRow;
    	int endCol;
    };

    Pos* record[MaxRec];

    int recordCount =0;

    Pos start;

    char * words[MaxWordCount];

    char matrix[MaxDim][MaxDim];

    int dim = 0;

    int wordCount =0;

    void inputFile(char* fileName);

    void outputFile(char * fileName);

    void searchWord(char* word);

    void scanWord(int i, int j, char* word);

    bool testDir(int& row, int& col, Direction dir);

    int main()
    {
    	inputFile("c:\\nickinput.txt");
    	outputFile("c:\\nickoutput.txt");
    	return 0;
    }

    void outputFile(char* fileName)
    {
    	ofstream f;
    	f.open(fileName);
    	for (int i=0; i<recordCount; i++)
    	{
    		f<<record[i]->word<<" "<<record[i]->startRow<<" "<<record[i]->startCol;
    		f<<" "<<record[i]->endRow<<" "<<record[i]->endCol<<"\n";
    	}
    }

    void inputFile(char* fileName)
    {
    	FILE* stream;
    	char buffer[20];
    	char * ptr;
    	char ch;
    	int len=0;
    	stream = fopen(fileName, "r");
    	ch = fgetc(stream);

    	while (isdigit(ch))
    	{
    		dim = 10 * dim + atoi(&ch);
    		ch = fgetc(stream);
    	}

    	for (int i=0; i< dim; i++)
    	{
    		for (int j=0; j<dim; j++)
    		{
    			matrix[i][j] = ch;
    			ch = fgetc(stream);
    		}
    	}
    	while (!isalnum(ch))
    	{
    		ch = fgetc(stream);   //eat non alpha number
    	}
    	while(true)
    	{
    		len =0;
    		while(isdigit(ch))
    		{
    			len = len*10 + atoi(&ch);
    			ch = fgetc(stream);
    		}
    		if (len==0)
    			break;
    		ptr = buffer;
    		for (i=0; i< len; i++)
    		{
    			*ptr = ch;
    			ch = fgetc(stream);
    			ptr++;
    		}
    		*ptr = '\0';
    		words[wordCount] = (char*)malloc(len+1);
    		strcpy(words[wordCount], buffer);
    		wordCount++;

    	}
    	for (i=0; i< wordCount; i++)
    	{
    		searchWord(words[i]);
    	}
    }

    bool testDir(int& row, int& col, Direction dir)
    {
    	int i = row, j = col;
    	switch(dir)
    	{
    	case LeftUp:
    		i--;
    		j--;
    		break;
    	case Up:
    		i--;
    		break;
    	case RightUp:
    		i--;
    		j++;
    		break;
    	case Right:
    		j++;
    		break;
    	case RightDown:
    		i++;
    		j++;
    		break;
    	case Down:
    		i++;
    		break;
    	case LeftDown:
    		i++;
    		j--;
    		break;
    	case Left:
    		j--;
    		break;
    	}
    	if (i<0||j<0||i>=dim||j>=dim)
    	{
    		return false;
    	}
    	else
    	{
    		row = i;
    		col = j;
    		return true;
    	}
    }

    void searchWord(char* word)
    {
    	for (int i =0; i<dim; i++)
    	{
    		for (int j=0; j< dim; j++)
    		{
    			if (matrix[i][j]==*word)
    			{
    				scanWord(i, j, word);
    			}
    		}
    	}
    }

    void doSearch(int i, int j, char* pWord, Direction dir)
    {
    	if (*pWord == matrix[i][j])
    	{
    		if (strlen(pWord)==1)
    		{
    			Pos * ptr = new Pos;
    			ptr->word = start.word;
    			ptr->startRow = start.startRow;
    			ptr->startCol = start.startCol;
    			ptr->endRow = i;
    			ptr->endCol = j;
    			record[recordCount] = ptr;
    			recordCount++;
    			return;
    		}
    		else
    		{
    			if (testDir(i, j, dir))
    			{
    				doSearch(i, j, pWord+1, dir);
    			}
    		}
    	}
    }

    void scanWord(int i, int j, char* word)
    {
    	int row = i, col = j;
    	char *ptr = word;
    	void doSearch(int i, int j, char* pWord, Direction dir);

    	for (int dir = LeftUp; dir<= Left; dir++)
    	{
    		start.word = word;
    		ptr = word;
    		row = i;
    		col = j;
    		start.startRow = i;
    		start.startCol = j;
    		doSearch(row, col, ptr, (Direction)dir);
    	}
    }

This is input file contents:

21
trihsyffupjsizanpuoscjracyllemsoxcdtkqkhprsulhecrlnvnhoomtnveeadinjakqtkhvacesriabnzyarixtvxvnozktltqprfykglbojvcwuiznjveacrf
jnonaerbeetgiarsclnkmokmnishmcvthpyefdaczyeyscahgtirctsangromnadoomjmtignnsedndndvxuakchttrobhtciaeeckllbvpuddyyenwdapyrbweqx
rozorbukwttprpabazmkkolkjccmcgpeuqodnnbrafragvbqgimltpopaiisrnntnehwjbvfitdjbyeacrtwsiooizdvwxcdtuatrnnxsekrsbbzfhvukxmdsbsnn
eaxgqigafcbffenaqvperzmbegaknirhswmyekardehteelainebenesrsxkramerm
7maestro12yadayadayada8soupnazi5cosmo11elainebenes8costanza6kramer12aboutnothing5frank6george6newman14crazyjoedavola8
uncleleo9smellycar10juniormint8thedrake10puffyshirt7thebris12poppiespizza6mickey9shrinkage8bigsalad5bania13jonvoightscar6
mrpitt5puddy12steinbrenner9jpeterman0

This is output file contents:

maestro 18 19 12 19
yadayadayada 7 12 18 12
soupnazi 0 19 0 12
cosmo 10 1 6 1
elainebenes 20 0 20 10
costanza 1 12 8 19
kramer 20 14 20 19
aboutnothing 16 12 5 1
frank 5 19 1 15
george 14 0 19 0
newman 9 13 14 18
crazyjoedavola 0 20 13 20
uncleleo 9 19 2 12
smellycar 1 9 1 1
juniormint 1 0 10 9
thedrake 19 19 19 12
puffyshirt 0 9 0 0
thebris 8 6 2 0
poppiespizza 14 11 3 11
mickey 14 6 19 11
shrinkage 19 8 19 0
bigsalad 10 7 3 0
bania 11 14 15 14
jonvoightscar 0 10 12 10
mrpitt 6 19 1 14
puddy 11 0 11 4
steinbrenner 17 13 6 13
jpeterman 15 10 7 2