////////////////////////////////////////////////////////////////
//  *** Filbert_Einstein ***                                  //
//                                                            //
//  a.k.a. DoomsDray                                          //
//  a.k.a. Trial_by_Scurry                                    //
//  a.k.a. Cheek_Full_O_Nuts                                  //
//                                                            //
//  Copyright (C) 2004 - William Little                       //
//  Limited right to publish granted to Fred Hicinbothem.     //
//  All other rights reserved.                                //
////////////////////////////////////////////////////////////////

//Defines
#define SWAP(x,y) { int temp=(y)-(x); y=(x); x+=temp; } //Swaps ints & ptrs
#define ITERATION_LIMIT 1000000
#define TIME_LIMIT      58
#define NUT_VALUE       232792560   //The value of one nut
#define RANDOM_FACTOR   100000      //The limit of random value skew

//Includes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#include <assert.h>

//Random number code
#define myrand() ((unsigned int)((myrandseed=myrandseed*1684056135+342964307)>>33))
#define myseed(x) myrandseed=((unsigned long long)(x))<<33;
unsigned long long myrandseed=1ULL<<33;

//Globals
int NumNuts, *NutX, *NutY, NumSquirrels, *SquirrelX, *SquirrelY,
    StartX, StartY, BoardSize, *NutTime, *NutSplit, *NutActive, ActiveNuts;

//Prototypes
void SingleSquirrelGame(void);
void MultiSquirrelGame(void);
int Recurse(int x, int y, int held, int t, int depth);
int Distance(int x1, int y1, int x2, int y2);
int Evaluate(int x, int y, int *path);
int InitializeBoard(FILE *fp);
void CleanUp(void);
int GeneratePath(int *result);
void OutputMove(int x, int y);
void WritePath(int *path);
int ReadPath(int *path);

int main(int argc, char *argv[])
{
    //Initialize the random number generator
    myseed(time(0));

    //Read in the game board state, and initialize globals
    int rc;
    assert(argc==2);
    FILE *fp=fopen(argv[1],"rt");
    assert(fp);
    rc=InitializeBoard(fp);
    assert(rc==0);
    rc=fclose(fp);
    assert(rc==0);

    //Call the appropriate engine for this game
    if(NumSquirrels==1)
      SingleSquirrelGame();
    else
      MultiSquirrelGame();

    //Clean up and shut down
    CleanUp();
    return(0);
}

//The main routine for single squirrel games (POTM #1)
void SingleSquirrelGame(void)
{
    //Allocate variables
    int *path=new int[NumNuts];
    assert(path);
    int *bestpath=new int[NumNuts];
    assert(bestpath);
    int bestscore=INT_MAX;

    switch(NumNuts)
    {
        //Special case for 1 nut
        case 1:
        *bestpath=0;
        break;

        //Special case for 2 nuts
        case 2:
        if(Distance(StartX,StartY,NutX[0],NutY[0])<=
           Distance(StartX,StartY,NutX[1],NutY[1]))
        {
            bestpath[0]=0;
            bestpath[1]=1;
        } else
        {
            bestpath[0]=1;
            bestpath[1]=0;
        }
        break;

        //Normal case
        default:
        //Read previous best path from the temporary file, and adjust as needed
        if(!ReadPath(bestpath))
          bestscore=Evaluate(StartX,StartY,bestpath);

        //Keep trying to make a better path until the time limit is reached
        while(clock()<(TIME_LIMIT*CLOCKS_PER_SEC))
        {
            int score=GeneratePath(path);
            if(score<bestscore)
            {
                bestscore=score;
                memcpy((void *)bestpath,(void *)path,sizeof(int)*NumNuts);
            }
        }

        //Write the new best path to the temporary file
        WritePath(bestpath);
    }

    //Output our move
    OutputMove(NutX[bestpath[0]],NutY[bestpath[0]]);

    //Cleanup and terminate
    delete [] bestpath;
    delete [] path;
}

