/*  POTM ENTRY: whirligig                                       */
/*  Your Name:  Franz Korntner                                  */
/*  Your email: korntner@xs4all.nl                              */
/*  To:         enter@potm.ffast.att.com                        */
/*  Subject:    P E G G E D                                     */

/* !! This code MUST be compiled with GCC                       */

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <unistd.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/times.h>

#define XMAX (49+1)
#define YMAX (25+2)
#define MAXHASH 40000
#define MAXMEM 16000000
#define MAXROOT 300000 /* +- (distdelta*2) */
#define MAXSEC1 530
#define MAXSEC2 580

#define NOPEG   0x0000
#define BORDER  0x0001
#define LASTPEG 0x0FFF

struct node {
  struct node   *next, *nexthash, *nextscore;
  int           numpegs, nummove;
  int           numwalk, numjump;
  short         *pegs;
  short         *grid;
  long          score;
  int           start, startinx;
  unsigned long hash;
};

#define JUMPN 0x0000
#define JUMPE 0x1000
#define JUMPS 0x2000
#define JUMPW 0x3000
#define WALKN 0x4000
#define WALKE 0x5000
#define WALKS 0x6000
#define WALKW 0x7000

char            *xgrid;
int             xmax, ymax, xymax;
struct node     **root, **hash;
struct node     *freelist, *root1, **roottbl1, *root2, **roottbl2;
long            *scoreJN, *scoreJE, *scoreJS, *scoreJW;
long            *scoreWN, *scoreWE, *scoreWS, *scoreWW;
long            *hashJN,  *hashJE,  *hashJS,  *hashJW;
long            *hashWN,  *hashWE,  *hashWS,  *hashWW;
long            *startg, thestart;
int             numnodes, numtst, numdups, totdups, level;
int             rootmax, rootmin, nodesiz, distdelta, rootbase;
int             maxmem = MAXMEM;
int             maxnode;
int             allowtst = 40, allownew=15;
int             dflag;
struct node     *answer;
int             clktck;
struct tms      tms;

char            *walkg;
long            *distg;
long            *hashg;


#define XMALLOC(X,Y) X = xmalloc (Y*sizeof(*X))
#define ZMALLOC(X,Y) X = xmalloc (Y*sizeof(*X))

void *xmalloc (int size)
{
void *p;

  p = malloc (size);
  if (p == NULL) {
    fprintf (stderr, "Out of memory\n");
    exit(1);
  }
  maxmem -= size;
  return p;
}

void *zmalloc (int size)
{
void *p;

  p = malloc (size);
  if (p == NULL) {
    fprintf (stderr, "Out of memory\n");
    exit(1);
  }
  memset (p, 0, size);
  maxmem -= size;
  return p;
}

void dump_node (struct node *p)
{
int x, y, i, m;
short *g;

#ifdef DEBUG
  g = p->grid;
  for (y=0; y<ymax; y++) {
    for (x=0; x<xmax; x++)
      switch (*g++) {
        case NOPEG : printf("O"); break;
        case BORDER: printf("."); break;
        default    : printf(g[-1]<0?"o":"X"); break;
      }
    printf ("  ");
    if (y == 0)
      printf ("Score: %d jump:%d walk:%d", p->score, p->numjump, p->numwalk);
    printf ("\n");
  }
#if 0
  for (i=0; i<p->nummove; i++) {
    m = p->pegs[i];
    y = (m&0xFFF) / xmax;
    x = (m&0xFFF) % xmax;
    printf ("%d %d -> ", x, y);
    switch (m&0xF000) {
case JUMPN: printf("JUMPN\n");break;
case JUMPE: printf("JUMPE\n");break;
case JUMPS: printf("JUMPS\n");break;
case JUMPW: printf("JUMPW\n");break;
case WALKN: printf("WALKN\n");break;
case WALKE: printf("WALKE\n");break;
case WALKS: printf("WALKS\n");break;
case WALKW: printf("WALKW\n");break;
    }
  }
#endif
#endif
}

