/*
** This program executes a chompers tournament.
** It takes the following commandline arguments:
**
** ch [-start sx sy] [-delay sec] array.txt prog1dir prog2dir ...
**
** These are:
**
**    -start sx sy      The x and y location at which to start all entrants
**                              (optional)
**
**    -delay sec        The seconds to delay before starting the match
**                              (optional)
**
**    array.txt         The array file to use for the tournament.
**                           The array file is formatted as an integer
**                              width and height followed by one capital
**                              letter for each cell of the array.
**
**    prog1dir          The directory containing the first entrant
**
**    prog2dir          The directory containing the second entrant
**
**    ...               More directories for other entrants...
**
**
*/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <sys/types.h>
#include <signal.h>
#include <sys/wait.h>
#include <sys/time.h>
#include <fcntl.h>
#include <unistd.h>
#include <assert.h>

#ifndef PROGRAM_NAME
# define PROGRAM_NAME   "pc2"
#endif

#ifndef SECONDS_BEFORE_FIRST_MOVE
#ifdef DEBUG_TTS
#define SECONDS_BEFORE_FIRST_MOVE       1
#else
#define SECONDS_BEFORE_FIRST_MOVE       60
#endif
#endif

#define MICROS_PER_SECOND               1000000

#ifndef STARVATION_TIME
#define STARVATION_TIME                 ( 45 * MICROS_PER_SECOND )
#endif

static unsigned int __gotSigPipe = 0;

typedef struct {
        /*
        ** path-name for entrant
        */
    const char* dir;

        /*
        ** file pointers to communicate with this entrant
        */
    FILE* to;
    FILE* from;

        /*
        ** entrant's process-id
        */
    pid_t pid;

        /*
        ** status for entrant
        */
    unsigned int col;
    unsigned int row;
    char lastMove;

        /*
        ** the move the entrant has requested
        */
    char requestedMove;

        /*
        ** track the score
        */
    unsigned int score;

        /*
        ** amount of turn time until entrant starves
        */
    long timeToStarve;

#ifdef DEBUG_TTS
    long minTimeToStarve;
#endif
} Entrant;

static void
__SigPipeCatcher( int sig )
{
    if ( sig == SIGPIPE ) {
        __gotSigPipe = 1;
    }

    signal( sig, __SigPipeCatcher );
}

static int
__ReadArray( const char* file, char** arrp, unsigned int* wp, unsigned int* hp )
{
    FILE* fp = fopen( file, "rb" );
    unsigned int width;
    unsigned int height;
    char* array;
    char* ptr;
    unsigned int ii;

    if ( fp == NULL ) {
        (void)fprintf( stderr, "Unable to open array <%s>\n", file );
        return __LINE__;
    }

    if ( fscanf( fp, "%u %u", &width, &height ) != 2 ) {
        (void)fclose( fp );
        (void)fprintf( stderr, "Unable to read array width and height\n" );
        return __LINE__;
    }

    array = (char*)malloc( width * height );

    if ( array == NULL ) {
        (void)fclose( fp );
        (void)fprintf( stderr, "Cannot alloc %ux%u array.\n", width, height );
        return __LINE__;
    }

    for ( ii=0, ptr=array; ii < width * height; ++ii, ++ptr ) {
        int ch;

        do {

            ch = fgetc( fp );

            if ( ch == EOF ) {
                free( array );
                (void)fclose( fp );
                (void)fprintf( stderr, "Premature end of array\n" );
                return __LINE__;
            }

        } while ( isspace( ch ) );

        *ptr = ch;
    }

    (void)fclose( fp );

    *arrp = array;
    *wp = width;
    *hp = height;

    return 0;
}

