/* 

	Abbott's Revenge

	An open/close tree traversal program.

	Author: David Shoon
	Last revised: 31/May/2004

        ---------------------------------------------------------------

	Goal and Ideas:
	This was based off Dr Rist's lecture on open/close tree
	traversal for breadth-first search. The original program was
	a C language depth search program. It was then modified  
	into C++ for open/close search.

	Basically, the program does:
	1) Store data into maze table 
		- parsing left/right to appropriate north/south/west/east directions
	The idea is this creates a table map instead of a pointer map. This 
	may slow down _continuous_ traversal a slight bit, but gives the convenience of 
	being able to reference any node in instant time.

	2) Store traversed paths into the open/close lists as appropriate, using
	STL list for faster coding. Two helper functions were added: add_open, and
	search_close. Both perform routines critical to the open/close traversal.
		- During traversal, store the parent node of the traversed node as well.
		- This is later used to generate the solution. (This may/may not have
		- been discussed in the class.)

	3) The solution is to trace back from the last (goal) via traversing the parent
	listed. This traversal is stored into a LIFO stack which is then regurgitated
	for output. In this program, STL list was used instead of STL stack, because
	an STL stack is just a restricted STL list (implementation-wise). 

	Possible optimisations:
	1) The code for searching the closed list can be made into a STL map (row, col, dir), 
	binary tree, or a hash, instead of a linear search algorithm. This would speed up 
	traversal greatly. 

	2) If only a single path and not shortest path was needed, this algorithm is not 
	optimal. A change from push_back to push_front into the add_open function
	would give you depth-first search (optimal) instead of breadth-first.

	3) If heuristics were available on the data set, then a heuristic method based on
	the open/close tree traversal may be faster. 

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <list>


/********************************* data && data types ***************************/

/******** GENERAL DATA TYPES ****************/

// flags (after directions on sign translated to compass directions)

#define NORTH 0x01
#define EAST  0x02
#define SOUTH 0x04
#define WEST  0x08

#define TOTAL (WEST+1)
#define ALL	0x0f

/******** Maze storage specific data types ********/

typedef int flags;

// a Maze is a storage unit to hold the parsed maze data. It is _not_ the object used
// to store the tree traversal. 

struct Maze
{
	// flags are also used as array indexes, which makes the code easier but larger in memory
	// (saves translating flags into indexes)
	flags dir[TOTAL]; 
};

/******** Traversal specific data types *************/

// each link in the maze, is described by 3 primary keys (row, col, and direction)

struct Link
{
	int row;
	int col;
	int dir;
};

// each Node is a node in the tree traversal algorithm. 

struct Node : public Link
{
	Node *parent;
};

typedef std::list<Node *> NodeList;

/************ GLOBAL VARIABLES ***************/

Link Entrance;
Link Goal;

Maze table[9][9];
char Name[1024];

NodeList list_open;
NodeList list_close;

/**************************** support functions ************************/

char *strip_newline(char *s)
{
	char *p;
	p = strpbrk(s, "\r\n");
	if (p) *p = 0;
	return s;
}

void add_open(Node *parent, int row, int col, int dir)
{
	Node *temp;

	temp = new Node();

	temp->parent = parent;
	temp->row = row;
	temp->col = col;
	temp->dir = dir;

	list_open.push_back(temp);
}

int search_close(int row, int col, int dir)
{
	NodeList::iterator it;
	Node *node;

	for (it = list_close.begin(); it != list_close.end(); it++) {
		node = *it;
		if ((node->row == row) && (node->col == col) && (node->dir == dir)) {
			return 1;
		}
	}	

	return 0;
}

/************************************* main functions *****************************/

void printSol()
{
	NodeList::iterator it;
	Node *node;
	NodeList solution;

	// the final goal node is in the open list, since we didn't close it yet..
	// we know it is the one which matches our row,col

	for (it = list_open.begin(); it != list_open.end(); it++) {
		node = *it;

		if ((node->row == Goal.row) && (node->col == Goal.col)) {
			while (node) {
				solution.push_front(node);
				node = node->parent;
			}

			break;
		}
	}

	printf("(%d,%d) ", Entrance.row, Entrance.col);

	for (it = solution.begin(); it != solution.end(); it++) {
		node = *it;
		printf("(%d,%d) ", node->row, node->col);
	}

	printf("\n");
}

void printNoSol()
{
	printf("No Solution Possible\n");
}