void solution (struct node *p)
{
int i, x, y, m;

#ifdef DEBUG
  dump_node (p);
  fprintf (stderr, "numwalk:%d Numjump:%d Totdups:%d\n", p->numwalk, p->numjump, totdups);
#endif

  for (i=0; i<p->nummove; i++) {
    m = p->pegs[i];
    y = (m&0xFFF) / xmax;
    x = (m&0xFFF) % xmax;
    printf ("%c%d ",  'A'-1+y, 1+x);
    switch (m&0xF000) {
      case JUMPN: y-=2;break;
      case JUMPE: x+=2;break;
      case JUMPS: y+=2;break;
      case JUMPW: x-=2;break;
      case WALKN: y-=1;break;
      case WALKE: x+=1;break;
      case WALKS: y+=1;break;
      case WALKW: x-=1;break;
    }
    printf ("%c%d\n",  'A'-1+y, 1+x);
  }
  exit(0);
}

struct node *new_node (struct node *orig, long newhash, long newscore, int move)
{
struct node *p;
long scoreval, hashval;
int i, x, y, m;

  /* test for existance of duplicate node */
  hashval = (newhash&0x7FFFFFFF) % MAXHASH;
  for (p=hash[hashval]; p; p=p->nexthash) {
    if (p->hash == newhash) {
      numdups++; totdups++;
      return NULL;
    }
  }

  /* Create new entry */
  if ((p=freelist) == NULL)
    return NULL;
  freelist = p->next;
  numnodes++;

  /* copy the contents */
  p->numpegs  = orig->numpegs;
  p->nummove = orig->nummove;
  p->numjump = orig->numjump;
  p->numwalk = orig->numwalk;
  p->score = newscore;
  p->hash  = newhash;
  p->start = orig->start;
  p->startinx = orig->startinx;
  memcpy (p->pegs,orig->pegs,p->nummove*sizeof(*p->pegs));
  memcpy (p->grid,orig->grid,xymax*sizeof(*p->grid));

  /* add move to list */
  p->pegs[p->nummove++] = move;

  /* ponder over the score */
  scoreval = newscore-rootbase;
  if (scoreval > rootmax) {
    if (scoreval >= distdelta)
      scoreval=distdelta-1;
    rootmax = scoreval;
  }
  if (scoreval < rootmin) {
    if (scoreval < 0)
      scoreval = 0;
    rootmin = scoreval;
  }

  /* Add to lists */
  p->nextscore = root[scoreval];
  root[scoreval] = p;
  p->nexthash = hash[hashval];
  hash[hashval] = p;

  return p;
}


int ff(int n)
{
static int result[400];


  if (n<=7) return n*n;
  if (result[n])
    return result[n];
  else
    return result[n] = ff(n-1)+ff(n-6)+ff(n-7)-ff(n-8)+1;

  return n*n*n;

  if (n<=0) return 1;
  if (n==1) return 2;
  if (n==2) return 3;
  return 2*ff(n-1)+ff(n-2)-ff(n-3)+1;
}