static int
__InitEntrant( const char* dir, unsigned int c, unsigned int r, Entrant* e )
{
    int to[2];
    int from[2];
    FILE* toFP;
    FILE* fromFP;
    pid_t pid;
    int wstatus;

    if ( pipe( to ) != 0 ) {
        (void)fprintf( stderr, "Could not make pipe to %s\n", dir );
        return __LINE__;
    }

    if ( pipe( from ) != 0 ) {
        (void)close( to[0] );
        (void)close( to[1] );
        (void)fprintf( stderr, "Could not make pipe from %s\n", dir );
        return __LINE__;
    }

        /*
        ** Make sure no child processes ever get access to
        ** file descriptors for other child processes.
        */
    (void)fcntl( to[1], F_SETFD, fcntl( to[1], F_GETFD ) | FD_CLOEXEC );
    (void)fcntl( from[0], F_SETFD, fcntl( from[0], F_GETFD ) | FD_CLOEXEC );

        /*
        ** Make sure fflush() never hangs when we try to write
        ** to this guy.
        */
    /*(void)fcntl( to[1], F_SETFL, fcntl( to[1], F_GETFL ) | O_NONBLOCK );*/

    toFP = fdopen( to[1], "wb" );

    if ( toFP == NULL ) {
        (void)close( to[0] );
        (void)close( to[1] );
        (void)close( from[0] );
        (void)close( from[1] );
        (void)fprintf( stderr, "Could not make fp for pipe to %s\n", dir );
        return __LINE__;
    }

    fromFP = fdopen( from[0], "rb" );

    if ( fromFP == NULL ) {
        (void)close( to[0] );
        (void)fclose( toFP );
        (void)close( from[0] );
        (void)close( from[1] );
        (void)fprintf( stderr, "Could not make fp for pipe from %s\n", dir );
        return __LINE__;
    }

    pid = fork();

    if ( pid == (pid_t)-1 ) {
        (void)close( to[0] );
        (void)fclose( toFP );
        (void)fclose( fromFP );
        (void)close( from[1] );
        (void)fprintf( stderr, "Could not fork() for %s\n", dir );
        return __LINE__;
    }

    if ( pid == 0 ) {
        
        (void)fclose( toFP );
        (void)fclose( fromFP );

        if ( to[0] != STDIN_FILENO ) {
            if ( dup2( to[0], STDIN_FILENO ) < 0 ) {
                (void)fprintf( stderr, "Cannot dup2 to stdin for %s\n", dir );
                exit( __LINE__ );
            }
            (void)close( to[0] );
        }

        if ( from[1] != STDOUT_FILENO ) {
            if ( dup2( from[1], STDOUT_FILENO ) < 0 ) {
                (void)fprintf( stderr, "Cannot dup2 to stdout for %s\n", dir );
                exit( __LINE__ );
            }
            (void)close( from[1] );
        }

        if ( chdir( dir ) != 0 ) {
            (void)fprintf( stderr, "Cannot chdir to %s\n", dir );
            exit( __LINE__ );
        }

        (void)execl( PROGRAM_NAME, "(programming contest 1)", NULL );

        (void)fprintf( stderr, "Cannot exec %s\n", PROGRAM_NAME );
        exit( __LINE__ );

    }

    (void)close( to[0] );
    (void)close( from[1] );

        /*
        ** give the child a second to exec...
        ** if this isn't long enough, then the
        ** worst that's going to happen is that
        ** I'll assume this dude is alive until
        ** the first time I try to give it an
        ** update.
        */
    (void)sleep( 1 );

        /*
        ** see if the child is still alive
        */
    if ( waitpid( pid, &wstatus, WNOHANG ) != 0 ) {
        (void)close( to[1] );
        (void)close( from[0] );

        (void)kill( pid, SIGHUP );
            (void)sleep( 1 );
        (void)kill( pid, SIGTERM );
            (void)sleep( 1 );
        (void)kill( pid, SIGKILL );

        (void)fprintf( stderr, "Looks like I failed starting %s\n", dir );

        return __LINE__;
    }

        /*
        ** fill in the entrant's structure
        */
    e->dir = dir;

    e->pid = pid;

    e->to = toFP;
    e->from = fromFP;

    e->col = c;
    e->row = r;
    e->lastMove = 'N';

    e->requestedMove = '\0';

    e->score = 0;

    e->timeToStarve = STARVATION_TIME;
#ifdef DEBUG_TTS
    e->minTimeToStarve = e->timeToStarve;
#endif

    return 0;
}

