//#define VERBOSE
/*
 * Program to brute-force solutions to Chesscourt Mission puzzles.
 *  Chesscourt Mission is a game involving chess pieces on extended
 *  chessboards with portions blocked; the objective is to get the king
 *  out the entrace.  Some cells are blocked for position but not
 *  motion, as in you cam move through them but not stop on them.
 *  Moves that look like captures swap the `capturing' and `captured'
 *  pieces, with the focus-of-control remaining on the same square (so
 *  the `captured' piece becoems the active one).
 *
 * For example, if we use # for a completely blocked cell (can't even
 *  move through) X for a can't-stop-on cell, . for accessible cells,
 *  the usual single letters for pieces (pnbrqk) for pieces, E for the
 *  entrance/exit, and ! for a bonus-puzzle entrance, the first puzzle
 *  looks like this (with an infinite # surround)
 *
 *	# # # # # # # # # # # # # # # # #
 *	# # # # # # . k . . # # # # # # #
 *	# # # # # # . . . # . # # # # # #
 *	# # # # # # . . . # # . # # # # #
 *	# # # # # # # # # # # # . . . # #
 *	# # # # # # # # # # # # . . . # #
 *	# # # # # # X X X X . . . . . # #
 *	# # # # # # . . . . X . . . . # #
 *	# # # # # # . . . . # X X X X # #
 *	# . . . . . . # . r X # # # # . #
 *	# . # # . # . # . . . # # # ! # #
 *	# X # . # # . . . . . # # # # # #
 *	# . . . # # # . P . # # # # # # #
 *	# . . b # # # # E # # # # # # # #
 *	# # # # # # # # # # # # # # # # #
 *
 *  where the use of P rather than p for the pawn indicates that it's
 *  the active piece.  One solution, writing (distance)(direction) for
 *  moves and x(other-piece)(direction) for swap `captures', is
 *
 *	2N xrNE 2N 2W 1S 5W 5S xbE 6NE 1SE 2NE 1SE 2NE 4NW 1SW xkNW 1NE
 *	1SE 1SE 1SE 1S 1SW 1W 1SW 1SW 1S 1S 1S 1S 1S.
 *
 * Pawns which reach the back rank always turn into queens, where `back
 *  rank' is defined as `moving forward runs into nothing but # cells'.
 *
 * The full list of characters accepted in puzzles (some of these are
 *  described below rather than above) is:
 *
 *	.	Empty space.
 *	#	Solid wall.
 *	X	Space that can be moved through but not onto.
 *	E	Exit.
 *	!	Bonus-level entrance.
 *	=	Gate.
 *	p, n, b, r, q, k
 *		Most pieces.
 *	P, N, B, R, Q, K
 *		The active piece.  There must be exactly one such.
 *
 * Gates are barriers which cannot be moved through; `capturing' them
 *  destroys them.  They are implemented as special pieces.
 *
 * The puzzle is read from stdin.
 */

#include <es.h>
#include <avl.h>
#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

typedef struct state STATE;
typedef struct xy XY;

struct xy {
  unsigned char x;
  unsigned char y;
  } ;
#define XYMAKE(xv,yv) ((XY){.x=(xv),.y=(yv)})

struct state {
  const STATE *parent;
  unsigned short int depth;
  XY *pclocs;
  unsigned char active;
  unsigned int moved;
  unsigned int queened;
  } ;

static int xsize;
static int ysize;
static int cellx;
static int ncells;
static int nbonus;
static XY *bonuslocs;
static unsigned int found;
static char *fixed;
#define FIX_EMPTY '.'
#define FIX_SOLID '#'
#define FIX_BLOCK 'X'
#define FIX_BONUS '!'
#define FIX_EXIT  'E'
#define LOC(x,y) ((x)+((y)*xsize))
static int afixed;
static int npcs;
static char *pctypes;
static AVL *seen;
static AVL *pending;
static int curdepth;
static int depthcount;

static STATE start;

#define Ctoupper(x) toupper((unsigned char)(x))

static char *new_cell(void)
{
 int i;
 int n;

 if (ysize < 1)
  { i = cellx;
    n = i + 1;
  }
 else
  { i = cellx + (xsize * ysize);
    n = xsize * (ysize + 1);
  }
 if (n > afixed)
  { afixed = n + 8;
    fixed = realloc(fixed,afixed);
  }
 cellx ++;
 return(&fixed[i]);
}

static void puzzle_nonpiece(char ch)
{
 *new_cell() = ch;
}

static void puzzle_piece(char pc)
{
 int i;

 puzzle_nonpiece(FIX_EMPTY);
 i = npcs ++;
 pctypes = realloc(pctypes,npcs);
 pctypes[i] = pc;
 start.pclocs = realloc(start.pclocs,npcs*sizeof(XY));
 start.pclocs[i] = XYMAKE(cellx-1,ysize); // -1: cellx++ during puzzle_nonpiece()
}

