Puzzle

> > > Code Competition(4)

    A.First Edition

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

    1¡£ Basic idea:

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

    This is a quite unexpected difficult problem as I tried to use "Breadth First Search" which I never tried before.

    I finished after more then one day! I guess I won't become the winning team as I think I am not the kind of

    coding fast.

    Actually I tried "Maze" problem before except that my old program cannot gurantee about "shortest" path. Even

    in old program I add some kind of "shortcut", still it is not a total solution. And I really want to try to use

    "Breadth First Search". However, it turned out quite complicated, even more complicated than "Depth First Search".

    At least I think so. I tried to find some algorithms in my "Data Structure Bible". But they only give a very

    common psudocode for graph which helps me little with this 3-son tree. After wasting almost a whole night usless

    debating with "MBA HU" about "Machine Authority", my time ran out like Mr. Sadam Hussain. And this morning I

    tried my best to rewrote the way of "searching next cousin". As soon as I hailed my success, I found out that

    the problem even requires "SEVERAL" mazes to be input at one time! I fainted. I have to destroy all my tree and

    output the result before I read next maze which means a "Walk-Arround" algorithms is required to delete all nodes.

    It cost my noon sleep to finish tracing and debugging.

    2¡£ Program design:

    I design a "huge" struct to stand for our nodes. In order to prevent looping, I used the way similar to solution

    that is to write a temporary "*" to represent every square I reached. In my old program, I actually record each

    step in an array, and I check the contents to see if I am looping. Maybe that is more effiently, I really don't

    know. As for find next sibling, I first try to find one of his uncle and then try to see if this uncle has any son

    of which the level are same to my current node. Then this should be his "cousin". If there is not a cousin for

    this "uncle", I try to find an "uncle" of this "uncle", then try to find his child of same level of my node. And

    so on, if there is no more uncle can be found, this means that there is no cousin. I have to find next generation

    of my node by "findFirstSon()" function. Before output result, I erase the temporary mark "*". "Breadth First

    Search" will definitely give you the shortest path but it is not the shortest way to code.

    3¡£ Major function£º

    	A. void startSearch(Node* node)

    	This function do the searching job, it tests each node to see if it is exit point. If not, it call addNode()

    to add new children of this node. Then it tries to find next node to repeat by first try same generation, if

    failed, try next generation.

         B. Node* nextSibling(Node* node)

    	This function find next node when constructing my tree. It first find "same father brother", then try find next uncle,if

    the uncle has a same-level child, it return the child. If not, try the uncle of "this uncle" until no more uncle fits. It will

    try next generation.

         C. Node* findSibling(Node* node)

    	This function does what I described above: first find an uncle to see if he has a same-level child. Until no more uncle can

    be found, it returns NULL to indicate this.

    	D.  Node* findBrother(Node* node)

    	This is the function to find same-father brother: if you are left son, the next possible is mid son, or right son by sequence.

    If you are mid-son, the only possible is right son. if you are right son, you have no same-father brother.

    	E. Node* findFirstSon(Node* node)

    	This is a "level-defined" searching for first possible child. Until you reach the level, you will repeat to find the

    first sequence child.

    	F. Node* findUncle(Node* node)

    	It is simple, your uncle is one of your father's little brother. If you father doesnot have one, try your grandfather.

    	G. void addNode(Node* node)

    	Node* doAdding(Node* node, Direction dir);

    	This function generate sons of this node with directions which means that according to the node's direction, you arrange

    the sequence of left, mid, right son accordingly. He has an internal function doAdding();

    	H. bool solveMaze(FILE* stream)

    	   void initialize();

    	Pls note the internal method initialize() which has to clear all nodes before we can re-construct the tree. However, this

    means a "Walk-Arround" from all leafs of tree to delete one by one. Its internal function "findSingle()" is similar as

    findFirstSon() except it doesnot require to go to certain depth levels.

    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>

    using namespace std;

    enum Direction
    {Up, Right, Down, Left};

    const Space = 32;

    const Wall = 'X';

    const Passed = '*';

    const Route = '.';

    const Return = '\n';

    const MaxRow = 20;

    const MaxCol = 70;

    const MaxStep = 200;

    char maze[MaxRow][MaxCol];

    struct Node
    {
    	Node* parent;
    	Node* left;
    	Node* mid;
    	Node* right;
    	int row;
    	int col;
    	Direction direction;
    	int level;
    };

    Node start;

    int level =0;

    int rowLimit = 0;

    int colLimit = 0;

    bool solveMaze(FILE* stream);

    bool inputFile(char* fileName);

    void outputFile(char* fileName);

    bool evalueNode(Node* node);

    void generateNode(Node* node);

    void startSearch(Node* node);

    Node* findSibling(Node* node);

    void recordPath(Node* node);

    Node* findUncle(Node* node);

    Node* findFirstSon(Node* node);

    Node* findBrother(Node* node);

    Node* nextNephew();

    void addPath(Node* node);

    int main()
    {
    	FILE* f;
    	f = fopen("c:\\nickinput.txt", "r");
    	while (solveMaze(f))
    	{
    		outputFile("c:\\nickoutput.txt");
    	}
    	return 0;
    }

    void outputFile(char* fileName)
    {
    	FILE*  stream;
    	stream = fopen(fileName, "a");
    	for (int i = 0; i< rowLimit; i++)
    	{
    		for (int j =0; j < colLimit; j++)
    		{
    			if (maze[i][j] == Passed)
    			{
    				maze[i][j] = Space;
    			}
    			fputc(maze[i][j], stream);
    		}
    		fputc('\n', stream);
    	}
    	fclose(stream);
    }

    Node* findSingle(Node* node)
    {
    	Node* ptr= node;
    	if (node != NULL)
    	{
    		ptr = findSingle(node->left);
    		if (ptr==NULL)
    		{
    			ptr = findSingle(node->mid);
    		}
    		if (ptr==NULL)
    		{
    			ptr = findSingle(node->right);
    		}
    		if (ptr==NULL)
    		{
    			ptr = node;
    		}
    	}
    	return ptr;
    }

    void destroy(Node* ptr)
    {
    	if (ptr->parent->left == ptr)
    	{
    		ptr->parent->left = NULL;
    	}
    	if (ptr->parent->mid == ptr)
    	{
    		ptr->parent->mid = NULL;
    	}
    	if (ptr->parent->right == ptr)
    	{
    		ptr->parent->right = NULL;
    	}
    	delete ptr;
    }

    void initialize()
    {
    	Node* findSingle(Node* node);
    	void destroy(Node* ptr);

    	Node* ptr = &start;
    	while (true)
    	{
    		ptr = &start;
    		ptr = findSingle(ptr);
    		if (ptr!=&start&&ptr!=NULL)
    		{
    			destroy(ptr);
    		}
    		else
    		{
    			break;
    		}
    	}
    	level =0;
    	colLimit = 0;
    	rowLimit = 0;
    	start.row = 0;
    	start.col = 0;
    	start.left = NULL;
    	start.mid  = NULL;
    	start.right = NULL;
    	start.parent = NULL;
    	start.level = 0;
    }

    bool solveMaze(FILE* stream)
    {
    	void initialize();
    	char ch;
    	Node* ptr = &start;
    	bool setRoot = false;
    	int i=0, j=0;

    	initialize();

    	ch = fgetc(stream);
    	while(true)
    	{
    		j =0;
    		while(ch!=Return)
    		{
    			maze[i][j] = ch;
    			ch = fgetc(stream);
    			j++;
    		}
    		i++;
    		if (i ==1)
    		{
    			if (j==1)
    			{
    				return false;
    			}
    			colLimit = j;
    		}

    		ch = fgetc(stream);
    		if (ch==Return)
    		{
    			rowLimit = i;
    			break;
    		}

    		if (ch == Space&&!setRoot)
    		{
    			start.row = i;
    			start.col = 0;
    			setRoot = true;
    			start.left = NULL;
    			start.mid =NULL;
    			start.right = NULL;
    			start.parent = NULL;
    			start.direction = Right;
    			start.level = 0;
    			maze[i][0] = Passed;
    		}

    	}
    	startSearch(ptr);
    	return true;

    }

    Node* doAdding(Node* node, Direction dir)
    {
    	int row, col;
    	Node* ptr;

    	row = node->row;
    	col = node->col;

    	switch (dir)
    	{
    	case Up:
    		row--;
    		break;
    	case Right:
    		col++;
    		break;
    	case Down:
    		row++;
    		break;
    	case Left:
    		col--;
    		break;
    	}
    	if (row<0||row>=rowLimit||col<0||col>=colLimit||maze[row][col]==Passed
    		||maze[row][col]==Wall)
    	{
    		return NULL;
    	}
    	ptr = new Node;
    	ptr->row = row;
    	ptr->col = col;
    	ptr->direction = dir;
    	ptr->parent = node;
    	ptr->left = NULL;
    	ptr->mid = NULL;
    	ptr->right = NULL;
    	ptr->level = node->level + 1;
    	maze[row][col] = Passed;
    	return ptr;
    }

    void addNode(Node* node)
    {
    	Node* doAdding(Node* node, Direction dir);

    	maze[node->row][node->col] = Passed;
    	switch (node->direction)
    	{
    	case Up:
    		node->left = doAdding(node, Left);
    		node->mid = doAdding(node, Up);
    		node->right = doAdding(node, Right);
    		break;
    	case Right:
    		node->left = doAdding(node, Up);
    		node->mid = doAdding(node, Right);
    		node->right = doAdding(node, Down);
    		break;
    	case Down:
    		node->left = doAdding(node, Right);
    		node->mid = doAdding(node, Down);
    		node->right = doAdding(node, Left);
    		break;
    	case Left:
    		node->left = doAdding(node, Down);
    		node->mid = doAdding(node, Left);
    		node->right = doAdding(node, Up);
    		break;
    	}

    }

    bool testNode(Node* node)
    {
    	if (node!=&start&&node->col == 0)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }

    Node* findUncle(Node* node)
    {
    	Node* ptr = node;
    	if (ptr->parent!=NULL)
    	{
    		ptr = findBrother(ptr->parent);
    		if (ptr!=NULL)
    		{
    			return ptr;
    		}
    		else
    		{
    			return findUncle(node->parent);
    		}
    	}
    	return NULL;
    }

    Node* findFirstSon(Node* node)
    {
    	Node* ptr = node;
    	if (ptr==NULL)
    	{
    		return NULL;
    	}
    	if (ptr->level != level)
    	{
    		ptr = findFirstSon(node->left);
    		if (ptr==NULL)
    		{
    			ptr = findFirstSon(node->mid);
    		}
    		if (ptr==NULL)
    		{
    			ptr = findFirstSon(node->right);
    		}

    	}
    	return ptr;
    }

    Node* findBrother(Node* node)
    {
    	Node* ptr= NULL;
    	if (node!= NULL)
    	{
    		if (node->parent==NULL)
    		{
    			return NULL;
    		}

    		if (node->parent->left==node)
    		{
    			ptr = node->parent->mid;  //problem
    			if (ptr==NULL)
    			{
    				ptr = node->parent->right;
    			}
    		}
    		if (node->parent->mid == node)
    		{
    			ptr = node->parent->right;
    		}
    		return ptr;
    	}
    	return NULL;
    }

    Node* findSibling(Node* node)
    {
    	Node* pUncle = node;
    	Node* ptr;

    	while (true)
    	{
    		pUncle = findUncle(pUncle);
    		if (pUncle ==NULL)
    		{
    			return NULL;
    		}
    		ptr = findFirstSon(pUncle);
    		if (ptr!= NULL)
    		{
    			return ptr;
    		}
    	}
    }

    Node* nextSibling(Node* node)
    {
    	Node* ptr = node;
    	ptr = findBrother(node);
    	if (ptr==NULL)
    	{
    		ptr = findSibling(node);
    	}
    	return ptr;
    }

    Node* nextNephew()
    {
    	level++;
    	return findFirstSon(&start);
    }

    void addPath(Node* node)
    {
    	maze[node->row][node->col] = Route;
    	if (node->level == 0)
    	{
    		return;
    	}
    	else
    	{
    		addPath(node->parent);
    	}
    }

    void startSearch(Node* node)
    {
    	Node* ptr;
    	Node* pNode;

    	pNode = node;
    	while (!testNode(pNode))
    	{
    		addNode(pNode);
    		ptr = nextSibling(pNode);
    		if (ptr==NULL)
    		{
    			ptr = nextNephew();
    			if (ptr==NULL)
    			{
    				cout<<"no solution!";
    				//return;
    			}
    		}
    		pNode = ptr;
    	}

    	addPath(pNode);
    }

This is input file contents:

    XXXXXXXX
    XX     X
       X XXX
    XXX  X X
           X
    XXXXXXXX

    XXXXXXXXXX
    X        X
      XX XXXXX
    XX       X
      XXXXXX X
    X        X
    XXXXXXXXXX

    X

This is output file contents:

    XXXXXXXX
    XX...  X
    ...X.XXX
    XXX .X X
    .....  X
    XXXXXXXX
    XXXXXXXXXX
    X....    X
    ..XX.XXXXX
    XX  .....X
    ..XXXXXX.X
    X........X
    XXXXXXXXXX

¡¡