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



#define MGRIDSIZE 100
#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 swap(a,b) swapvar=a; a=b ;b=swapvar;

int             swapvar;

char           *words[MWORDS + 3];
int             lengths[MWORDS + 3];
char           *clues[MWORDS + 3];
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];

#ifndef OCHECK

char            thor[MGRIDSIZE][MGRIDSIZE];
char            tver[MGRIDSIZE][MGRIDSIZE]; 
char            tbeg[MGRIDSIZE][MGRIDSIZE]; 
char            tend[MGRIDSIZE][MGRIDSIZE];

#endif

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;

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[3 * 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, 3 * 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++) {
#ifdef OCHECK
      cc=0;
#else
      /* cc=tend[j][i]; */ cc=0;
#endif
      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 + 1), 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 + 1), loose);
  fprintf(outtex, "\\bye");
  fclose(out);
  fclose(outtex);

}


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

#ifdef OCHECK

void
add(int w, int x, int y, int ir)
{				/* reads from the heap */
  int             i, l, oldcrosses;
/*  addwrite(w,x,y); */
  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;
    loosex = x;
    loosey = y;
    loosel = l;
    looseir = ir;
  }
  else {
    loose = 0;
  }
}

#else

void
add(int w, int x, int y, int ir)
{				/* reads from the heap */
  int             i, l, oldcrosses;
  int             xir, yir;
/*  addwrite(w,x,y); */
  xir = ir % 2;
  yir = ir / 2;
  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);
  switch (ir) {
  case HOR:
    ++thor[x-1][y];
    ++thor[x+l][y];
    ++tver[x-1][y];
    ++tver[x+l][y];
    break;
  case VER:
    ++thor[x][y-1];
    ++thor[x][y+l];
    ++tver[x][y-1];
    ++tver[x][y+l];
  }
  for (i = 0; i < l; i++) {
    switch (ir) {
    case HOR:
      ++thor[x + i ][y - 1];
      ++tend[x + i ][y - 1];
      ++thor[x + i ][y + 1];
      ++tbeg[x + i ][y + 1];
      break;
    case VER:
      ++tver[x - 1][y + i ];
      ++tend[x - 1][y + i ];
      ++tver[x + 1][y + i ];
      ++tbeg[x + 1][y + 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;
    loosex = x;
    loosey = y;
    loosel = l;
    looseir = ir;
  }
  else {
    loose = 0;
  }
  }

#endif

#ifdef OCHECK

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;
}

#else

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 (tbeg[x][y] && grid[x][y]==' ')
      return 0;
    if (tend[x + l - 1][y] && grid[x + l - 1][y]==' ')
      return 0;
    for (i = 0; i < l; i++) {
      if (grid[x + i][y] != ' ') {
	++ig;
	if (grid[x + i][y] != words[w][i])
	  return 0;
      }
      else {
	 if (thor[x + i][y])
           return 0;
      }
    }
    break;
  case VER:
    if (tbeg[x][y] && grid[x][y]==' ')
      return 0;
    if (tend[x][y + l - 1] && grid[x][y +l - 1]==' ')
      return 0;
    for (i = 0; i < l; i++) {
      if (grid[x][y + i] != ' ') {
	++ig;
	if (grid[x][y + i] != words[w][i])
	  return 0;
      }
      else
	if (tver[x][y + i])
          return 0; 
    }
  }
  return ig;
}

#endif

