#include <time.h>
#include <stdio.h>
#include <strings.h> 
#include <stdlib.h>
#include "minfo.h"

// constants for status array second dimention
#define ST_COL 0
#define ST_ROW 1
#define ST_OPERATION 2
#define ST_SIZE 3

#define MATRIX_DISPLAY_INTERVAL 100000

int  simpleDist (int sx, int sy, int dx, int dy)
{
    return abs(dx - sx) + abs(dy - sy);
}


bestDist (int ourX, int ourY, int dx, int dy, int cols, int rows, int * wrap)
//
{
    int shortestDist;
    int northDist, southDist, eastDist, westDist;
    int wrapX; int wrapY; int base;

    *wrap = 0;

    shortestDist = simpleDist(dx, dy, ourX, ourY);

    // calculate distance if we wrap north.
    base = ourY;
    wrapX = cols - ourX + 1;
    wrapY = rows;
    northDist = simpleDist(wrapX, wrapY, dx, dy) + base;
    if (northDist <shortestDist)
    {
	shortestDist = northDist;
	*wrap = 1;
    }

    // calculate distance if we wrap south.
    base = rows - ourY + 1;
    wrapX = cols - ourX + 1;
    wrapY = 1;
    southDist = simpleDist(wrapX, wrapY, dx, dy) + base;
    if (southDist <shortestDist)
    {
	shortestDist = southDist;
	*wrap = 2;
    }

    // calculate distance if we wrap east.
    base = cols - ourX + 1;
    wrapX = 1;
    wrapY = rows - ourY + 1;
    eastDist = simpleDist(wrapX, wrapY, dx, dy) + base;
    if (eastDist <shortestDist)
    {
	shortestDist = eastDist;
	*wrap = 3;
    }

    // calculate distance if we wrap west.
    base = ourX;
    wrapX = cols;
    wrapY = rows - ourY + 1;
    westDist = simpleDist(wrapX, wrapY, dx, dy) + base;
    if (westDist <shortestDist)
    {
	shortestDist = westDist;
	*wrap = 4;
    }

    return shortestDist;
}

char getPrimaryDir (int ourX, int ourY, int dx, int dy, int cols, int rows)
{
    int deltaX, deltaY;
    int bar;
    int wrapdir;
    bar = bestDist (ourX, ourY, dx, dy, cols, rows, &wrapdir);

    if (wrapdir != 0)
	switch (wrapdir)
	{
	case 1:
	    return 'N';
	    break;
	case 2:
	    return 'S';
	    break;
	case 3:
	    return 'E';
	    break;
	case 4:
	    return 'W';
	    break;
	default:
	    break;
	}

    // calculate difference in X and Y
    deltaX = dx - ourX;
    deltaY = dy - ourY;

    if (abs(deltaX) > abs(deltaY))
	// then E or W is primary
	if (deltaX > 0)
	    return 'E';
	else
	    return 'W';
    else
	// then N or S is primary
	if (deltaY > 0)
	    return 'S';
	else
	    return 'N';
    return 'D';
}

char dumpPD (int status[1000][ST_SIZE], struct minfo * theMatrix,
	     int bx, int by)
{
    int curX, curY;
    for (curY = 1; curY <= theMatrix->rows; curY++)
    {
	for (curX = 1; curX <= theMatrix->cols; curX++)
	    fprintf (stderr, "%c", 
		getPrimaryDir (bx, by, curX, curY, theMatrix->cols,
			       theMatrix->rows));
	putc('\n', stderr); 
    }
    fflush (stderr);
    // sleep (3);
}


int distFromUs(int status[1000][ST_SIZE], 
	       struct minfo * theMatrix, int dx, int dy)
{
    int ourNum = theMatrix->ourNum - 1;
    int ourX = status[ourNum][ST_COL];
    int ourY = status[ourNum][ST_ROW];
    int cols = theMatrix->cols;
    int rows = theMatrix->rows;
    int foo;

    return bestDist (ourX, ourY, dx, dy, cols, rows, &foo);
}

void dumpDist (int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    int curX, curY;
    for (curY = 1; curY <= theMatrix->rows; curY++)
    {
	for (curX = 1; curX <= theMatrix->cols; curX++)
	    fprintf (stderr, "%02d ", distFromUs(status, theMatrix, curX, curY));
	putc('\n', stderr); 
    }
    // sleep (3);
}

//
// determine index into the matrix 1D array based on the status feedback for ourself
//
int ourCellIndex(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    return matrixLoc(theMatrix, status[theMatrix->ourNum - 1][ST_ROW] - 1,
				status[theMatrix->ourNum - 1][ST_COL] - 1);
}

//
// Return the food at our current location '@' if none
//
int ourCellContents(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    return theMatrix->matrix[ourCellIndex(status, theMatrix)];
}