static void puzzle_endline(void)
{
 if (ysize > 0)
  { if (cellx != xsize)
     { fprintf(stderr,"%s: puzzle X size inconsistent\n",__progname);
       exit(1);
     }
  }
 else
  { xsize = cellx;
  }
 ysize ++;
 cellx = 0;
}

static void read_puzzle(void)
{
 int c;
 int nexit;

 xsize = 0;
 ysize = 0;
 cellx = 0;
 fixed = 0;
 afixed = 0;
 npcs = 0;
 pctypes = 0;
 nbonus = 0;
 nexit = 0;
 start.pclocs = 0;
 start.active = 0xff;
 while <"input"> (1)
  { c = getchar();
    switch (c)
     { case EOF:
	  if (ferror(stdin))
	   { fprintf(stderr,"%s: read error reading puzzle: %s\n",__progname,strerror(errno));
	     exit(1);
	   }
	  break <"input">;
       case '\n':
	  puzzle_endline();
	  break;
       case ' ':
       case '\t':
	  continue <"input">;
	  break;
       case FIX_EMPTY:
       case FIX_SOLID:
       case FIX_BLOCK:
	  puzzle_nonpiece(c);
	  break;
       case FIX_BONUS:
	  nbonus ++;
	  bonuslocs = realloc(bonuslocs,nbonus*sizeof(XY));
	  bonuslocs[nbonus-1] = XYMAKE(cellx,ysize);
	  puzzle_nonpiece(c);
	  break;
       case FIX_EXIT:
	  nexit ++;
	  puzzle_nonpiece(c);
	  break;
       case 'p':
       case 'n':
       case 'b':
       case 'r':
       case 'q':
       case 'k':
       case '=':
	  puzzle_piece(c);
	  break;
       case 'P': c = 'p';   if (0) {
       case 'N': c = 'n'; } if (0) {
       case 'B': c = 'b'; } if (0) {
       case 'R': c = 'r'; } if (0) {
       case 'Q': c = 'q'; } if (0) {
       case 'K': c = 'k'; }
	  if (start.active != 0xff)
	   { fprintf(stderr,"%s: multiple active pieces\n",__progname);
	     exit(1);
	   }
	  start.active = npcs;
	  puzzle_piece(c);
	  break;
       default:
	  fprintf(stderr,"%s: bad char `%c' in puzzle\n",__progname,c);
	  exit(1);
	  break;
     }
  }
 if (cellx != 0)
  { fprintf(stderr,"%s: last puzzle line missing its newline\n",__progname);
    exit(1);
  }
 ncells = xsize * ysize;
 if (ncells < 1)
  { fprintf(stderr,"%s: puzzle has no cells!\n",__progname);
    exit(1);
  }
 if (nexit < 1)
  { fprintf(stderr,"%s: no exit\n",__progname);
  }
 else if (nexit > 1)
  { fprintf(stderr,"%s: multiple exits\n",__progname);
    exit(1);
  }
 if (nbonus > 29)
  { fprintf(stderr,"%s: too many bonus cells\n",__progname);
    exit(1);
  }
 if (npcs > 32)
  { fprintf(stderr,"%s: too many pieces\n",__progname);
    exit(1);
  }
 found = 0;
 if (start.active == 0xff)
  { fprintf(stderr,"%s: no initial active piece\n",__progname);
    exit(1);
  }
}

static void setup_state(void)
{
 start.parent = 0;
 start.depth = 0;
 start.moved = 0;
 start.queened = 0;
}

static void dumpstate(const STATE *s, const char *pref)
{
 XY at;
 int i;
 static char *obuf = 0;
 int x;
 int y;
 int j;
 char c;

 if (! obuf) obuf = malloc(ncells);
 bcopy(fixed,obuf,ncells);
 for (i=npcs-1;i>=0;i--)
  { at = s->pclocs[i];
    c = pctypes[i];
    if ((at.x == 0xff) && (at.y == 0xff) && (c == '=')) continue;
    if ((at.x >= xsize) || (at.y >= ysize)) abort();
    if ((c == 'p') && (s->queened & (1 << i))) c = 'q';
    if (i == s->active) c = Ctoupper(c);
    obuf[LOC(at.x,at.y)] = c;
  }
 i = 0;
 for (y=0;y<ysize;y++)
  { printf("%s",pref);
    for (x=0;x<xsize;x++)
     { printf(" %c",obuf[i]);
       i ++;
     }
    if (y == 0)
     { printf("    ");
#ifdef VERBOSE
       printf("%p parent %p",(const void *)s,(const void *)s->parent);
#endif
       printf(" d%d",s->depth);
       for (j=npcs-1;j>=0;j--)
	{ printf(" %c(%d,%d)",
		(j==s->active) ? Ctoupper(pctypes[j]) : pctypes[j],
		s->pclocs[j].x, s->pclocs[j].y);
	}
       printf(" m%x",s->moved);
       printf(" q%x",s->queened);
     }
    putchar('\n');
  }
}