void
addall(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
looseaddall(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
compare(void)
{
  if (level < minwords) {
    if (bestlevel >= minwords)
      return;
    if (level < bestlevel)
      return;
  }
  if (
      (crosses * (bestlevel + 1) > bestcrosses * (level + 1)) ||
      ((level > bestlevel) && (crosses * (bestlevel + 1) == bestcrosses * (level + 1))) ||
      ((level == bestlevel) && (crosses * (bestlevel + 1) == bestcrosses * (level + 1)) && ((y1 - y0) * (x1 - x0) < gridsize))
    ) {
    bestlevel = level;
    bestcrosses = crosses;
    gridsize = (y1 - y0) * (x1 - x0);
    /* printf("*******************************");  */
    gridout();
    waitt();
  }
  /*
   * else { symb=(symb+1)%4; gotoxy(1,1); cprintf("%c",symbols[symb]); } 
   */
}

#ifdef OCHECK

void
unadd(void)
{				/* reads from heap */
  int             i, l, w, x, y, ir;
  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--];
}

#else

void
unadd(void)
{				/* reads from heap */
  int             i, l, w, x, y, ir;
  wpop(&w, &x, &y, &ir);
  l = lengths[w];
  switch (ir) {
  case HOR:
    --thor[x - 1][y];
    --tver[x - 1][y];
    --thor[x + l][y];
    --tver[x + l][y];
    break;
  case VER:
    --thor[x][y - 1];
    --tver[x][y - 1];
    --thor[x][y + l];
    --tver[x][y + l];
  }
  if (ir == HOR) {
    for (i = x; i < x + l; i++) {
      --thor[i][y - 1];
      --tend[i][y - 1];
      --thor[i][y + 1];
      --tbeg[i][y + 1];
      if ((grid[i][y - 1] == ' ') && (grid[i][y + 1] == ' ')) {
	grid[i][y] = ' ';
      }
      else
	--crosses;
    }
  }
  else {
    for (i = y; i < y + l; i++) {
      --tver[x - 1][i];
      --tend[x - 1][i];
      --tver[x + 1][i];
      --tbeg[x + 1][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--];
}

#endif


void
orderlevel(void)
{
  int             oheapp;
  int             i, j, db;
  int             sizes[MONLEVEL];
  int             levelcros[MONLEVEL];
  int             maxcros;
  int             a, b, c, d;
  maxcros = 0;
  oheapp = heapp;
  pop(&db);
  if (db == 0) {
    heapp = oheapp;
    return;
  }
  for (i = 1; i <= db; i++) {
    wpop(&a, &b, &c, &d);
    add(a, b, c, d);
    levelcros[i] = crosses;
    if (crosses > maxcros)
      maxcros = crosses;
    heapp += 4;
    unadd();
  }
  heapp = oheapp;
  for (i = 1; i <= db - 1; i++) {
    for (j = i + 1; j <= db; j++) {
      if (levelcros[j] < levelcros[i]) {
	swap(levelcros[j], levelcros[i]);
	swap(sizes[j], sizes[i]);
	swap(heap[heapp - j * 4], heap[heapp - i * 4]);
	swap(heap[heapp - j * 4 + 1], heap[heapp - i * 4 + 1]);
	swap(heap[heapp - j * 4 + 2], heap[heapp - i * 4 + 2]);
	swap(heap[heapp - j * 4 + 3], heap[heapp - i * 4 + 3]);
      }
    }
  }

   pop(&db); while (levelcros[db] < maxcros) { heapp -= 4; --db; }
   push(db);

}

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;
  return 0;
}

void
doit(void)
{
  int             i, j;
  for (i = 0; i < MGRIDSIZE; i++) {
    for (j = 0; j < MGRIDSIZE; j++) {
      grid[i][j] = ' ';
#ifndef OCHECK
      thor[i][j] = 0;
      tver[i][j] = 0;
      tbeg[i][j] = 0;
      tend[i][j] = 0;
#endif
    }
  }
  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();
      /* orderlevel(); */
      pop(&more);
    }
    else
      more = 0;
    while (more == 0) {
      --level;
      unadd();
#ifdef DEBUG
      printf("Unadd %s", words[level]);
      gridout();
      waitt();
#endif
#ifdef __BORLANDC__
      if (kbhit())
	exit(0);
#endif
      pop(&more);
    }
    if (more == -1)
      return;
    if (more > 0) {
      wpop(&word, &x, &y, &ir);
      add(word, x, y, ir);
#ifdef DEBUG
      printf("Add %s", words[level]);
      gridout();
      waitt();
#endif
      compare();
      push(--more);
      mores[level] = more;
      wpush(word, x, y, ir);	/* push it back to be able to unadd */
    }
    else {
      printf("something's wrong");
    }
  }
}

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:\nujpuzz 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();
  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;
  }
  if (argc >= 4)
    minwords = (nwords * atoi(argv[3])) / 100;
  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;
    }
  }
}