/*
 * Generate a solver for a marbles problem.
 *
 * Reads the problem from stdin.  Then reads solve-template.c and
 *  interprets the @-prefixed sequences, generating source to a solver;
 *  this source is printed on stdout.
 *
 * @ sequences understood:
 *
 *	@;	Everything from the @; up to and including the next
 *		newline is deleted.  (This is for comments that apply
 *		to the template but not the generated solver.)
 *
 *	@C	Generates three #define constants: SIZEX, SIZEY, and
 *		NMARBLES.  SIZEX and SIZEY are the size of the board;
 *		NMARBLES is the number of marbles.
 *
 *	@B	Generates static variable initializations.
 *
 *	@G	Generates a goal() test function.
 *
 *	@@	Turns into a single @.
 *
 * The input problem takes the form of two parts separated by a blank
 *  line.  The first part is the initial board position; the second,
 *  the goal pattern.
 *
 * The initial board position consists of a grid.  This grid must be
 *  rectangular.  Whitespace is ignored; other characters accepted are
 *
 *	*		Wall
 *	-		Outside-the-arena background
 *	.		Empty
 *	A B C D E F G	Marbles (of up to seven colours)
 *	O @ Ø ©		Teleporters (of up to four colours)
 *	< > ^ v		One-ways
 *	« » ~ _		Corresponding one-ways with bars
 *	1		Shatterable wall
 *
 * The goal pattern is made up of the same character set, but
 *  restricted to empty cells and marbles.  It too must be rectangular.
 */
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

static const char *templatefile = "solve-template.c";

#define MAXMTYPES 7

typedef struct grid GRID;

struct grid {
  int w;
  int h;
  char *contents;
  } ;

static GRID puzzle;
static GRID goal;
static int nmarbles;
static int mcount[MAXMTYPES];
static int (*minit)[3];

static void panic(void)
{
 (void)*(volatile char *)0;
 abort();
}

static int chartest_puzzle(unsigned char c)
{
 switch (c)
  { case '*': case '-': case '.':
    case 'A': case 'B': case 'C': case 'D':
    case 'E': case 'F': case 'G':
    case 'O': case '@':
    case (unsigned char)'Ø': case (unsigned char)'©':
    case '<': case '>': case '^': case 'v':
    case (unsigned char)'«': case (unsigned char)'»':
    case '~': case '_': case '1':
       return(1);
       break;
  }
 return(0);
}

static int chartest_goal(unsigned char c)
{
 switch (c)
  { case '.':
    case 'A': case 'B': case 'C': case 'D':
    case 'E': case 'F': case 'G':
       return(1);
       break;
  }
 return(0);
}

static void readgrid(const char *what, FILE *f, GRID *g, int (*test)(unsigned char))
{
 int c;
 char *b;
 int a;
 int l;
 int x;
 int y;

 g->w = -1;
 g->h = 0;
 b = 0;
 a = 0;
 l = 0;
 x = 0;
 y = 0;
 while (1)
  { c = getc(f);
    if (c == EOF)
     { if (x != 0)
	{ fprintf(stderr,"%s: unexpected EOF in %s pattern\n",__progname,what);
	  exit(1);
	}
       break;
     }
    if (c == '\n')
     { if (x == 0) break;
       if (y == 0)
	{ g->w = x;
	}
       else if (g->w != x)
	{ fprintf(stderr,"%s: %s pattern isn't rectangular (row %d len %d != previous len %d)\n",__progname,what,y+1,x,g->w);
	  exit(1);
	}
       x = 0;
       y ++;
       continue;
     }
    if ((c == ' ') || (c == '\t')) continue;
    if (! (*test)(c))
     { fprintf(stderr,"%s: bad char %02x (%c) in input\n",__progname,c,c);
       exit(1);
     }
    if (l >= a) b = realloc(b,a=l+8);
    b[l++] = c;
    x ++;
  }
 if (y == 0)
  { fprintf(stderr,"%s: no %s pattern\n",__progname,what);
    exit(1);
  }
 g->h = y;
 g->contents = b;
}

static void checkeof(void)
{
 int c;

 c = getchar();
 if (c != EOF)
  { fprintf(stderr,"%s: junk after puzzle\n",__progname);
    exit(1);
  }
}

static void dumpgrid(GRID *g, const char *what)
{
 int x;
 int y;
 char *cp;

 cp = g->contents;
 printf("%s: %dx%d\n",what,g->w,g->h);
 for (y=0;y<g->h;y++)
  { for (x=0;x<g->w;x++)
     { printf(" %c",*cp++);
     }
    printf("\n");
  }
}

