#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#ifdef __BORLANDC__
#include "conio.h"
#endif



#define MGRIDSIZE 200
#define MIDDLE MGRIDSIZE/2
#define WORDLENGTH 30
#define MWORDS 50
#define MHEAP 22000
#define HOR 1
#define VER 2
#define MONLEVEL 30
#define DEBUGg
#define WAITt
#define OCHECK
#define NOGRIDOUTt
#define CUT

#define swap(a,b) swapvar=a; a=b ;b=swapvar;

int swapvar;

char *words[MWORDS + 3];
int lengths[MWORDS + 3];
char *clues[MWORDS + 3];
int analysis[MWORDS + 3][MWORDS + 3];
int *analyses;
int nwords;			/* no of words to be placed */
int minwords;			/* how many needs to be in the puzzle */
int word, level;
int more;			/* how many more on this level */
int x, y, ir;
int gridsize;			/* size of the grid */

char grid[MGRIDSIZE][MGRIDSIZE];


int heap[MHEAP];
int heapp;
int sizeheap[MWORDS * 4 + 10];
int sizeheapp;

int x0, x1, y0, y1;

int crosses;
int bestcrosses;
int bestlevel;
int mores[MWORDS];

int stops[MWORDS + 3];
int goodness = 5;

int nomix;

int loose, loosex, loosey, loosel, looseir;

int counter;
int addcount;

struct place_st
{
  int w;
  int x;
  int y;
  int ir;
};
struct place_st place[MWORDS];
int placep;

void
waitt (void)
{
#ifdef WAIT
  int i;

  /* if (nomix!=PROBLEM) return; */

  i = getch ();
  if (i == 'd')
    i = 'd';
  if (i == ' ')
    exit (5);
#endif
}

void
readwords (char *name)
{
  FILE *in;
  char ss[10 * WORDLENGTH];
  int l;
  int j = 0;

  nwords = -1;
  if ((in = fopen (name, "r")) == NULL) {
    fprintf (stderr, "Cannot open input file.\n");
    exit (1);
  }
  while (!feof (in)) {
    ss[0] = 0;
    fscanf (in, "%s", ss);
    if (ss[0] == 0)
      break;
    if ((words[++nwords] = (char *) malloc (strlen (ss) + 1)) == NULL) {
      printf ("Not enough memory to allocate buffer\n");
      exit (1);			/* terminate program if out of memory */
    }
    strcpy (words[nwords], ss);
    lengths[nwords] = strlen (ss);
    do {
      if (!feof (in))
	j = fgetc (in);
    }
    while (j == ' ');
    ungetc (j, in);
    if (!feof (in)) {
      fgets (ss, 10 * WORDLENGTH, in);
      /*
       * j=fgetc(in); ungetc(j,in); 
       */
      l = strlen (ss);
      if (l > 1) {
	ss[l - 1] = 0;
	if ((clues[nwords] = (char *) malloc (l)) == NULL) {
	  printf ("Not enough memory to allocate buffer\n");
	  exit (1);		/* terminate program if out of memory */
	}
	strcpy (clues[nwords], ss);
      }
      else
	clues[nwords] = words[nwords];
    }
  }
  fclose (in);
}


void
order (void)
{
  int i, j, k;
  char *sss;
  for (i = 0; i < nwords; i++) {
    for (j = i + 1; j <= nwords; j++) {
      if (lengths[j] > lengths[i]) {
	sss = words[i];
	words[i] = words[j];
	words[j] = sss;
	sss = clues[i];
	clues[i] = clues[j];
	clues[j] = sss;
	k = lengths[i];
	lengths[i] = lengths[j];
	lengths[j] = k;
      }
    }
  }
}

void
wpush (int word, int x, int y, int i)
{
  if (heapp + 4 < MHEAP) {
    heap[++heapp] = word;
    heap[++heapp] = x;
    heap[++heapp] = y;
    heap[++heapp] = i;
  }
  else {
    printf ("heap too small");
    exit (1);
  }
}

void
push (int i)
{
  if (heapp + 1 < MHEAP) {
    heap[++heapp] = i;
  }
  else {
    printf ("heap too small");
    exit (1);
  }
}


void
wpop (int *word, int *x, int *y, int *i)
{
  if (heapp - 4 >= -1) {
    *i = heap[heapp--];
    *y = heap[heapp--];
    *x = heap[heapp--];
    *word = heap[heapp--];
  }
  else {
    printf ("heap error 1");
    exit (1);
  }
}

