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);
	}
}

Hosted by www.Geocities.ws