/* 
params: 
Node *parent = parent node
row, col = current row and column
direction = direction of movement

returns 1 if we've found a goal
returns 0 otherwise

*/
int traverse(Node *parent, int row, int col, int dir)
{
	int nrow, ncol; // new location

	switch(dir) {
		case NORTH:
			nrow = row - 1;
			ncol = col;
		break;

		case EAST:
			nrow = row;
			ncol = col + 1;
		break;

		case SOUTH:
			nrow = row + 1;
			ncol = col;
		break;

		case WEST:
			nrow = row;
			ncol = col - 1;
		break;
	}

	add_open(parent, nrow, ncol, dir);

	// always check to see if we made the goal..

	if ((nrow == Goal.row) && (ncol == Goal.col)) {
		return 1;
	}

	return 0;
}


void run()
{
	int r;
	NodeList::iterator it;
	int flags, i; // for traversal
	Node *node;

	printf("%s\n", Name);

	r = traverse(NULL, Entrance.row, Entrance.col, Entrance.dir);

	while(!list_open.empty()) { // this is not necessary in breadth-first, but needed in depth-first
		for (it = list_open.begin(); it != list_open.end();) {
			node = *it;

			for (flags = NORTH, i = 0; i < 4; flags = flags << 1, i++) {
				if (search_close(node->row, node->col, node->dir)) continue;

				if (table[node->row][node->col].dir[node->dir] & flags) {
					r = traverse(*it, node->row, node->col, flags);
					if (r == 1) { printSol(); return; }
				}
			}

			// add to list_close
				list_close.push_back(*it);

			// remove from list_open, and get the next iterator
			it = list_open.erase(it);
		}
	}

	printNoSol();
}


/******************** parser ***********************/

int dirparse(char *tok)
{
	int x;
	int y;

	x = 0;
	y = *tok;
	tok = tok + 1;

	while (*tok != 0) {
		switch (*tok) {
			case 'L':
				if (y == 'N') x |= WEST;
				else if (y == 'E') x |= NORTH;
				else if (y == 'S') x |= EAST;
				else if (y == 'W') x |= SOUTH;
			break;

			case 'R':
				if (y == 'N') x |= EAST;
				else if (y == 'E') x |= SOUTH;
				else if (y == 'S') x |= WEST;
				else if (y == 'W') x |= NORTH;
			break;

			case 'F':
				if (y == 'N') x |= NORTH;
				else if (y == 'E') x |= EAST;
				else if (y == 'S') x |= SOUTH;
				else if (y == 'W') x |= WEST;
			break;
		}

		tok++;
	}

	return x;
}

void nodeparse(int row, int col, char *tok)
{
	switch(tok[0]) {
		case 'N':
			table[row][col].dir[NORTH] = dirparse(tok);
		break;

		case 'S':
			table[row][col].dir[SOUTH] = dirparse(tok);
		break;

		case 'E':
			table[row][col].dir[EAST] = dirparse(tok);
		break;

		case 'W':
			table[row][col].dir[WEST] = dirparse(tok);
		break;

	}
}

void parse()
{
	char string[1024];
	char *tok;
	int row, col;

	memset(table, 0, sizeof(table));

// parse in entrance/goal details
	fgets(string, sizeof(string), stdin);
	strip_newline(string);

	tok = strtok(string, " "); assert(tok);
	Entrance.row = atoi(tok);

	tok = strtok(NULL, " "); assert(tok);
	Entrance.col = atoi(tok);

	tok = strtok(NULL, " "); assert(tok);
	switch(*tok) {
		case 'N': Entrance.dir = NORTH; break;
		case 'E': Entrance.dir = EAST; break;
		case 'S': Entrance.dir = SOUTH; break;
		case 'W': Entrance.dir = WEST; break;
	}

	tok = strtok(NULL, " "); assert(tok);
	Goal.row = atoi(tok);
	
	tok = strtok(NULL, " "); assert(tok);
	Goal.col = atoi(tok);
	
// parse in intersection details

	while (fgets(string, sizeof(string), stdin)) {
		strip_newline(string);

		tok = strtok(string, " ");
		if (!tok) break;
		row = atoi(tok);
		if (row == 0) break;

		tok = strtok(NULL, " ");
		if (!tok) break;
		col = atoi(tok);

		while ((tok = strtok(NULL, " ")) != NULL) {
			if (strcmp(tok, "*") == 0) break;

			nodeparse(row, col, tok);
		}
	}
}

int main()
{
	char string[1024];

	while (fgets(string, sizeof(string), stdin)) {
		strip_newline(string);

		if (strcmp(string, "END") == 0) {
			break;
		}

		if (strcmp(string, "") == 0) { 
			continue; 
		}

		strcpy(Name, string);

		parse();
		run();
	}
}