void
pop (int *i)
{
  if (heapp - 1 >= -1) {
    *i = heap[heapp--];
  }
  else {
    printf ("heap error 2");
    exit (1);
  }
}

void
gridout (void)
{
  int i, j, db, k, l;
  int tombv[MWORDS];
  int tombf[MWORDS];
  char ss[WORDLENGTH];
  FILE *out, *outtex;
  char cc;

#ifdef NOGRIDOUT
  return;
#endif

  if ((out = fopen ("puzzle.txt", "a")) == NULL) {
    fprintf (stderr, "Cannot open output file.\n");
    exit (1);
  }
  if ((outtex = fopen ("puzzle.tex", "w")) == NULL) {
    fprintf (stderr, "Cannot open output file.\n");
    exit (1);
  }
  printf ("\n");
  fprintf (out, "\n");
  fprintf (outtex, "\\input puzmac.tex\n\\vbox{\\offinterlineskip\n");
  for (i = y0 - 1; i <= y1 + 1; i++) {
    fprintf (outtex, "\\hbox{ ");
    for (j = x0 - 1; j <= x1 + 1; j++) {
      cc = 0;
      if ((grid[j][i] != ' ') || (cc == 0))
	printf ("%c", grid[j][i]);
      else
	printf ("%c", 47 + cc);
      fprintf (out, "%c", grid[j][i]);
      if (grid[j][i] == ' ') {
	fprintf (outtex, "\\emp  ");
      }
      else
	fprintf (outtex, "\\bx{%c}", grid[j][i]);
    }
    printf ("\n");
    fprintf (out, "\n");
    fprintf (outtex, "}\n");
  }

  db = 0;
  fprintf (outtex, "}\\eject \\vbox{\\offinterlineskip");
  for (i = y0; i <= y1; i++) {
    fprintf (outtex, "\\hbox{ ");
    for (j = x0; j <= x1; j++) {
      if (grid[j][i] == ' ') {
	fprintf (outtex, "\\emp  ");
      }
      else {
	if (((grid[j - 1][i] == ' ') && (grid[j + 1][i] != ' ')) ||
	    ((grid[j][i - 1] == ' ') && (grid[j][i + 1] != ' '))) {
	  fprintf (outtex, "\\nm{%i}", ++db);
	  tombv[db] = 0;
	  tombf[db] = 0;
	}
	else
	  fprintf (outtex, "\\bx{ }");
	if (((grid[j - 1][i] == ' ') && (grid[j + 1][i] != ' '))) {
	  for (k = 0; ' ' != (ss[k] = grid[j + k][i]); k++);
	  ss[k] = 0;
	  for (l = 0; strcmp (ss, words[l]); l++);
	  tombv[db] = l + 1;
	}
	if (((grid[j][i - 1] == ' ') && (grid[j][i + 1] != ' '))) {
	  for (k = 0; ' ' != (ss[k] = grid[j][i + k]); k++);
	  ss[k] = 0;
	  for (l = 0; strcmp (ss, words[l]); l++);
	  tombf[db] = l + 1;
	}
      }
    }
    fprintf (outtex, "}\n");
  }
  fprintf (outtex, "\n}\\noindent Across \n\n");
  for (i = 1; i <= db; i++) {
    if (tombv[i])
      fprintf (outtex, "\\item{%i}{%s} \n", i, clues[tombv[i] - 1]);
  }

  fprintf (outtex, "\n\\noindent Down \n\n");
  for (i = 1; i <= db; i++) {
    if (tombf[i])
      fprintf (outtex, "\\item{%i}{%s} \n", i, clues[tombf[i] - 1]);
  }

  printf
    ("\nDim: %i by %i, Words: %i out of %i, Cross: %i, Mix: %i  Ratio: %i Loose %i \n",
     x1 - x0 + 1, y1 - y0 + 1, level + 1, nwords + 1, crosses, nomix,
     (100 * crosses) / (level), loose);
  fprintf (out,
	   "\nDim: %i by %i, Words: %i out of %i, Cross: %i, Mix: %i  Ratio: %i Loose %i \n",
	   x1 - x0 + 1, y1 - y0 + 1, level + 1, nwords + 1, crosses, nomix,
	   (100 * crosses) / level, loose);
  fprintf (outtex, "\\bye");
  fclose (out);
  fclose (outtex);
  for (i=1;i<=level;i++) {
    printf("%d ",stops[i]);
  }
  printf("\n");
}