//The main routine for multi-squirrel games (POTM #2)
void MultiSquirrelGame(void)
{
    //Allocate and initialize variables
    NutTime=new int [NumNuts];
    assert(NutTime);
    for(int i=0;i<NumNuts;i++)
      NutTime[i]=INT_MAX;
    NutSplit=new int [NumNuts];
    assert(NutSplit);
    NutActive=new int [NumNuts];
    assert(NutActive);

    //Guess where all the other squirrels are likely to go
    for(int s=NumSquirrels-1;s>0;s--)
    {
        for(int i=0;i<NumNuts;i++)
          NutActive[i]=1;
        int t=0, x=SquirrelX[s], y=SquirrelY[s];
        for(ActiveNuts=NumNuts;ActiveNuts>0;ActiveNuts--)
        {
            int bestnut, bestscore=-1, bestdist;
            for(int i=0;i<NumNuts;i++)
              if(NutActive[i])
              {
                int dist=Distance(x,y,NutX[i],NutY[i]), score=0;
                if((t+dist)<=NutTime[i])
                {
                    score=NUT_VALUE/dist;
                    if((t+dist)==NutTime[i])
                      score/=NutSplit[i]+1;
                }
                score+=(myrand()%RANDOM_FACTOR);
                if(score>bestscore)
                {
                    bestscore=score;
                    bestdist=dist;
                    bestnut=i;
                }
              }

            //Update various variables to reflect this squirrel's move
            x=NutX[bestnut];
            y=NutY[bestnut];
            t+=bestdist;
            NutActive[bestnut]=0;
            if(t<NutTime[bestnut])
            {
                NutTime[bestnut]=t;
                NutSplit[bestnut]=1;
            } else NutSplit[bestnut]++;
        }
    }

    //Knowing where other squirrels are likely to go, and when
    //they're likely to arrive, choose a nut toward which to
    //head, using 3-ply lookahead, attempting to maximize our
    //average gain per move.
    for(int i=0;i<NumNuts;i++)
      NutActive[i]=1;
    ActiveNuts=NumNuts-1;
    int bestnut, bestscore=-1;
    for(int i=0;i<NumNuts;i++)
    {
        int dist=Distance(StartX,StartY,NutX[i],NutY[i]), gain=0;
        if(dist<=NutTime[i])
        {
            gain=NUT_VALUE;
            if(dist==NutTime[i])
              gain/=NutSplit[i]+1;
        }
        NutActive[i]=0;
        int score=Recurse(NutX[i],NutY[i],gain,dist,2);
        NutActive[i]=1;
        if(score>bestscore)
        {
            bestscore=score;
            bestnut=i;
        }
    }
    
    //Output our move
    OutputMove(NutX[bestnut],NutY[bestnut]);

    //Clean up
    delete [] NutActive;
    delete [] NutSplit;
    delete [] NutTime;
}

//The recursion engine for the 3-ply move-tree search
int Recurse(int x, int y, int held, int t, int depth)
{
    if((!ActiveNuts) || (!depth))
      return(held/t+(myrand()%RANDOM_FACTOR));
    depth--;
    int bestscore=-1;
    for(int i=0;i<NumNuts;i++)
      if(NutActive[i])
      {
        //Calculate the Estimated Time of Arrival at the nut in question
        int eta;
        {
            //Inline Distance() code for speed
            register int x2=NutX[i], y2=NutY[i];
            x2=(x>x2)?(x-x2):(x2-x);
            y2=(y>y2)?(y-y2):(y2-y);
            eta=t+((x2>y2)?x2:y2);
        }

        //Calculate the probable gain for the nut in question
        int gain=0;
        if(eta<=NutTime[i])
        {
            gain=NUT_VALUE;
            if(eta==NutTime[i])
              gain/=NutSplit[i]+1;
        }

        //Combine these values along with future potential to form the score
        int score;
        if(depth>0)
        {
            //We are a branch
            NutActive[i]=0;
            ActiveNuts--;
            score=Recurse(NutX[i],NutY[i],held+gain,eta,depth);
            ActiveNuts++;
            NutActive[i]=1;
        } else
        {
            //We are a leaf
            score=(held+gain)/eta+(myrand()%RANDOM_FACTOR);
        }
        if(score>bestscore)
          bestscore=score;
      }
    assert(bestscore>=0);
    return(bestscore);
}

int Distance(int x1, int y1, int x2, int y2)
{
    register int xd=(x1>x2)?(x1-x2):(x2-x1),
                 yd=(y1>y2)?(y1-y2):(y2-y1);
    return((xd>yd)?xd:yd);
}

