#include <stdio.h>
#include <strings.h> 
#include <stdlib.h>

#define NORTH 0
#define SOUTH 1
#define EAST  2
#define WEST  3

struct minfo
{
    int **movePenalty[4]; // direction, row, col
    int **visits; // row, col
    char *matrix;
    int rows, cols;
};

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

    int const maxpath = 2097152;
    static char path[2097152];
    int plen;
    int score = -999999;

    if (argc < 3)
    {
	(void) puts ("Usage: test matrixfile pathfile");
	exit (-1);
    }
    if (!openFiles(&mfile, &pfile, argv))
	exit (-2);
    if (!parseMatrix(mfile, &theMatrix))
	exit (-3);
    (void) fclose(mfile);
    dumpMatrix(&theMatrix);
    if ((plen = parsePath(pfile, path, maxpath)) < 2)
    {
	puts ("Path too short");
	exit (-4);
     }
    (void) fclose(pfile);
    (void) printf ("Path = <%s>\nlen = %d\n", path, plen);
    fflush (stdout);
    score = checkPath(&theMatrix, path, plen);
    (void) printf ("The score is %d\n", score);
    exit(0);
    return -1; // should never get here but gcc complains
}

//
//
//
int calcVisitValue (struct minfo *theMatrix, int curRow, int curCol)
{
    int retval = 2 - (1 << theMatrix->visits[curRow][curCol]);
    if (retval < 3)
	return retval;
    else
	return -2097152;
}

// Determine changes in score for the move (and progress one
//
// Accounts for out of bounds move penalty
// and box visit score adjustments
//
int doMove (struct minfo *theMatrix, char movetype, int *curRowPtr, int *curColPtr)
{
    int score = 0;
    printf ("Moving %c : ", movetype);
    switch (movetype)
    {
	case 'N':
	    score += theMatrix->movePenalty[NORTH][*curRowPtr][*curColPtr];
	    (*curRowPtr)--;
	    break;
	case 'S':
	    score += theMatrix->movePenalty[SOUTH][*curRowPtr][*curColPtr];
	    (*curRowPtr)++;
	    break;
	
	case 'W':
	    score += theMatrix->movePenalty[WEST][*curRowPtr][*curColPtr];
	    (*curColPtr)--;
	    break;
	case 'E':
	    score += theMatrix->movePenalty[EAST][*curRowPtr][*curColPtr];
	    (*curColPtr)++;
	    break;
    }


    if (*curRowPtr < 0)
    {
	*curRowPtr = 0;
#ifdef BOUNDRY_PENALTY
	score -= 5;
#endif
    }

    if (*curRowPtr >= theMatrix->rows)
    {
	*curRowPtr = theMatrix->rows - 1;
#ifdef BOUNDRY_PENALTY
	score -= 5;
#endif
    }

    if (*curColPtr < 0)
    {
	*curColPtr = 0;
#ifdef BOUNDRY_PENALTY
	score -= 5;
#endif
    }

    if (*curColPtr >= theMatrix->cols)
    {
	*curColPtr = theMatrix->cols - 1;
#ifdef BOUNDRY_PENALTY
	score -= 5;
#endif
    }

    printf ("now at %d, %d\n", *curRowPtr, *curColPtr);
    printf ("visit value = %d\n", calcVisitValue(theMatrix,
						*curRowPtr, *curColPtr));
    return score + calcVisitValue(theMatrix, *curRowPtr, *curColPtr);
}

int matrixLoc(struct minfo *theMatrix, int row, int col)
{
    return row * theMatrix->cols + col;
}

int calcPenalty(struct minfo *theMatrix, int curRow, int curCol, 
				       int deltaRow, int deltaCol)
{
    int matrixCell = matrixLoc(theMatrix, curRow, curCol);
    int adjacentCell = matrixLoc(theMatrix, deltaRow, deltaCol);

    if (theMatrix->matrix[adjacentCell] < theMatrix->matrix[matrixCell])
	return -5;
    else 
	return 0;
}