static void countmarbles(GRID *g, int *mcv)
{
 int i;
 char *cp;
 int mx;

 cp = g->contents;
 for <"cell"> (i=g->w*g->h;i>0;i--,cp++)
  { switch (*cp)
#if MAXMTYPES != 7
#error "Code assumes MAXMTYPES is 7"
#endif
     { case 'A': mx = 0; break;
       case 'B': mx = 1; break;
       case 'C': mx = 2; break;
       case 'D': mx = 3; break;
       case 'E': mx = 4; break;
       case 'F': mx = 5; break;
       case 'G': mx = 6; break;
       default: continue <"cell">; break;
     }
    mcv[mx] ++;
  }
}

static void findmarbles(void)
{
 int i;
 int n;
 int x;
 int y;
 int mx;
 int pcount[MAXMTYPES];
 int gcount[MAXMTYPES];

 for (i=MAXMTYPES-1;i>=0;i--)
  { pcount[i] = 0;
    gcount[i] = 0;
  }
 countmarbles(&puzzle,&pcount[0]);
 countmarbles(&goal,&gcount[0]);
 nmarbles = 0;
 for (i=MAXMTYPES-1;i>=0;i--)
  { if (pcount[i] != gcount[i])
     { fprintf(stderr,"%s: different %c counts for puzzle (%d) and goal (%d)\n",__progname,'A'+i,pcount[i],gcount[i]);
       exit(1);
     }
    mcount[i] = pcount[i];
    nmarbles += mcount[i];
  }
 minit = malloc(nmarbles*sizeof(*minit));
 n = 0;
 for (y=0;y<puzzle.h;y++) for (x=0;x<puzzle.w;x++)
  { switch (puzzle.contents[(y*puzzle.w)+x])
     { case 'A': mx = 1;   if (0) {
       case 'B': mx = 2; } if (0) {
       case 'C': mx = 3; } if (0) {
       case 'D': mx = 4; } if (0) {
       case 'E': mx = 5; } if (0) {
       case 'F': mx = 6; } if (0) {
       case 'G': mx = 7; }
	  if (n >= nmarbles)
	   { fprintf(stderr,"%s: marble array overflow\n",__progname);
	     panic();
	   }
	  minit[n][0] = mx;
	  minit[n][1] = x;
	  minit[n][2] = y;
	  n ++;
	  break;
     }
  }
 if (n != nmarbles)
  { fprintf(stderr,"%s: marble array underflow\n",__progname);
    panic();
  }
}

static void gen_C(void)
{
 printf("#define SIZEX %d\n#define SIZEY %d\n#define NMARBLES %d\n",puzzle.w,puzzle.h,nmarbles);
}