void
addwrite (int w, int x, int y)
{
  printf ("%i %i %i %i \n", ++addcount, w, x, y);
}

void
add (int w, int x, int y, int ir)
{				/* reads from the heap */
  int i, l, oldcrosses;
/*  addwrite(w,x,y); */
  place[placep].w = w;
  place[placep].x = x;
  place[placep].y = y;
  place[placep++].ir = ir;
  oldcrosses = crosses;
  sizeheap[++sizeheapp] = x0;
  sizeheap[++sizeheapp] = x1;
  sizeheap[++sizeheapp] = y0;
  sizeheap[++sizeheapp] = y1;
  if (x < x0)
    x0 = x;
  if (y < y0)
    y0 = y;
  l = lengths[w];
  if ((x + (l - 1) * (ir % 2) > x1))
    x1 = x + (l - 1) * (ir % 2);
  if ((y + (l - 1) * (ir / 2) > y1))
    y1 = y + (l - 1) * (ir / 2);

  for (i = 0; i < l; i++) {
    if (grid[x + (i) * (ir % 2)][y + (i) * (ir / 2)] == ' ') {
      grid[x + (i) * (ir % 2)][y + (i) * (ir / 2)] = words[w][i];
    }
    else
      ++crosses;
  }
  if (crosses < oldcrosses + 2) {
    loose = 1;
  }
  else {
    loose = 0;
  }
}



int
checkloc (int w, int x, int y, int ir)
{				/* check if word can go into the grid */
  int i, l, ig;
  l = lengths[w];
  ig = 0;
  switch (ir) {
  case HOR:
    if (grid[x - 1][y] != ' ')
      return 0;
    if (grid[x + l][y] != ' ')
      return 0;
    for (i = 0; i < l; i++) {
      if (grid[x + i][y] == ' ') {
	if ((grid[x + i][y - 1] != ' ') || (grid[x + i][y + 1] != ' '))
	  return 0;
      }
      else {
	++ig;
	if (grid[x + i][y] != words[w][i])
	  return 0;
	if ((grid[x + i][y - 1] == ' ') && (grid[x + i][y + 1] == ' '))
	  return 0;
      }
    }
    break;
  case VER:
    if (grid[x][y - 1] != ' ')
      return 0;
    if (grid[x][y + l] != ' ')
      return 0;
    for (i = 0; i < l; i++) {
      if (grid[x][y + i] == ' ') {
	if ((grid[x - 1][y + i] != ' ') || (grid[x + 1][y + i] != ' '))
	  return 0;
      }
      else {
	++ig;
	if (grid[x][y + i] != words[w][i])
	  return 0;
	if ((grid[x - 1][y + i] == ' ') && (grid[x + 1][y + i] == ' '))
	  return 0;
      }
    }
  }
  return ig;
}


void
addallold (void)
{
  int db;
  int l;
  int i, j;
/*  ++counter;
  if (counter>10000) exit (20); */
  l = lengths[level];
  db = 0;
  /*
   * wpush(level,x1+2,y0,VER); wpush(level,x0,y1+2,HOR); db +=2;  
   */
  for (i = x1; i >= x0; i--) {
    for (j = y0 - l + 1; j <= y1; j++) {
      if (checkloc (level, i, j, VER)) {
	wpush (level, i, j, VER);
	++db;
      }
    }
  }
  for (i = x0 - l + 1; i <= x1; i++) {
    for (j = y1; j >= y0; j--) {
      if (checkloc (level, i, j, HOR)) {
	wpush (level, i, j, HOR);
	++db;
      }
    }
  }
  push (db);
}

void
addall (void)
{
  int dbdb;
  int db;
  int i, j, k, l;
  int ii, jj;
  int m;
  int w, x, y, ir, pir;
  int cross,maxcross;
  l = lengths[level];
  db = 0;
  maxcross=1;
  for (i = 0; i < placep; i++) {
    w = place[i].w;
    x = place[i].x;
    y = place[i].y;
    ir = place[i].ir;
    if (ir == VER) {
      pir = HOR;
    }
    else {
      pir = VER;
    }
    m = analysis[w][level];
    dbdb = analyses[m];
    for (j = m + 1; j <= m + 2 * dbdb;) {
      ii = analyses[j++];
      jj = analyses[j++];
      switch (ir) {
      case HOR:
	k = x + ii;
	l = y - jj;
	break;
      case VER:
	k = x - jj;
	l = y + ii;
      }
      if (cross=checkloc (level, k, l, pir)) {
#ifdef CUT
	if (cross>maxcross) {
          maxcross=cross;
          while (db>0) {
            heapp -= 4;
            --db;
          }
        }
#endif
        wpush (level, k, l, pir);
	++db;
      }
    }
  }
  push (db);
}