void buildVisits (struct minfo *theMatrix)
{
    int curRow, curCol;

    theMatrix->visits = (int **) malloc (sizeof(int *) * theMatrix->rows);

    for (curRow = 0; curRow < theMatrix->rows; curRow++)
	theMatrix->visits[curRow] = (int *) calloc (theMatrix->cols, sizeof(int));
}

void buildMovePenalty (struct minfo *theMatrix)
{
    int curRow, curCol;

    theMatrix->movePenalty[NORTH] = (int **) 
	malloc (sizeof(int *) * theMatrix->rows);
    theMatrix->movePenalty[SOUTH] = (int **) 
	malloc (sizeof(int *) * theMatrix->rows);
    theMatrix->movePenalty[EAST]  = (int **) 
	malloc (sizeof(int *) * theMatrix->rows);
    theMatrix->movePenalty[WEST]  = (int **) 
	malloc (sizeof(int *) * theMatrix->rows);

    for (curRow = 0; curRow < theMatrix->rows; curRow++)
    {
	theMatrix->movePenalty[NORTH][curRow] = (int *) calloc (theMatrix->cols,
						     sizeof(int));
	theMatrix->movePenalty[SOUTH][curRow] = (int *) calloc (theMatrix->cols,
						     sizeof(int));
	theMatrix->movePenalty[EAST][curRow]  = (int *) calloc (theMatrix->cols,
						     sizeof(int));
	theMatrix->movePenalty[WEST][curRow]  = (int *) calloc (theMatrix->cols,
						     sizeof(int));
    }
    for (curRow = 0; curRow < theMatrix->rows; curRow++)
	for (curCol = 0; curCol < theMatrix->cols; curCol++)
	{
	if (curRow > 0)
	    theMatrix->movePenalty[NORTH][curRow][curCol] = calcPenalty(theMatrix,
							     curRow, curCol,
							     curRow-1, curCol);
	else
	    theMatrix->movePenalty[NORTH][curRow][curCol] = 0;
	if (curRow < theMatrix->rows - 1)
	    theMatrix->movePenalty[SOUTH][curRow][curCol] = calcPenalty(theMatrix,
							     curRow, curCol,
							     curRow+1, curCol);
	else
	    theMatrix->movePenalty[SOUTH][curRow][curCol] = 0;
	if (curCol > 0)
	    theMatrix->movePenalty[WEST][curRow][curCol] = calcPenalty(theMatrix,
							     curRow, curCol,
							     curRow, curCol-1);
	else
	    theMatrix->movePenalty[WEST][curRow][curCol] = 0;
	if (curCol < theMatrix->cols - 1)
	    theMatrix->movePenalty[EAST][curRow][curCol] = calcPenalty(theMatrix,
							     curRow, curCol,
							     curRow, curCol+1);
	else
	    theMatrix->movePenalty[EAST][curRow][curCol] = 0;
	}
    for (curRow = 0; curRow < theMatrix->rows; curRow++)
	for (curCol = 0; curCol < theMatrix->cols; curCol++)
	{
	    printf ("[N|S|E|W][%d][%d] = %d,%d,%d,%d\n", curRow, curCol,
		    theMatrix->movePenalty[NORTH][curRow][curCol],
		    theMatrix->movePenalty[SOUTH][curRow][curCol],
		    theMatrix->movePenalty[EAST][curRow][curCol],
		    theMatrix->movePenalty[WEST][curRow][curCol]);
	}
}

//
// determine score for the path
//
int checkPath(struct minfo *theMatrix, char path[], const int pathlen)
{

    /* penalize for length of path but credit for first box */
    int score = -pathlen + 1; 
    int curRow = 0;
    int curCol = 0;
    int maxmoves = 2097152 * 16;
    int pathpos = 0;

    buildMovePenalty(theMatrix);
    buildVisits(theMatrix);

    theMatrix->visits[0][0] ++; /* initial cell is visited to start with */

    while (score > -1000000 && maxmoves-- && 
	   !(curRow == theMatrix->rows - 1 && curCol == theMatrix->cols -1))
    {
	score += doMove(theMatrix, path[pathpos], &curRow, &curCol);
	printf ("workScore = %d\n", score);
	pathpos++;
	if (pathpos >= pathlen)
	    pathpos = 0;
	theMatrix->visits[curRow][curCol] ++;
    }
    return score;
}