static void gen_B(void)
{
 int x;
 int y;
 int tx;
 int ty;
 int i;
 char tsrc;
 int n;

 printf("static BOARD initboard = {{"/*}}*/);
 for (x=0;x<puzzle.w;x++)
  { printf("{\n"/*}*/);
    for (y=0;y<puzzle.h;y++)
     { switch (puzzle.contents[(y*puzzle.w)+x])
	{ default:
	     fprintf(stderr,"%s: impossible contents char %c in puzzle\n",__progname,puzzle.contents[(y*puzzle.w)+x]);
	     panic();
	     break;
	  case '*': case '-':
	     printf("CELL_F_WALL");
	     break;
	  case '.':
	     printf("CELL_F_EMPTY");
	     break;
	  case 'A':
	     printf("CELL_F_EMPTY | (1 << CELL_MARBLE_S)");
	     break;
	  case 'B':
	     printf("CELL_F_EMPTY | (2 << CELL_MARBLE_S)");
	     break;
	  case 'C':
	     printf("CELL_F_EMPTY | (3 << CELL_MARBLE_S)");
	     break;
	  case 'D':
	     printf("CELL_F_EMPTY | (4 << CELL_MARBLE_S)");
	     break;
	  case 'E':
	     printf("CELL_F_EMPTY | (5 << CELL_MARBLE_S)");
	     break;
	  case 'F':
	     printf("CELL_F_EMPTY | (6 << CELL_MARBLE_S)");
	     break;
	  case 'G':
	     printf("CELL_F_EMPTY | (7 << CELL_MARBLE_S)");
	     break;
	  case 'O':
	     printf("CELL_F_TPORT | (0 << CELL_F_AUX_S)");
	     break;
	  case '@':
	     printf("CELL_F_TPORT | (1 << CELL_F_AUX_S)");
	     break;
	  case 'Ø':
	     printf("CELL_F_TPORT | (2 << CELL_F_AUX_S)");
	     break;
	  case '©':
	     printf("CELL_F_TPORT | (3 << CELL_F_AUX_S)");
	     break;
	  case '<':
	     printf("CELL_F_DIODE | CELL_F_LF");
	     break;
	  case '>':
	     printf("CELL_F_DIODE | CELL_F_RT");
	     break;
	  case '^':
	     printf("CELL_F_DIODE | CELL_F_UP");
	     break;
	  case 'v':
	     printf("CELL_F_DIODE | CELL_F_DN");
	     break;
	  case '«':
	     printf("CELL_F_DBARS | CELL_F_LF");
	     break;
	  case '»':
	     printf("CELL_F_DBARS | CELL_F_RT");
	     break;
	  case '~':
	     printf("CELL_F_DBARS | CELL_F_UP");
	     break;
	  case '_':
	     printf("CELL_F_DBARS | CELL_F_DN");
	     break;
	  case '1':
	     printf("CELL_F_BREAK");
	     break;
	}
       printf(",\n");
     }
    printf(/*{*/"},\n");
  }
 printf(/*{*/"},{\n"/*}*/);
 for (i=0;i<nmarbles;i++) printf("{%d,%d,%d},\n",minit[i][0],minit[i][1],minit[i][2]);
 printf(/*{{*/"}};\n");
 printf("static const signed char tportto[SIZEX][SIZEY][2] = {\n"/*}*/);
 for (x=0;x<puzzle.w;x++)
  { printf("{\n"/*}*/);
    for <"entry"> (y=0;y<puzzle.h;y++)
     { tsrc = puzzle.contents[(y*puzzle.w)+x];
       switch (tsrc)
	{ default:
	     printf("{-1,-1},\n");
	     break;
	  case 'O': case '@': case 'Ø': case '©':
	     n = 0;
	     for (tx=0;tx<puzzle.w;tx++) for (ty=0;ty<puzzle.h;ty++)
	      { if (puzzle.contents[(ty*puzzle.w)+tx] == tsrc)
		 { if ((tx == x) && (ty == y)) continue;
		   printf("{%d,%d},\n",tx,ty);
		   n ++;
		 }
	      }
	     if (n == 0)
	      { fprintf(stderr,"%s: no paired teleporter for (%d,%d)\n",__progname,x,y);
		exit(1);
	      }
	     if (n != 1)
	      { fprintf(stderr,"%s: too many (%d) paired teleporters for (%d,%d)\n",__progname,n,x,y);
		exit(1);
	      }
	     break;
	}
     }
    printf(/*{*/"},\n");
  }
 printf(/*{*/"};\n");
}