void updateMatrix(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    int curProg;
    int index;

    for (curProg = 0; curProg < theMatrix->numContestants; curProg++)
	if (status[curProg][ST_OPERATION] == 'C')
	    {
	    index = matrixLoc(theMatrix,
				status[curProg][ST_ROW] - 1,
				status[curProg][ST_COL] - 1
				);
	    theMatrix->matrix[index] = '@';
	    }
};

// x, y, operation (ascii value)
void readStatus(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    register int curLine;
    char operation;
    int numConvert;
    int numLines = theMatrix->numContestants;

    for (curLine = 0; curLine < numLines; curLine++)
    {
        numConvert = scanf("%d%d %c", &status[curLine][ST_COL],
				      &status[curLine][ST_ROW],
				      &operation);
	if (numConvert == 3)
	{
	    // fprintf(stderr, "location = %d,%d\n",
		    // status[curLine][ST_COL], status[curLine][ST_ROW]);
	    status[curLine][ST_OPERATION] = operation;
	}
	else
	{
	    fputs("Error reading status\n", stderr);
	    fprintf(stderr, "number of conversions = %d\n", numConvert);
	    exit (0);
	}
    }
    updateMatrix (status, theMatrix);
    // dumpMatrix(theMatrix, stderr);
    calcHist (theMatrix);
    calcThreshold (theMatrix);
};


void sendMove(char move, int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    int ourNum;
    (void) putchar (move);
    (void) fflush(stdout);
    ourNum = theMatrix->ourNum - 1;
    if (move == 'C')
	(void) fprintf (stderr, "pc2:%c - %d;%d\n", move
		       ,status[ourNum][ST_COL]
		       ,status[ourNum][ST_ROW]
		       );
    else
	(void) fprintf (stderr, "pc2:%c\n", move);
	;

    // sleep(1);
    // always read status after a move...
    readStatus(status, theMatrix);
}

int localFoodAvail(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    return ourCellContents(status, theMatrix) != '@';
}

int goodFood(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    return ourCellContents(status, theMatrix) > theMatrix->threshold;
}

void smartChomp(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    static timeToDisplay = 0;

    if (localFoodAvail(status, theMatrix) && goodFood(status, theMatrix))
    {
	sendMove('C', status, theMatrix);
	theMatrix->lastChompTime = 0;
    }
    else
	theMatrix->lastChompTime++;
#ifdef NEVER
	(void) fprintf (stderr, "pc2:Poor food at - %d;%d\n",
		       status[theMatrix->ourNum - 1][ST_COL]
		       ,status[theMatrix->ourNum - 1][ST_ROW]
		       );
    dumpDist (status, theMatrix);
#endif
    if (timeToDisplay++ > MATRIX_DISPLAY_INTERVAL)
    {
	dumpMatrix(theMatrix, stderr);
	// sleep (1);
	timeToDisplay = 0;
    }
}

goToTopCorner(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    while (status[theMatrix->ourNum - 1][ST_COL] > 1)
    {
	sendMove('W', status, theMatrix);
	smartChomp(status, theMatrix);
    }
    while (status[theMatrix->ourNum - 1][ST_ROW] > 1)
    {
	sendMove('N', status, theMatrix);
	smartChomp(status, theMatrix);
    }
}

void  initBD(int bestDirs [4][3][2])
{
    int x, y, z;
    for (x = 0; x < 4; x ++)
	for (y = 0; y < 3; y ++)
	    for (z = 0; z < 2; z ++)
		bestDirs[x][y][z] = 0;
}

int closestIndex(int status[1000][ST_SIZE], struct minfo * theMatrix,
		 int bestDirs [4][3][2], int bestIndex)
{
    int cx;
    int retval = 0;
    int bestDist = 999999;
    int curDist;

    for (cx = 0; cx < 3; cx++)
    {
	if (bestDirs[bestIndex][cx][0] == 0 || bestDirs[bestIndex][cx][1] == 0)
	    break; // abort if no more in that direction
	curDist = distFromUs(status, theMatrix, 
		             bestDirs[bestIndex][cx][0],
			     bestDirs[bestIndex][cx][1]);
	fprintf (stderr,
		 "Distance to goal %d, %d = %d\n",
		 bestDirs[bestIndex][cx][0],
		 bestDirs[bestIndex][cx][1],
		 curDist);
	if (curDist > bestDist)
	{
	    curDist = bestDist;
	    retval = cx;
	}
    }
    fflush (stderr);
    // sleep (2);
    return retval;
}