int Evaluate(int x, int y, int *path)
{
    register int total=0;
    for(int i=0;i<NumNuts;i++)
    {
        {
            register int a=NutX[*path], b=NutY[*path];
            a=(x>a)?(x-a):(a-x);
            b=(y>b)?(y-b):(b-y);
            total+=(a>b)?a:b;
        }
        x=NutX[*path];
        y=NutY[*path];
        path++;
    }
    return(total);
}

//Read in the game board state, and initialize globals
int InitializeBoard(FILE *fp)
{
    char buf[100];
    int x, y, yous=0, sizes=0;

    NumNuts=NumSquirrels=0;
    while(!feof(fp))
    {
        int rc=fscanf(fp,"%[a-zA-Z]=%d,%d\n",buf,&x,&y);
        if(rc!=3)
          break;
        if(strcasecmp(buf,"NUT")==0)
          NumNuts++;
        if(strcasecmp(buf,"SQUIRREL")==0)
          NumSquirrels++;
    }
    NutX=new int[NumNuts];
    assert(NutX);
    NutY=new int[NumNuts];
    assert(NutY);
    SquirrelX=new int[NumSquirrels];
    assert(SquirrelX);
    SquirrelY=new int[NumSquirrels];
    assert(SquirrelY);
    rewind(fp);
    int n=0, s=0;
    while(!feof(fp))
    {
        int rc=fscanf(fp,"%[a-zA-Z]=%d,%d\n",buf,&x,&y);
        if(rc!=3)
          break;
        if(strcasecmp(buf,"NUT")==0)
        {
            NutX[n]=x;
            NutY[n]=y;
            n++;
        }
        else if(strcasecmp(buf,"SQUIRREL")==0)
        {
            SquirrelX[s]=x;
            SquirrelY[s]=y;
            s++;
        }
        else if(strcasecmp(buf,"YOU")==0)
        {
            StartX=x;
            StartY=y;
            yous++;
        }
        else if(strcasecmp(buf,"SIZE")==0)
        {
            assert(x==y);
            BoardSize=x+1;
            sizes++;
        }
    }
    assert(n==NumNuts);
    assert(s==NumSquirrels);
    assert(yous==1);
    assert(sizes==1);
    
    //Make sure we are the first Squirrel in the list
    for(s=0;s<NumSquirrels;s++)
      if((SquirrelX[s]==StartX)&&(SquirrelY[s]==StartY))
      {
        SWAP(SquirrelX[0],SquirrelX[s]);
        SWAP(SquirrelY[0],SquirrelY[s]);
        break;
      }
    assert(s<NumSquirrels);

    return(0);
}

void CleanUp(void)
{
    delete [] SquirrelY;
    delete [] SquirrelX;
    delete [] NutY;
    delete [] NutX;
}