int initialize (char *fname)
{
FILE *f;
int ch, i, dist, start, peg;
int x, y, changed;
struct node *p;

  clktck = sysconf(_SC_CLK_TCK);

  /* Allocate structures */
  XMALLOC (xgrid, XMAX*YMAX);

  /* open the input file containing grid information */
  f = fopen (fname, "r");
  if (f == NULL)
    return -1;
 
  /* load the grid */
  xmax = ymax= 0;
  x = 0;
  y = 1;
  memset (xgrid, 'B', XMAX*YMAX*sizeof(*xgrid));
  while ((ch=fgetc(f)) != EOF) {
    switch (ch) {
      case 'X': case 'x':
        if (x+1 > xmax) xmax = x+1;
        if (y+1 > ymax) ymax = y+1;
        xgrid[y*XMAX+x] = 'X';
        x++;
        break;
      case 'O': case 'o':
        if (x+1 > xmax) xmax = x+1;
        if (y+1 > ymax) ymax = y+1;
        xgrid[y*XMAX+x] = 'O';
        x++;
        break;
      case '_':
        if (x+1 > xmax) xmax = x+1;
        if (y+1 > ymax) ymax = y+1;
        x++;
        break;
      default:
        x++;
        break;
      case '\n':
        y++;
        x = 0;
        break;
    }
  }
  fclose(f);

  /* don't forget the borders */
  xmax += 1;
  ymax += 1;
  xymax = xmax * ymax;

  nodesiz = sizeof(*p) + xymax*(2*sizeof(*p->pegs)+sizeof(*p->grid));
  maxnode = 700000 / xymax;
  if (maxnode > maxmem/nodesiz/2)
    maxnode = maxmem/nodesiz/2;
#ifdef DEBUG
  fprintf (stderr, "xymax:%d Nodesiz:%d Maxnode:%d\n", xymax, nodesiz, maxnode);
#endif

  /* create global structures */
  XMALLOC (roottbl1, MAXROOT);
  XMALLOC (roottbl2, MAXROOT);
  XMALLOC (hash, MAXHASH);

  /* create freelists */
  root1 = root2 = NULL;
  for (i=maxnode; i>=0; i--) {
    XMALLOC (p,1); p->next = root1; root1 = p;
  }
  for (i=maxnode; i>=0; i--) {
    XMALLOC (p,1); p->next = root2; root2 = p;
  }
  for (p=root1; p; p=p->next) {
    XMALLOC (p->pegs, xymax*2);
    XMALLOC (p->grid, xymax);
  }
  for (p=root2; p; p=p->next) {
    XMALLOC (p->pegs, xymax*2);
    XMALLOC (p->grid, xymax);
  }

  /* Create a new grid */
  p = root1;

  /* Calculate grid for walking */
  ZMALLOC(walkg, xymax);
  XMALLOC(distg, xymax);
  XMALLOC(startg,xymax);
  for (y=0; y<ymax; y++)
    for (x=0; x<xmax; x++)
      p->grid[y*xmax+x] = xgrid[y*XMAX+x] == 'B' ? BORDER : NOPEG;
  for(i=xymax-1; i>=0; i--)
    distg[i] = -1;

  /* mark center hole */
#ifdef DEBUG
  fprintf (stderr, "Center %c %d\n", 'A'-1+(ymax/2), 1+(xmax/2-1));
#endif
  peg = (ymax/2)*xmax+(xmax/2-1);
  distg[peg] = dist = 0;
  walkg[peg] = 0;
  startg[peg] = start = 0;
  p->grid[peg] = -LASTPEG;

  /* add holes, sorted in order of distance to center hole */
  do {
    /* preamble */
    changed = 0;
    dist++;

#define TSTPEG(N)               \
  if (distg[i+(N)]+1 == dist) { \
    distg[i] = dist;            \
    walkg[i] = N;               \
    startg[i] = ++start;        \
    p->grid[i] = -peg;          \
    peg = i;                    \
    changed++;                  \
  }

    /* scan for holes */
    for (y=0; y<ymax; y++) {
      for (x=0; x<xmax; x++) {
        i = y*xmax+x;
        if (p->grid[i] == NOPEG) {
          TSTPEG(-xmax) else TSTPEG(+xmax) else TSTPEG(-1) else TSTPEG(+1)
        }
      }
    }
  } while (changed);
  thestart = peg;

  /* adapt distance for scoring purposes */
  for (i=xymax-1; i>=0; i--)
    distg[i] = distg[i]*distg[i];

  distdelta = dist*dist + (dist-1)*(dist-1) - (dist-2)*(dist-2);
#ifdef DEBUG
  fprintf (stderr, "distdelta:%d %d\n", dist, distdelta);
#endif

  /* Get some random values for hashing */
  XMALLOC (hashg, xymax);
  for (i=xymax-1; i>=0; i--)
    hashg[i] = random();

  /* precalc frequent calculations */
  ZMALLOC (scoreJN, xymax);
  ZMALLOC (scoreJE, xymax);
  ZMALLOC (scoreJS, xymax);
  ZMALLOC (scoreJW, xymax);
  ZMALLOC (scoreWN, xymax);
  ZMALLOC (scoreWE, xymax);
  ZMALLOC (scoreWS, xymax);
  ZMALLOC (scoreWW, xymax);
  ZMALLOC (hashJN, xymax);
  ZMALLOC (hashJE, xymax);
  ZMALLOC (hashJS, xymax);
  ZMALLOC (hashJW, xymax);
  ZMALLOC (hashWN, xymax);
  ZMALLOC (hashWE, xymax);
  ZMALLOC (hashWS, xymax);
  ZMALLOC (hashWW, xymax);
  for (i=xymax-1; i>=0; i--) {
    if (distg[i] > 0) {
        scoreJN[i] = - distg[i] + distg[i-xmax] - distg[i+xmax];
        scoreJE[i] = - distg[i] + distg[i   +1] - distg[i   -1];
        scoreJS[i] = - distg[i] + distg[i+xmax] - distg[i-xmax];
        scoreJW[i] = - distg[i] + distg[i   -1] - distg[i   +1];
        scoreWN[i] = - distg[i] + distg[i-xmax];
        scoreWE[i] = - distg[i] + distg[i   +1];
        scoreWS[i] = - distg[i] + distg[i+xmax];
        scoreWW[i] = - distg[i] + distg[i   -1];
        hashJN[i]  = - hashg[i] + hashg[i-xmax] - hashg[i+xmax];
        hashJE[i]  = - hashg[i] + hashg[i   +1] - hashg[i   -1];
        hashJS[i]  = - hashg[i] + hashg[i+xmax] - hashg[i-xmax];
        hashJW[i]  = - hashg[i] + hashg[i   -1] - hashg[i   +1];
        hashWN[i]  = - hashg[i] + hashg[i-xmax];
        hashWE[i]  = - hashg[i] + hashg[i   +1];
        hashWS[i]  = - hashg[i] + hashg[i+xmax];
        hashWW[i]  = - hashg[i] + hashg[i   -1];
    }
  }

  /* Place the pegs */
  p->startinx = startg[p->start = thestart];
  p->score = 0;
  p->hash  = 0;
  p->numpegs = 0;
  p->nummove = 0;
  p->numwalk = 0;
  p->nummove = 0;
  for (y=0; y<ymax; y++) {
    for (x=0; x<xmax; x++) {
      if (xgrid[y*XMAX+x] == 'X') {
        i = y*xmax+x;
        p->grid[i] = -p->grid[i];
        p->score += distg[i];
        p->hash  += hashg[i];
        p->numpegs++;
      }
    }
  }

  /* display starting node */
  if (p) dump_node (p);

  return 0;
}