void
looseaddallold (void)
{
  int db;
  int l;
  int i, j;
  l = lengths[level];
  db = 0;
  switch (looseir) {
  case HOR:
    for (i = loosex + loosel - 1; i >= loosex; i--) {
      for (j = loosey - l + 1; j <= loosey; j++) {
	if (checkloc (level, i, j, VER)) {
	  wpush (level, i, j, VER);
	  ++db;
	}
      }
    }
    break;
  case VER:
    for (i = loosex - l + 1; i <= loosex; i++) {
      for (j = loosey + loosel - 1; j >= loosey; j--) {
	if (checkloc (level, i, j, HOR)) {
	  wpush (level, i, j, HOR);
	  ++db;
	}
      }
    }
  }				/* switch */
  push (db);
}

void
looseaddall (void)
{
  int dbdb;
  int db;
  int i, j, k, l;
  int ii, jj;
  int m;
  int w, x, y, ir, pir;
  l = lengths[level];
  db = 0;
  for (i = placep - 1; i < placep; i++) {
    w = place[i].w;
    x = place[i].x;
    y = place[i].y;
    ir = place[i].ir;
    if (ir == VER) {
      pir = HOR;
    }
    else {
      pir = VER;
    }
    m = analysis[w][level];
    dbdb = analyses[m];
    for (j = m + 1; j <= m + 2 * dbdb;) {
      ii = analyses[j++];
      jj = analyses[j++];
      switch (ir) {
      case HOR:
	k = x + ii;
	l = y - jj;
	break;
      case VER:
	k = x - jj;
	l = y + ii;
      }
      if (checkloc (level, k, l, pir)) {
	wpush (level, k, l, pir);
	++db;
      }
    }
  }
  push (db);
}

void
compare (void)
{ int h,v, ngridsize;
  h=x1-x0;
  v=y1-y0;
  if (h>v) {
    ngridsize=2*h+v;
  }
  else {
    ngridsize=2*v+h;  
  }
  if (
      (100*crosses/level > 100*bestcrosses/bestlevel) ||
      ( 
      ( (level == bestlevel) && (ngridsize<gridsize) )
      && (100*crosses/level == 100*bestcrosses/bestlevel)
      ) ||
      ( 
      ( (level > bestlevel)  )
      && (100*crosses/level == 100*bestcrosses/bestlevel)
      ) 
     ) {
    bestlevel = level;
    bestcrosses = crosses;
    gridsize = ngridsize;
    /* printf("*******************************");  */
    gridout ();
    waitt ();
  }
  /*
   * else { symb=(symb+1)%4; gotoxy(1,1); cprintf("%c",symbols[symb]); } 
   */
}

void
unadd (void)
{				/* reads from heap */
  int i, l, w, x, y, ir;
  placep--;
  wpop (&w, &x, &y, &ir);
  l = lengths[w];
  if (ir == HOR) {
    for (i = x; i < x + l; i++) {
      if ((grid[i][y - 1] == ' ') && (grid[i][y + 1] == ' ')) {
	grid[i][y] = ' ';
      }
      else
	--crosses;
    }
  }
  else {
    for (i = y; i < y + l; i++) {
      if ((grid[x - 1][i] == ' ') && (grid[x + 1][i] == ' ')) {
	grid[x][i] = ' ';
      }
      else
	--crosses;
    }
  }
  y1 = sizeheap[sizeheapp--];
  y0 = sizeheap[sizeheapp--];
  x1 = sizeheap[sizeheapp--];
  x0 = sizeheap[sizeheapp--];
}


int
stop (void)
{

  /* if ((level>=bestlevel) && (crosses<bestcrosses)) return 1; */
  /* if ((level<bestlevel) && ((x1-x0)*(y1-y0)>gridsize) ) return 1; */
  /* if ( (level-1>=4) && (10*crosses<=11*(level-1)) ) return 1; */
  if (crosses < stops[level])
    return 1;
/*  stops[level]=crosses; */  
  return 0;
}