void makeMove(int status[1000][ST_SIZE], struct minfo * theMatrix)
{
    int curX, curY;
    char primaryDir;
    char foodValue;
    int ourNum = theMatrix->ourNum - 1;
    int ourX = status[ourNum][ST_COL];
    int ourY = status[ourNum][ST_ROW];
    int cols = theMatrix->cols;
    int rows = theMatrix->rows;
    double scores[4][3] = {-999999.09,-999999.09,-999999.09,-999999.09,
			   -999999.09,-999999.09,-999999.09,-999999.09,
			   -999999.09,-999999.09,-999999.09,-999999.09};
    int bestDirs[4][3][2];
    int dist;
    double curScore;
    int cs;
    int dirIndex;
    double northSum, southSum, eastSum, westSum;
    char goalFoodValue;
    int ci;

    // if we have a current goal just go that way if food still there.
    if (theMatrix->goalX && theMatrix->goalY)
    {
	goalFoodValue = theMatrix->matrix[matrixLoc(theMatrix,
						    theMatrix->goalY - 1,
						    theMatrix->goalX - 1)];
	if  (goalFoodValue > '@')
	{
	    primaryDir = getPrimaryDir (ourX, ourY, 
					theMatrix->goalX, theMatrix->goalY,
					cols, rows);
	    sendMove(primaryDir, status, theMatrix);
	    return;
	}
	if (theMatrix->goalX == ourX && theMatrix->goalY == ourY)
	{
	    theMatrix->goalX = 0;
	    theMatrix->goalY = 0;
	}
    }
    initBD(bestDirs);
    // Determine the most rewarding direction
    for (curY = 1; curY <= theMatrix->rows; curY++)
    {
	for (curX = 1; curX <= theMatrix->cols; curX++)
	{
	    foodValue = theMatrix->matrix[matrixLoc(theMatrix, curY - 1,
							curX - 1)];
	    if (foodValue > theMatrix->threshold && foodValue > '@')
	    {
	        dist = distFromUs(status, theMatrix, curX, curY);
		if (dist == 0)
		    break;
		primaryDir = getPrimaryDir (ourX, ourY, curX, curY, cols, rows);
		// quick shortcut if we are adjacent to something acceptable
		if (dist == 1 && foodValue > '@')
		{
		    sendMove(primaryDir, status, theMatrix);
		    return;
		}
		curScore = 5.0 * (foodValue - '@') + 1.0;
		curScore = curScore / (dist);
		// curScore = curScore / (dist);
		switch (primaryDir)
		{
		    case 'N':
			dirIndex = 0;
			break;
		    case 'S':
			dirIndex = 1;
			break;
		    case 'E':
			dirIndex = 2;
			break;
		    case 'W':
			dirIndex = 3;
			break;
		    default:
			dirIndex = 0;
			break;
		}
		if (curScore > scores[dirIndex][0])
		{   // new best score for this direction
		    scores[dirIndex][2] = scores[dirIndex][1];
		    bestDirs[dirIndex][2][0] = bestDirs[dirIndex][1][0];
		    bestDirs[dirIndex][2][1] = bestDirs[dirIndex][1][1];

		    scores[dirIndex][1] = scores[dirIndex][0];
		    bestDirs[dirIndex][1][0] = bestDirs[dirIndex][0][0];
		    bestDirs[dirIndex][1][1] = bestDirs[dirIndex][0][1];

		    scores[dirIndex][0] = curScore;
		    bestDirs[dirIndex][0][0] = curX;
		    bestDirs[dirIndex][0][1] = curY;
		}
		else if (curScore > scores[dirIndex][1])
		{  // new second best score
		    scores[dirIndex][2] = scores[dirIndex][1];
		    bestDirs[dirIndex][2][0] = bestDirs[dirIndex][1][0];
		    bestDirs[dirIndex][2][1] = bestDirs[dirIndex][1][1];

		    scores[dirIndex][1] = curScore;
		    bestDirs[dirIndex][1][0] = curX;
		    bestDirs[dirIndex][1][1] = curY;
		}
		else if (curScore > scores[dirIndex][2])
		{
		    scores[dirIndex][2] = curScore;
		    bestDirs[dirIndex][2][0] = curX;
		    bestDirs[dirIndex][2][1] = curY;
		}
	    }
	}
    }
    southSum = eastSum = westSum = northSum = 0.0;
    for (cs = 0; cs < 3; cs ++)
    {
	if (scores[0][cs] > -999999.09)
	    northSum += scores[0][cs];
	if (scores[1][cs] > -999999.09)
	    southSum += scores[1][cs];
	if (scores[2][cs] > -999999.09)
	    eastSum += scores[2][cs];
	if (scores[3][cs] > -999999.09)
	    westSum += scores[3][cs];
    }
    fprintf (stderr, "Sums = %f, %f, %f, %f\n", northSum, southSum, eastSum, westSum);
    fflush(stderr);
    if (northSum > southSum && northSum > eastSum && northSum > westSum)
    {
	sendMove('N', status, theMatrix);
	// set goal as closest north score
	ci = closestIndex(status, theMatrix, bestDirs, 0);
	theMatrix->goalX = bestDirs[0][ci][0];
	theMatrix->goalY = bestDirs[0][ci][1];
	fprintf (stderr, "New goal = %d, %d\n", theMatrix->goalX, theMatrix->goalY);
	fflush (stderr);
	// sleep (1);
    }
    else if (southSum > eastSum && southSum > westSum)
    {
	sendMove('S', status, theMatrix);
	ci = closestIndex(status, theMatrix, bestDirs, 1);
	theMatrix->goalX = bestDirs[1][ci][0];
	theMatrix->goalY = bestDirs[1][ci][1];
	fprintf (stderr, "New goal = %d, %d\n", theMatrix->goalX, theMatrix->goalY);
	fflush (stderr);
	// sleep (1);
    }
    else if (westSum > eastSum)
    {
	sendMove('W', status, theMatrix);
	ci = closestIndex(status, theMatrix, bestDirs, 3);
	theMatrix->goalX = bestDirs[3][ci][0];
	theMatrix->goalY = bestDirs[3][ci][1];
	fprintf (stderr, "New goal = %d, %d\n", theMatrix->goalX, theMatrix->goalY);
	fflush (stderr);
	// sleep (1);
    }
    else
    {
	sendMove('E', status, theMatrix);
	ci = closestIndex(status, theMatrix, bestDirs, 2);
	theMatrix->goalX = bestDirs[2][ci][0];
	theMatrix->goalY = bestDirs[2][ci][1];
	fprintf (stderr, "New goal = %d, %d\n", theMatrix->goalX, theMatrix->goalY);
	fflush (stderr);
	// sleep (1);
    }
}