void gen_moves (struct node *orig)
{
register struct node *p;
register short *pegp, *newp;
register const max = xmax;
register int peg;
int found, count=allownew;

  numtst++;

  while (orig->grid[peg=orig->start] < 0)
    orig->startinx = startg[orig->start = -orig->grid[orig->start]];

  for (;;) {
    if (*(pegp=orig->grid+peg) > BORDER) {

      pegp     = orig->grid+peg;
      found = 0;

#define JUMP(FROM,TO,MOVE,NEWHASH,NEWSCORE)                             \
    if (pegp[FROM] > BORDER && pegp[TO] <= NOPEG) {                     \
      p = new_node(orig,                                                \
                   orig->hash +NEWHASH[peg],                            \
                   orig->score+NEWSCORE[peg],                           \
                   MOVE|(peg FROM));                                    \
      if (p != NULL) {                                                  \
        p->numjump++;                                                   \
        p->numpegs--;                                                   \
        found++;                                                        \
                                                                        \
        newp=p->grid+peg;                                               \
        newp[FROM] = -newp[FROM];                                       \
        *newp = -*newp;                                                 \
        newp[TO] = -newp[TO];                                           \
        if (p->startinx < startg[peg TO])                               \
          p->startinx = startg[p->start=peg TO];                        \
        if (p->numpegs==1)                                              \
          if (!answer || p->score < answer->score)                      \
            answer = p;                                                 \
      }                                                                 \
    }

#define WALK(TO,MOVE,NEWHASH,NEWSCORE)                                  \
    if (pegp[TO] <= NOPEG && NEWSCORE[peg]<0) {                         \
      p = new_node(orig,                                                \
                   orig->hash +NEWHASH[peg],                            \
                   orig->score+NEWSCORE[peg],                           \
                   MOVE|(peg));                                         \
      if (p != NULL) {                                                  \
        p->numwalk++;                                                   \
        found++;                                                        \
                                                                        \
        newp=p->grid+peg;                                               \
        *newp = -*newp;                                                 \
        newp[TO] = -newp[TO];                                           \
      }                                                                 \
    }

      JUMP(+max, -max, JUMPN,hashJN,scoreJN) else
      JUMP(-max, +max, JUMPS,hashJS,scoreJS)
      JUMP(  -1,   +1, JUMPE,hashJE,scoreJE) else
      JUMP(  +1,   -1, JUMPW,hashJW,scoreJW)

      if (found == 0) {
        WALK(-max, WALKN,hashWN,scoreWN)
        WALK(+max, WALKS,hashWS,scoreWS)
        WALK(  +1, WALKE,hashWE,scoreWE)
        WALK(  -1, WALKW,hashWW,scoreWW)
      }

      if (found && --count < 0)
        return;
      if ((peg=*pegp) == LASTPEG)
        break;
    } else {
      if ((peg=-*pegp) == LASTPEG)
        break;
    }
  }
}