static int
__DeInitEntrant( Entrant* e )
{
    int wstatus;

        /*
        ** close the connection to the process
        */
    (void)fclose( e->to );
    (void)fclose( e->from );

        /*
        ** give the process a second to wind down
        */
    (void)sleep( 1 );

        /*
        ** kill off the process
        */
    (void)kill( e->pid, SIGHUP );
        (void)sleep( 1 );
    (void)kill( e->pid, SIGTERM );
        (void)sleep( 1 );
    (void)kill( e->pid, SIGKILL );

        /*
        ** wait for the process to die
        */
    (void)waitpid( e->pid, &wstatus, 0 );

    return 0;
}

int
main( int argc, const char* argv[] )
{
    unsigned int width;
    unsigned int height;
    char* array;
    Entrant* entrants;
    unsigned int K;
    unsigned int sCol = 0;
    unsigned int sRow = 0;
    unsigned int curArg = 1;
    unsigned int ii;
    unsigned long turnCount = 0;
    unsigned int delay = SECONDS_BEFORE_FIRST_MOVE;

        /*
        ** don't need it... may as well save file descriptors
        */
    (void)close( STDIN_FILENO );

        /*
        ** Check for starting position arguments.
        */
    if ( argc - curArg > 3 ) {
        if ( !strcmp( argv[ curArg ], "-start" ) ) {
            char* ptr = NULL;

            sCol = strtol( argv[ curArg+1 ], &ptr, 10 );
            if ( ptr == argv[ curArg+1 ] ) {
                sCol = 0;
            }

            sRow = strtol( argv[ curArg+2 ], &ptr, 10 );
            if ( ptr == argv[ curArg+2 ] ) {
                sRow = 0;
            }

            curArg += 3;
        }
    }

    if ( argc - curArg > 2 ) {
        if ( !strcmp( argv[ curArg ], "-delay" ) ) {
            char* ptr = NULL;

            delay = strtol( argv[ curArg+1 ], &ptr, 10 );
            if ( ptr == argv[ curArg+1 ] ) {
                delay = SECONDS_BEFORE_FIRST_MOVE;
            }

            curArg += 2;
        }
    }

        /*
        ** Make sure there are still enough arguments
        */
    if ( argc - curArg < 2 ) {
        (void)fprintf( stderr,
		"Usage: %s [-start sx sy] [-delay n] array.txt prog1dir ...\n",
		argv[0]
	    );
        return __LINE__;
    }

        /*
        ** read the input array
        */
    if ( __ReadArray( argv[ curArg++ ], &array, &width, &height ) != 0 ) {
        return __LINE__;
    }

    (void)fprintf( stderr, ":::: Got %ux%u array\n", width, height );

        /*
        ** allocate space for entrants
        */
    entrants = (Entrant*)malloc( ( argc - curArg ) * sizeof(Entrant) );

    if ( entrants == NULL ) {
        free( array );
        (void)fprintf( stderr, "Cannot allocate %u entrants\n", ( argc - 2 ) );
        return __LINE__;
    }

        /*
        ** pick the initial cell for each entrant
        ** if they weren't specified
        */
    srandom( getpid() );

    if ( sCol == 0 ) {
        sCol = ( random() % width ) + 1;
    }
    if ( sRow == 0 ) {
        sRow = ( random() % height ) + 1;
    }

        /*
        ** prepare for faulty entrants
        */
    signal( SIGPIPE, __SigPipeCatcher );

        /*
        ** initialize each entrant
        */
    for ( ii=curArg, K=0; ii < argc; ++ii ) {
        Entrant* e = &entrants[K];

        if ( __InitEntrant( argv[ii], sCol, sRow, e ) == 0 ) {
            (void)fprintf( stderr, ":::: Got entrant %s\n", argv[ii] );
            ++K;
        }
    }

        /*
        ** if we initialized at least one entrant, then
        ** it's worth actually running the tournament.
        */
    if ( K > 0 ) {

        int foodLeft = width * height;
        int entrantsAlive = 0;
        
            /*
            ** send all of the entrants the initial data
            */
        for ( ii=0; ii < K; ++ii ) {
            Entrant* e = &entrants[ii];
            FILE* to = e->to;
            unsigned int yy;

            __gotSigPipe = 0;

                /*
                ** print entrant number and entrant count
                */
            (void)fprintf( to, "%d %d\n", ii+1, K );

                /*
                ** print array
                */
            (void)fprintf( to, "%d %d\n", width, height );

            for ( yy=0; yy < height; ++yy ) {
                unsigned int xx;

                for ( xx=0; xx < width; ++xx ) {
                    (void)fputc( array[ yy * width + xx ], to );
                }

                (void)fputc( '\n', to );
                (void)fflush( to );
            }

                /*
                ** if we are having trouble speaking to
                ** the entrant, then kill the entrant.
                */
            if ( fflush( to ) == EOF || __gotSigPipe ) {
                e->lastMove = 'D';
                (void)fprintf( stderr, ":::: Killing mute %s (%d)\n", e->dir,
                        __gotSigPipe );
            } else {
                ++entrantsAlive;
            }
        }

        (void)fprintf( stderr, ":::: Waiting for entrants to prepare\n" );

        (void)sleep( delay );

        (void)fprintf( stderr, ":::: Starting turns\n" );

        while ( entrantsAlive > 0 && foodLeft > 0 ) {
            
            struct timeval startTime;
            struct timeval endTime;
            long  deltaTime;

            ++turnCount;

#ifdef DEBUG_TTS
            if ( ( turnCount & 0x1FFF ) == 0 ) {
                for ( ii=0; ii < K; ++ii ) {
                    Entrant* e = &entrants[ii];
                    (void)fprintf( stderr, "%s minTimeToStarve = %lu\n",
                        e->dir, e->minTimeToStarve );
                    e->minTimeToStarve = e->timeToStarve;
                }
            }
#endif

                /*
                ** Loop through sending status and getting
                ** moves from each player.
                */
            for ( ii=0; ii < K; ++ii ) {
                Entrant* e = &entrants[ii];
                int cc;
                int jj;

                if ( e->lastMove == 'D' ) {
                    continue;
                }

                    /*
                    ** send the status of everyone
                    */
                __gotSigPipe = 0;

                for ( jj=0; jj < K; ++jj ) {
                    Entrant* d = &entrants[jj];

                    (void)fprintf( e->to, "%u %u %c\n",
                        d->col, d->row, d->lastMove );
                }

                if ( fflush( e->to ) == EOF || __gotSigPipe ) {
                    e->requestedMove = 'D';
                    continue;
                }

                    /*
                    ** Start the timer
                    */
                (void)gettimeofday( &startTime, 0 );

                    /*
                    ** Get the move
                    */
                cc = fread( &e->requestedMove, 1, 1, e->from );

                    /*
                    ** End the timer
                    */
                (void)gettimeofday( &endTime, 0 );

                    /*
                    ** Calculate the delta time
                    */
                deltaTime = ( endTime.tv_sec - startTime.tv_sec );
                deltaTime *= MICROS_PER_SECOND;
                deltaTime += ( endTime.tv_usec - startTime.tv_usec );

                if ( deltaTime == 0 ) {
                    deltaTime = 1;
                }

                e->timeToStarve -= deltaTime;
#ifdef DEBUG_TTS
                if ( e->timeToStarve < e->minTimeToStarve ) {
                    e->minTimeToStarve = e->timeToStarve;
                }
#endif

                if ( e->timeToStarve < 0 ) {
                    (void)fprintf( stderr, ":::: Starving %s\n", e->dir );
                    e->requestedMove = 'D';
                } else if ( cc != 1 ) {
                    (void)fprintf( stderr, ":::: Killing silent %s\n", e->dir );
                    e->requestedMove = 'D';
                } else {
                    switch ( e->requestedMove ) {
                    case 'N':
                    case 'S':
                    case 'E':
                    case 'W':
                    case 'C':
                    case 'D':
                        break;
                    default:
                        e->requestedMove = 'C';
                        break;
                    }
                }
            }

                /*
                ** do all moves simultaneously
                */
            for ( ii=0; ii < K; ++ii ) {
                Entrant* e = &entrants[ii];

                if ( e->lastMove == 'D' ) {

                    /*
                    ** Let dead dogs lie.
                    */

                } else if ( e->requestedMove == 'C' ) {
                    int spot = array[ ( e->row - 1 ) * width + e->col - 1 ];

                    if ( isupper( spot ) ) {
                        unsigned int k = 0;
                        unsigned int jj;

                            /*
                            ** count how many people are chomping
                            ** this spot
                            */
                        for ( jj=0; jj < K; ++jj ) {
                            Entrant* d = &entrants[jj];

                            if ( d->col == e->col && d->row == e->row
                            && d->requestedMove == 'C' ) {
                                ++k;
                            }
                        }

                        assert( k > 0 );

                            /*
                            ** update everyone else who is chomping
                            ** this spot
                            */
                        for ( jj=0; jj < K; ++jj ) {
                            Entrant* d = &entrants[jj];
                            if ( d->col == e->col && d->row == e->row
                            && d->requestedMove == 'C' ) {
                                d->score += ( spot - 'A' + k ) / k;
                                d->timeToStarve = STARVATION_TIME;
#ifdef DEBUG_TTS
                                d->minTimeToStarve = d->timeToStarve;
#endif
                            }
                        }

                            /*
                            ** clear this spot
                            */
                        array[ ( e->row - 1 ) * width + e->col - 1 ] = ' ';
                        --foodLeft;
                    }
                } else {
                    switch ( e->requestedMove ) {
                    case 'N':
                        e->row -= 1;
                        break;
                    case 'S':
                        e->row += 1;
                        break;
                    case 'E':
                        e->col += 1;
                        break;
                    case 'W':
                        e->col -= 1;
                        break;
                    default:
                        break;
                    }

                        /*
                        ** Projective plane wrap around
                        */
                    if ( e->row < 1 ) {
                        e->row = height;
                        e->col = width + 1 - e->col;
                    } else if ( e->row > height ) {
                        e->row = 1;
                        e->col = width + 1 - e->col;
                    } else if ( e->col < 1 ) {
                        e->row = height + 1 - e->row;
                        e->col = width;
                    } else if ( e->col > width ) {
                        e->row = height + 1 - e->row;
                        e->col = 1;
                    }
                }
            }

                /*
                ** Update each player's last move.
                ** and count the number of players
                ** who were alive at the start of
                ** this round.
                */
            entrantsAlive = 0;

            for ( ii=0; ii < K; ++ii ) {
                Entrant* e = &entrants[ii];

                if ( e->lastMove != 'D' ) {
                    e->lastMove = e->requestedMove;
                    ++entrantsAlive;
                }
            }
        }

        (void)fprintf( stderr, "::::: %lu turns\n", turnCount );
        if ( entrantsAlive > 0 ) {
            (void)fprintf( stderr, "::::: %d entrants alive\n", entrantsAlive );
        }
        if ( foodLeft > 0 ) {
            (void)fprintf( stderr, "::::: %d food left\n", foodLeft );
        }

            /*
            ** clean up all of the entrants
            */
        for ( ii=0; ii < K; ++ii ) {
            Entrant* e = &entrants[ii];
            (void)fprintf( stdout, "%s:%u\n", e->dir, e->score );
            (void)__DeInitEntrant( e );
        }
    }

        /*
        ** clean up
        */

    free( entrants );
    free( array );

    return 0;
}