//Come up with a good, short path through all the nuts
int GeneratePath(int *result)
{
    //Create a path through all the nuts in random order
    for(int i=0;i<NumNuts;i++)
      result[i]=i;
    for(int i=0;i<NumNuts;i++)
    {
        int a=myrand()%(NumNuts-i)+i;
        SWAP(result[i],result[a]);
    }

    //Insert the nuts, one by one
    for(int j=1;j<NumNuts;j++)
    {
        //Find an insertion point with the minimal detour
        int bestposition=j,
            bestdistance=Distance(NutX[result[j-1]],NutY[result[j-1]],
                                  NutX[result[j]],NutY[result[j]]);
        for(int i=j-1;i>0;i--)
        {
            int newdistance=Distance(NutX[result[i-1]],NutY[result[i-1]],
                                     NutX[result[j]],NutY[result[j]])+
                            Distance(NutX[result[j]],NutY[result[j]],
                                     NutX[result[i]],NutY[result[i]])-
                            Distance(NutX[result[i-1]],NutY[result[i-1]],
                                     NutX[result[i]],NutY[result[i]]);
            if(newdistance<bestdistance)
            {
                bestdistance=newdistance;
                bestposition=i;
            }
        }
        int newdistance=Distance(NutX[StartX],NutY[StartY],
                                 NutX[result[j]],NutY[result[j]])+
                        Distance(NutX[result[j]],NutY[result[j]],
                                 NutX[result[0]],NutY[result[0]])-
                        Distance(NutX[StartX],NutY[StartY],
                                 NutX[result[0]],NutY[result[0]]);
        if(newdistance<bestdistance)
        {
            bestdistance=newdistance;
            bestposition=0;
        }

        //Move it into position
        {
            int *first=result+bestposition, *last=result+j;
            assert(first<=last);
            int temp=*last;
            for(;first<last;last--)
              *last=*(last-1);
            *first=temp;
        }
    }

    //Evolve through mutation
    int *path=new int[NumNuts];
    assert(path);
    int resultscore=Evaluate(StartX,StartY,result);
    int iterations=0, timecounter=1000;
    while(iterations<ITERATION_LIMIT)
    {
        if(!(--timecounter))
        {
            timecounter=1000;
            if(clock()>=(TIME_LIMIT*CLOCKS_PER_SEC))
              break;
        }
        iterations++;
        memcpy((void *)path,(void *)result,sizeof(int)*NumNuts);
        {
            //Mutate by reversing a section at random
            register int *first=path+(myrand()%NumNuts), *last=path+(myrand()%NumNuts);
            if(first>last)
              SWAP(first,last);
            //If the reversal's going to make things worse, skip it.
            {
                int x1=StartX, y1=StartY, x2=NutX[*first], y2=NutY[*first],
                    x3=NutX[*last], y3=NutY[*last];
                if(first>path)
                {
                    x1=NutX[*(first-1)];
                    y1=NutY[*(first-1)];
                }
                if((last+1)==(path+NumNuts))
                {
                    if(Distance(x1,y1,x2,y2)<Distance(x1,y1,x3,y3))
                      continue;
                } else
                {
                    int x4=NutX[*(last+1)], y4=NutY[*(last+1)];
                    if((Distance(x1,y1,x2,y2)+Distance(x3,y3,x4,y4))<
                       (Distance(x1,y1,x3,y3)+Distance(x2,y2,x4,y4)))
                      continue;
                }
            }
            //Perform the reversal
            while(last>first)
            {
                SWAP(*first,*last);
                first++;
                last--;
            }
        }
        int score=Evaluate(StartX,StartY,path);
        assert(score<=resultscore);
        if(score<resultscore)
        {
            iterations=0;
        }
        resultscore=score;
        memcpy((void *)result,(void *)path,sizeof(int)*NumNuts);
    }
    delete [] path;
    return(resultscore);
}

//Print the move to stdout
void OutputMove(int x, int y)
{
    //Find a square next to the starting square, but closer to the goal
    if(x>StartX)
      x=StartX+1;
    else if(x<StartX)
      x=StartX-1;
    else
      x=StartX;
    if(y>StartY)
      y=StartY+1;
    else if(y<StartY)
      y=StartY-1;
    else
      y=StartY;

    //Output the new square
    printf("%d,%d\n",x,y);
}

//Write a path to the temporary file
void WritePath(int *path)
{
    int rc;
    FILE *fp=fopen("bestpath","wt");
    assert(fp);
    for(int i=0;i<NumNuts;i++)
    {
        rc=fprintf(fp,"%d,%d\n",NutX[path[i]],NutY[path[i]]);
        assert(rc>0);
    }
    rc=fclose(fp);
    assert(rc==0);
}

//Read a path from the temporary file, and determine it's relevancy
//Returns zero if successful
int ReadPath(int *path)
{
    int rc;
    int *nutuses=new int[NumNuts];
    assert(nutuses);
    for(int i=0;i<NumNuts;i++)
      nutuses[i]=0;

    //Read the temporary file
    FILE *fp=fopen("bestpath","rt");
    if(!fp)
    {
        delete [] nutuses;
        return(1);
    }
    for(int j=0;(j<NumNuts)&&(!feof(fp));j++)
    {
        //Read in a coordinate pair
        int x, y;
        rc=fscanf(fp,"%d,%d\n",&x,&y);
        if(rc!=2)
          break;

        //Determine which nut is on this square, and add it to the path
        for(int i=0;i<NumNuts;i++)
          if((x==NutX[i])&&(y==NutY[i]))
          {
            *(path++)=i;
            nutuses[i]++;
          }
    }
    rc=fclose(fp);
    assert(rc==0);

    //Make sure all nuts have been used exactly once
    for(int i=0;i<NumNuts;i++)
      if(nutuses[i]!=1)
      {
        delete [] nutuses;
        return(1);
      }

    //Success
    delete [] nutuses;
    return(0);
}