void panic (struct node *p)
{
register short *pegp, *newp;
register const max = xmax;
register int peg;
int found;

  for (;;) {
    while (p->grid[peg=p->start] < 0)
      p->startinx = startg[p->start = -p->grid[p->start]];

  for (;;) {
    if (*(pegp=p->grid+peg) > BORDER) {

      pegp     = p->grid+peg;
      found = 0;

#undef JUMP
#define JUMP(FROM,TO,MOVE,NEWHASH,NEWSCORE)                             \
    if (pegp[FROM] > BORDER && pegp[TO] <= NOPEG) {                     \
        p->numjump++;                                                   \
        p->numpegs--;                                                   \
        p->score = p->score+NEWSCORE[peg];                              \
        p->hash  = p->hash +NEWHASH[peg];                               \
        p->pegs[p->nummove++] = MOVE|(peg FROM);                        \
                                                                        \
        newp=p->grid+peg;                                               \
        newp[FROM] = -newp[FROM];                                       \
        *newp = -*newp;                                                 \
        newp[TO] = -newp[TO];                                           \
        if (p->startinx < startg[peg TO])                               \
          p->startinx = startg[p->start=peg TO];                        \
        if (p->numpegs==1)                                              \
          if (!answer || p->score < answer->score)                      \
            answer = p;                                                 \
        found++;                                                        \
    }

#undef WALK
#define WALK(TO,MOVE,NEWHASH,NEWSCORE)                                  \
    if (pegp[TO] <= NOPEG && NEWSCORE[peg]<0) {                         \
        p->numwalk++;                                                   \
        p->score = p->score+NEWSCORE[peg];                              \
        p->hash  = p->hash +NEWHASH[peg];                               \
        p->pegs[p->nummove++] = MOVE|(peg);                             \
                                                                        \
        newp=p->grid+peg;                                               \
        *newp = -*newp;                                                 \
        newp[TO] = -newp[TO];                                           \
        found++;                                                        \
    }

      if (!found)
        JUMP(+max, -max, JUMPN,hashJN,scoreJN)
      if (!found)
        JUMP(-max, +max, JUMPS,hashJS,scoreJS)
      if (!found)
        JUMP(  -1,   +1, JUMPE,hashJE,scoreJE)
      if (!found)
        JUMP(  +1,   -1, JUMPW,hashJW,scoreJW)
      if (!found)
        WALK(-max, WALKN,hashWN,scoreWN)
      if (!found)
        WALK(+max, WALKS,hashWS,scoreWS)
      if (!found)
        WALK(  +1, WALKE,hashWE,scoreWE)
      if (!found)
        WALK(  -1, WALKW,hashWW,scoreWW)

      if (found)
        if (answer)
          return;
        else
          break;
      if ((peg=*pegp) == LASTPEG)
        break;
    } else {
      if ((peg=-*pegp) == LASTPEG)
        break;
    }
  }
}
}