static void gen_G(void)
{
 int i;
 int j;
 int k;
 int x;
 int y;
 int ix;
 int iy;
 int gx;
 int gy;
 char *cp;
 const char *sep;

 printf("static int goal(const BOARD *b)\n{\n"/*}*/);
 j = -1;
 for (i=MAXMTYPES-1;i>=0;i--)
  { if (mcount[i] == 0) continue;
    if ((j < 0) || (mcount[i] < mcount[j])) j = i;
  }
 if (mcount[j] == 1)
  { for (i=nmarbles-1;i>=0;i--) if (minit[i][0] == j+1) break;
    if (i < 0)
     { fprintf(stderr,"%s: can't find marble %c in init array\n",__progname,'A'+j);
       panic();
     }
    printf(" int x;\n int y;\n\n x = b->m[%d].x;\n y = b->m[%d].y;\n",i,i);
    do <"find">
     { cp = goal.contents;
       for (iy=0;iy<goal.h;iy++) for (ix=0;ix<goal.w;ix++) if (*cp++ == 'A'+j) break <"find">;
       fprintf(stderr,"%s: can't find marble %c in goal pattern\n",__progname,'A'+j);
       panic();
     } while (0);
    sep = " if (";
    if (ix > 0)
     { printf("%s(x < %d)",sep,ix);
       sep = " || ";
     }
    if (iy > 0)
     { printf("%s(y < %d)",sep,iy);
       sep = " || ";
     }
    if (ix < goal.w-1)
     { printf("%s(x > %d)",sep,puzzle.w-1-(goal.w-1-ix));
       sep = " || ";
     }
    if (iy < goal.h-1)
     { printf("%s(y > %d)",sep,puzzle.h-1-(goal.h-1-iy));
       sep = " || ";
     }
    if (sep[1] != 'i') printf(") return(0);\n");
    cp = goal.contents;
    for (y=0;y<goal.h;y++) for (x=0;x<goal.w;x++)
     { if (*cp != '.')
	{ k = *cp - 'A';
	  if (k != j)
	   { printf(" if ((b->b[x%+d][y%+d] & CELL_MARBLE) != (%d << CELL_MARBLE_S)) return(0);\n",x-ix,y-iy,k+1);
	   }
	}
       cp ++;
     }
    printf(" return(1);\n");
  }
 else
  { printf(" int x;\n int y;\n\n");
    k = 0;
    for (i=nmarbles-1;i>=0;i--)
     { if (minit[i][0] == j+1)
	{ if (k) printf(" if (b->m[%d].x < x) x = b->m[%d].x;\n if (b->m[%d].y < y) y = b->m[%d].y;\n",i,i,i,i);
	  else printf(" x = b->m[%d].x;\n y = b->m[%d].y;\n",i,i);
	  k ++;
	}
     }
    if (k != mcount[j])
     { fprintf(stderr,"%s: marble %c pattern found %d expected %d\n",__progname,'A'+j,k,mcount[j]);
       panic();
     }
    cp = goal.contents;
    k = 0;
    for (iy=0;iy<goal.h;iy++) for (ix=0;ix<goal.w;ix++)
     { if (*cp++ == 'A'+j)
	{ if (k)
	   { if (ix < gx) gx = ix;
	     if (iy < gy) gy = iy;
	   }
	  else
	   { gx = ix;
	     gy = iy;
	   }
	  k ++;
	}
     }
    if (k != mcount[j])
     { fprintf(stderr,"%s: marble %c goal found %d expected %d\n",__progname,'A'+j,k,mcount[j]);
       panic();
     }
    sep = " if (";
    if (gx > 0)
     { printf("%s(x < %d)",sep,gx);
       sep = " || ";
     }
    if (gy > 0)
     { printf("%s(y < %d)",sep,gy);
       sep = " || ";
     }
    if (gx < goal.w-1)
     { printf("%s(x > %d)",sep,puzzle.w-1-(goal.w-1-gx));
       sep = " || ";
     }
    if (gy < goal.h-1)
     { printf("%s(y > %d)",sep,puzzle.h-1-(goal.h-1-gy));
       sep = " || ";
     }
    if (sep[1] != 'i') printf(") return(0);\n");
    cp = goal.contents;
    for (y=0;y<goal.h;y++) for (x=0;x<goal.w;x++)
     { if (*cp != '.')
	{ k = *cp - 'A';
	  printf(" if ((b->b[x%+d][y%+d] & CELL_MARBLE) != (%d << CELL_MARBLE_S)) return(0);\n",x-gx,y-gy,k+1);
	}
       cp ++;
     }
    printf(" return(1);\n");
  }
 printf(/*{*/"}\n");
}

static void processtemplate(void)
{
 FILE *tf;
 int c;

 tf = fopen(templatefile,"r");
 if (tf == 0)
  { fprintf(stderr,"%s: can't open %s: %s\n",__progname,templatefile,strerror(errno));
    exit(1);
  }
 while (1)
  { c = getc(tf);
    if (c == EOF) break;
    if (c != '@')
     { putchar(c);
       continue;
     }
    c = getc(tf);
    if (c == EOF)
     { fprintf(stderr,"%s: %s: EOF after @\n",__progname,templatefile);
       exit(1);
     }
    switch (c)
     { default:
	  fprintf(stderr,"%s: %s: unrecognized @ sequence @%c\n",__progname,templatefile,c);
	  exit(1);
	  break;
       case ';':
	  while (1)
	   { c = getc(tf);
	     if (c == EOF)
	      { fprintf(stderr,"%s: %s: EOF while reading @; line\n",__progname,templatefile);
		exit(1);
	      }
	     if (c == '\n') break;
	   }
	  break;
       case 'C':
	  gen_C();
	  break;
       case 'B':
	  gen_B();
	  break;
       case 'G':
	  gen_G();
	  break;
       case '@':
	  putchar('@');
	  break;
     }
  }
}

int main(void);
int main(void)
{
 readgrid("puzzle",stdin,&puzzle,&chartest_puzzle);
 readgrid("goal",stdin,&goal,&chartest_goal);
 checkeof();
 findmarbles();
 printf("/*\n");
 dumpgrid(&puzzle,"puzzle");
 dumpgrid(&goal,"goal");
 printf("*/\n");
 processtemplate();
 return(0);
}