static STATE *new_state(void)
{
 STATE *s;

 s = malloc(sizeof(STATE));
 s->pclocs = malloc(npcs*sizeof(XY));
 return(s);
}

static void copystate(STATE *to, const STATE *from)
{
 bcopy(from->pclocs,to->pclocs,npcs*sizeof(XY));
 to->active = from->active;
 to->moved = from->moved;
 to->queened = from->queened;
}

static void dump_soln(const STATE *s)
{
 if (s->parent) dump_soln(s->parent);
 dumpstate(s,"");
 printf("----\n");
}

static void reached_bonus(const STATE *s, int x, int y)
{
 int i;

 for (i=nbonus-1;i>=0;i--)
  { if ((x == bonuslocs[i].x) && (y == bonuslocs[i].y))
     { if (! (found & (2 << i)))
	{ printf("Reached bonus at (%d,%d)\n",x,y);
	  dump_soln(s);
	  found |= 2 << i;
	  fflush(stdout);
	}
       return;
     }
  }
}

static void reached_exit(const STATE *s)
{
 if (! (found & 1))
  { printf("Reached exit\n");
    dump_soln(s);
    found |= 1;
    fflush(stdout);
  }
}

static int piecethere(const STATE *s, int x, int y)
{
 int i;

 for (i=npcs-1;i>=0;i--)
  { if ((s->pclocs[i].x == x) && (s->pclocs[i].y == y)) return(i);
  }
 return(-1);
}

static int queen_square(int x, int y)
{
 int i;

 if ((x < 0) || (x >= xsize) || (y < 0) || (y >= ysize)) abort();
 i = LOC(x,y);
 if (fixed[i] != FIX_EMPTY) return(0);
 while (1)
  { y --;
    i -= xsize;
    if (y < 0) return(1);
    if (fixed[i] != FIX_SOLID) return(0);
  }
}

static int trymove(const STATE *s, int x, int y, int flags)
#define MOVE_NOMOVE 0x00000001
#define MOVE_NOCAP  0x00000002
{
 int i;
 int j;
 static STATE *n;
 int rv;
 XY loctmp;
 int pc;

 if ((x < 0) || (x >= xsize) || (y < 0) || (y >= ysize)) return(1);
#ifdef VERBOSE
 printf("Trying move to (%d,%d)\n",x,y);
#endif
 pc = s->active;
 if ((pc < 0) || (pc >= npcs)) abort();
 i = LOC(x,y);
 switch (fixed[i])
  { case FIX_EMPTY:
       break;
    case FIX_SOLID:
       return(1);
       break;
    case FIX_BLOCK:
       return(0);
       break;
    case FIX_BONUS:
       reached_bonus(s,x,y);
       return(0);
       break;
    case FIX_EXIT:
       if (pctypes[pc] == 'k') reached_exit(s);
       return(0);
       break;
    default:
       abort();
       break;
  }
 j = piecethere(s,x,y);
 if ( ((j >= 0) && (flags & MOVE_NOCAP)) ||
      ((j < 0) && (flags & MOVE_NOMOVE)) ) return(0);
 if (! n) n = new_state();
 if (j < 0)
  { copystate(n,s);
    n->pclocs[pc].x = x;
    n->pclocs[pc].y = y;
    n->moved |= 1 << pc;
    rv = 0;
  }
 else if (j >= npcs)
  { abort();
  }
 else if (pctypes[j] == '=')
  { copystate(n,s);
    n->pclocs[j].x = 0xff;
    n->pclocs[j].y = 0xff;
    n->pclocs[pc].x = x;
    n->pclocs[pc].y = y;
    n->moved |= 1 << pc;
    rv = 1;
  }
 else
  { copystate(n,s);
    loctmp = n->pclocs[pc];
    n->pclocs[pc] = n->pclocs[j];
    n->pclocs[j] = loctmp;
    n->active = j;
    n->moved |= (1 << pc) | (1 << j);
    rv = 1;
  }
 if ((pctypes[pc] == 'p') && queen_square(x,y)) n->queened |= 1 << pc;
 n->parent = s;
 n->depth = s->depth + 1;
 if (avl_insert(seen,n))
  {
#ifdef VERBOSE
    printf("Already seen\n");
#endif
    return(rv);
  }
#ifdef VERBOSE
 printf("New\n");
 dumpstate(n,"\t");
#endif
 if (avl_insert(pending,n)) abort();
 n = 0;
 return(rv);
}