int main (int argc, char **argv)
{
struct node *p, **scanroot;
int i, scanmin, scanmax, count;
char *fname = "input";
int ch;
int secs;

  while ((ch=getopt(argc, argv, "dt:n:")) != EOF)
    switch (ch) {
      case 't':
        if (optarg) {allowtst = atoi(optarg);}
        break;
      case 'n':
        if (optarg) {allownew = atoi(optarg);}
        break;
      case 'd':
        dflag++;
      case '?':
        break;
      default:
        printf ("Unsupported option: %c\n", ch);
    }
  while (optind < argc) {
    fname = argv[optind];
    optind++;
  }
#ifdef DEBUG
  fprintf (stderr, "name:%s allowtst:%d allownew:%d\n", fname, allowtst, allownew);
#endif

  /* load initial grid */
  if (initialize(fname) < 0)
    return -1;

#ifdef DEBUG
  fprintf (stderr, "memused:%d\n", MAXMEM-maxmem);
#endif

  level = 0;
  rootmin = rootmax = 0;
  roottbl1[0] = root1;
  root1->nextscore = NULL;

  for (;;) {
    level++;
    scanmin = rootmin;
    scanmax = rootmax;
    scanroot = level&1 ? roottbl1 : roottbl2;
    root     = level&1 ? roottbl2 : roottbl1;
    freelist = level&1 ? root2    : root1;

    rootmin = MAXROOT;
    rootmax = 0;
    rootbase = scanroot[scanmin]->score -distdelta;
    if (rootbase < 0)
      rootbase = 0;
    memset (root, 0, MAXROOT*sizeof(*root));
    memset (hash, 0, MAXHASH*sizeof(*hash));
    numtst = numnodes = numdups = 0;

    times(&tms);
    secs = (tms.tms_stime + tms.tms_utime)/clktck;
    if (secs >= MAXSEC2) {
      /* time to panic */
      p = scanroot[scanmin];
      panic(p);
      solution(p);
      return 0;
    } else if (secs >= MAXSEC1) {
      allowtst = 2;
      allownew = 8;
    }

    count = allowtst;
    for (i=scanmin; i<=scanmax; i++) {
      for (p=scanroot[i]; p; p=p->nextscore) {
        gen_moves (p);
        if (--count<0) {
          p->nextscore=NULL;
          i=scanmax+1;
        }
      }
      if (freelist == NULL)
        break;
      if (answer)
        solution(answer);
    }

#ifdef DEBUG
    p = level&1 ? roottbl2[rootmin] : roottbl1[rootmin];
    if (dflag)
      fprintf(stderr, ".");
    else
      fprintf (stderr, "#node:%d #tst:%d #dups:%d, lvl:%d, rmin:%d, rmax:%d %d %d %d\n",
               numnodes, numtst, numdups, level, rootmin, rootmax, p->numjump, p->numwalk, p->score);
    
/*    dump_node (p); */
    fflush (stdout);
#endif

    if (numnodes == 0)
      break;
  }
  return 0;
}