int main(int argc, char * argv[])
{
    static FILE *mfile, *pfile;
    struct minfo theMatrix; // ha ha
    time_t startTime;

    static char *path;
    int plen;
    int score = -999999;
    int status[1000][ST_SIZE]; // x, y, operation (ascii value)
    int curRow, curCol;

    time(&startTime);

    srand48(startTime);

    if (!parseMatrix(stdin, &theMatrix))
    {
	(void) putchar ('D');
	exit (-1);
    }
    dumpMatrix(&theMatrix, stderr);
    theMatrix.threshold = '?'; // will chomp empty locations
    theMatrix.lastChompTime = 0; 
    theMatrix.goalX = 0;
    theMatrix.goalY = 0;

    readStatus(status, &theMatrix); // get initial status

    fprintf(stderr, "pc2:Hello, World!\n");
#ifdef NEVER
    dumpPD (status, &theMatrix, 1, 1);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 8, 1);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 1, 6);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 6, 6);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 1, 3);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 4, 1);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 8, 3);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 4, 6);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 2, 2);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 3, 3);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 4, 4);   putc('\n', stderr); 
    dumpPD (status, &theMatrix, 7, 5);   putc('\n', stderr); 
    fflush (stderr);
    sleep (1);
#endif

    for (;;)
    {
	do
	{
	    smartChomp(status, &theMatrix);
	    makeMove(status, &theMatrix);
	}
	while (theMatrix.lastChompTime < (2 * (theMatrix.rows + theMatrix.cols)));

	fprintf(stderr, "pc2:I got confused! GOING TO PLAN B (From outer space)!\007\n");
	smartChomp(status, &theMatrix);
	sleep (2);

	{
	    goToTopCorner(status, &theMatrix);
	    theMatrix.lastChompTime = 0; 

	    for (curRow = 0; curRow < theMatrix.rows ; curRow++)
	    {
		for (curCol = 1; curCol < theMatrix.cols ; curCol++)
		{
		    sendMove('E', status, &theMatrix);
		    smartChomp(status, &theMatrix);
		}
		sendMove('S', status, &theMatrix);
		smartChomp(status, &theMatrix);

		// sleep (1);

		curRow++;

		for (curCol = 1; curCol < theMatrix.cols ; curCol++)
		{
		    sendMove('W', status, &theMatrix);
		    smartChomp(status, &theMatrix);
		}

		sendMove('S', status, &theMatrix);
		smartChomp(status, &theMatrix);
		sleep (1);
	    }
	}
	while (theMatrix.lastChompTime < theMatrix.rows + theMatrix.cols);

	fprintf(stderr, "pc2:Too inefficient! GOING TO PLAN A!\007\n");
	smartChomp(status, &theMatrix);
	sleep (1);

    }
    sendMove('D', status, &theMatrix);
    (void) fputs ("pc2:Goodbye.\n", stderr);
    exit(0);
    return -1; // should never get here but gcc complains
}