static void trymove_direction(const STATE *s, int dx, int dy)
{
 XY loc;

 loc = s->pclocs[s->active];
 while (1)
  { loc.x += dx;
    loc.y += dy;
    if (trymove(s,loc.x,loc.y,0)) break;
  }
}

static void trymove_bishop(const STATE *s)
{
 trymove_direction(s,-1,-1);
 trymove_direction(s,-1,1);
 trymove_direction(s,1,1);
 trymove_direction(s,1,-1);
}

static void trymove_rook(const STATE *s)
{
 trymove_direction(s,-1,0);
 trymove_direction(s,0,-1);
 trymove_direction(s,1,0);
 trymove_direction(s,0,1);
}

static void trymoves(const STATE *s)
{
 XY loc;

 if (s->active >= npcs) abort();
 loc = s->pclocs[s->active];
 switch (pctypes[s->active])
  { case 'p':
       if (s->queened & (1 << s->active))
	{
    case 'q':
	  trymove_bishop(s);
	  trymove_rook(s);
	  break;
	}
       else
	{ if (loc.y >= 1)
	   { if ( !(s->moved & (1 << s->active)) &&
		  (loc.y >= 2) &&
		  (fixed[LOC(loc.x,loc.y-1)] != FIX_SOLID) &&
		  (piecethere(s,loc.x,loc.y-1) < 0) )
	      { trymove(s,loc.x,loc.y-2,MOVE_NOCAP);
	      }
	     trymove(s,loc.x,loc.y-1,MOVE_NOCAP);
	     trymove(s,loc.x-1,loc.y-1,MOVE_NOMOVE);
	     trymove(s,loc.x+1,loc.y-1,MOVE_NOMOVE);
	   }
	}
       break;
    case 'n':
       trymove(s,loc.x-1,loc.y-2,0);
       trymove(s,loc.x+1,loc.y-2,0);
       trymove(s,loc.x+2,loc.y-1,0);
       trymove(s,loc.x+2,loc.y+1,0);
       trymove(s,loc.x+1,loc.y+2,0);
       trymove(s,loc.x-1,loc.y+2,0);
       trymove(s,loc.x-2,loc.y+1,0);
       trymove(s,loc.x-2,loc.y-1,0);
       break;
    case 'b':
       trymove_bishop(s);
       break;
    case 'r':
       trymove_rook(s);
       break;
    case 'k':
       trymove(s,loc.x-1,loc.y-1,0);
       trymove(s,loc.x-1,loc.y,0);
       trymove(s,loc.x-1,loc.y+1,0);
       trymove(s,loc.x,loc.y+1,0);
       trymove(s,loc.x+1,loc.y+1,0);
       trymove(s,loc.x+1,loc.y,0);
       trymove(s,loc.x+1,loc.y-1,0);
       trymove(s,loc.x,loc.y-1,0);
       break;
  }
}

static int cmp_seen(void *av, void *bv)
{
 STATE *a;
 STATE *b;
 int i;

 a = av;
 b = bv;
 if (a->active != b->active) return((int)a->active-(int)b->active);
 for (i=npcs-1;i>=0;i--)
  { if (a->pclocs[i].y != b->pclocs[i].y) return((int)a->pclocs[i].y-(int)b->pclocs[i].y);
    if (a->pclocs[i].x != b->pclocs[i].x) return((int)a->pclocs[i].x-(int)b->pclocs[i].x);
  }
 return(0);
}

static const AVL_OPS ao_seen = { .compare = &cmp_seen, .flags = AVL_F_NODUPS };

static int cmp_pending(void *av, void *bv)
{
 return((int)((STATE *)av)->depth-(int)((STATE *)bv)->depth);
}

static const AVL_OPS ao_pending = { .compare = &cmp_pending, .flags = 0 };

int main(void);
int main(void)
{
 STATE *s;

 read_puzzle();
 setup_state();
 seen = avl_new(&ao_seen);
 pending = avl_new(&ao_pending);
 if (avl_insert(seen,&start)) abort();
 if (avl_insert(pending,&start)) abort();
 curdepth = 0;
 depthcount = 0;
 while (1)
  { s = avl_delete_first(pending);
    if (! s) break;
    if (s->depth == curdepth)
     { depthcount ++;
     }
    else
     { printf("depth %d count %d\n",curdepth,depthcount);
       fflush(stdout);
       curdepth = s->depth;
       depthcount = 1;
     }
#ifdef VERBOSE
    printf("Considering:\n");
    dumpstate(s,"    ");
#endif
    trymoves(s);
  }
 printf("Done\n");
 return(0);
}