int parsePath( FILE *pfile, char path[], const int maxpath)
{
    int pathlen = 0;
    char workChar;

    while ((workChar = getc(pfile)) != EOF && pathlen < maxpath)
	switch (workChar)
	{
	    case 'N':
	    case 'S':
	    case 'E':
	    case 'W':
		path[pathlen++] = workChar;
	}
    return pathlen;
}

void dumpVisits(struct minfo *theMatrix)
{
    int curRow, curCol;

    for (curRow = 0; curRow < theMatrix->rows; curRow++)
	for (curCol = 0; curCol < theMatrix->cols; curCol++)
	    printf ("visits[%d][%d] = %d\n", curRow, curCol,
		    theMatrix->visits[curRow][curCol]);
}

int dumpMatrix(struct minfo *theMatrix)
{
    int curRow = 0, curCol = 0;
    char *curChar = theMatrix->matrix;

    for (; curRow < theMatrix->rows; curRow++)
    {
	for (curCol = 0; curCol < theMatrix->cols; curCol++)
	{
	    putchar(*curChar);
	    curChar++;
	}
	putchar('\n');
    }
    putchar('\n');
    fflush (stdout);
}

int parseMatrix(FILE *mfile, struct minfo *theMatrix)
{
    static char firstline[200] = "no line read";
    char *workPtr;
    int size, size2;
    int conversions;
    int curRow;

    theMatrix->rows = -1;
    theMatrix->cols = -1;

    if (!fgets (firstline, 190, mfile))
    {
	puts ("Can't read first line in matrix file");
	return 0;
    }
    if (!index(firstline, '\n'))
    {
	puts ("First line of matrix file too long");
	return 0;
    }
    if ((conversions = sscanf (firstline, "%d%d", &theMatrix->cols, &theMatrix->rows)) != 2)
    {
	puts ("Error reading cols and rows in matrix file");
	puts (firstline);
	printf ("number of conversions = %d\n", conversions);
	printf ("rows = %d, cols = %d\n", theMatrix->rows, theMatrix->cols);
	return 0;
    }
    printf ("rows = %d, cols = %d\n", theMatrix->rows, theMatrix->cols);
    size = theMatrix->cols * theMatrix->rows;
    if (size < 0 || theMatrix->rows < 1 || theMatrix->cols < 1)
    {
	puts ("Error invalid column/row specification");
	return 0;
    }
    theMatrix->matrix = (char *) malloc(size + 2);
    if (!theMatrix->matrix)
    {
	puts ("Cant allocate mem for matrix");
	return 0;
    }
    workPtr = theMatrix->matrix;
    for (curRow = 0; curRow < theMatrix->rows; curRow++)
    {
	/* add 1 for newline and 1 for null char */
	if (!fgets (workPtr, theMatrix->cols + 2, mfile))
	{
	    printf ("Error reading row %d of matrix", curRow + 1);
	    return 0;
	}
	workPtr += theMatrix->cols;
    }
    return 1;
}

int openFiles(FILE **mfile, FILE **pfile, const char *argv[])
{
    if (strcmp(argv[1], "-") == 0)
    {
	printf ("using stdin %s\n", argv[1]);
	fflush(stdout);
	*mfile = stdin;
    }
    else
    {
	printf ("Opening %s\n", argv[1]);
	*mfile = fopen (argv[1], "r");
    }
    printf ("Opening %s\n", argv[2]);
    *pfile = fopen (argv[2], "r");

    if (!*mfile || !*pfile)
    {
	puts ("Error opening files");
	if (mfile)
	    fclose (*mfile);
	if (pfile)
	    fclose (*pfile);
	return 0;
    }
    return 1;
}