void
doit (void)
{
  int i, j;
  for (i = 0; i < MGRIDSIZE; i++) {
    for (j = 0; j < MGRIDSIZE; j++) {
      grid[i][j] = ' ';
    }
  }
  addcount = 0;
  heapp = -1;
  sizeheapp = -1;
  x0 = y0 = MGRIDSIZE;
  x1 = y1 = 0;
  crosses = 0;
  add (0, MIDDLE, MIDDLE, HOR);
  push (-1);			/* how many more -1=end of everything */
  wpush (0, MIDDLE, MIDDLE, HOR);
  level = 0;
  for (;;) {
    ++level;
    if ((level <= nwords) && !stop ()) {
      if (loose) {
	/* loose */ addall ();
      }
      else {
	addall ();
      }
      pop (&more);
    }
    else
      more = 0;
    while (more == 0) {
      --level;
      unadd ();
      pop (&more);
    }
    if (more == -1)
      return;
    if (more > 0) {
      wpop (&word, &x, &y, &ir);
      add (word, x, y, ir);
      compare ();
      push (--more);
      mores[level] = more;
      wpush (word, x, y, ir);	/* push it back to be able to unadd */
    }
    else {
      printf ("something's wrong");
    }
  }
}

void
analyze (void)
{
  int i, j, k, l, m;
  int db;
  heapp = 0;
  placep = 0;
  for (i = 0; i < nwords; i++) {
    for (j = 0; j < nwords; j++) {
      if (i != j) {
	db = 0;
	for (k = 0; k < lengths[i]; k++) {
	  for (l = 0; l < lengths[j]; l++) {
	    if (words[i][k] == words[j][l]) {
	      db++;
	      push (l);
	      push (k);
	      /*     printf("%s %s %d %d\n",words[i],words[j],k,l); */
	    }
	  }
	}
	push (db);
	push (i);
	push (j);
      }
    }
  }
  if (
      (analyses =
       (int *) malloc ((heapp - 2 * nwords * nwords + 1) * 3 *
		       sizeof (int))) == NULL) {
    printf ("Not enough memory to allocate analysis table\n");
    exit (1);			/* terminate program if out of memory */
  }
  k = 0;
  while (heapp > 0) {
    pop (&j);
    pop (&i);
    pop (&db);
    analysis[i][j] = k;
    analyses[k++] = db;
    for (l = 0; l < db; l++) {
      pop (&m);
      analyses[k++] = m;
      pop (&m);
      analyses[k++] = m;
    }
  }
  if (heapp != 0) {
    printf ("Error: heapp should be 0 not %d", heapp);
    exit (1);
  }
/*
  i=10;j=11;
  m=analysis[i][j];
  db=analyses[m];
  printf("->%s %s %d\n",words[i],words[j],db);
  for (k=1;k<=2*db;k++) {
    printf("%d ",analyses[m+k]);
  }
  exit(1);
*/
}

int
main (int argc, char **argv)
{
  int i, j, k;
  char *sss;
  int l;
  if (argc < 2) {
    printf
      ("\nEducational Crossword Puzzle Generator by Nandor Sieben 3/22/1997\n"
       "usage:crs infile.txt #1 #2\n"
       "\ninfile.txt contains the words one in a line. "
       "You can put an optional clue after the word. "
       "#1 is a number between 2-5 which determines how optimistic the serach is (2 most optimistic)"
       " #2 is the percentage of the words that has to be used.\n");
    exit (1);
  }
  if (argc >= 3)
    goodness = atoi (argv[2]);
  readwords (argv[1]);
  order ();
  analyze ();
/* */
  for (i = 2, j = 1, k = 1; i <= nwords + 3; i++, j++, k++) {
    stops[i] = j;
    if (k == goodness) {
      k = 0;
      if (i >= 4)
	++j;
    }
    stops[i] = j;
  }
/*  for (i = 0; i <=MWORDS; i++) {
    stops[i] = 0;
  }
*/  
  if (argc >= 4) {
    minwords = (nwords * atoi (argv[3])) / 100;
    printf ("minwords %d", minwords);
  }
  loose = 0;
  bestcrosses = 0;
  bestlevel = 1;
  nomix = 0;
  gridsize = MGRIDSIZE * MGRIDSIZE;
  for (;;) {
    ++nomix;
    doit ();
    /* printf(".");  */
    for (k = 1; k <= 3; k++) {
      i = rand () % nwords;
      j = rand () % nwords;
      sss = words[i];
      words[i] = words[j];
      words[j] = sss;
      sss = clues[i];
      clues[i] = clues[j];
      clues[j] = sss;
      l = lengths[i];
      lengths[i] = lengths[j];
      lengths[j] = l;
    }
    free (analyses);
    analyze ();
  }
}