/*
 *                          *********************
 *                          *  B O G G L E . C  *
 *                          *********************
 */

/*)BUILD	$(PROGRAM)	= boggle
		$(STACK)	= 3000
		$(TKBOPTIONS)	= {
			STACK = 1024
			ACTFIL = 6
			UNITS = 6
		}
*/

/*
 *
 *
 *
 * Written by:
 *    Bob Denny
 *    Creative System Design Co.
 *    Pasadena, CA  91107
 *
 * N O T E:
 *       This version doesn't handle "Qu" cube face,
 *       and it is for "Big Boggle", 5x5 board.
 *
 * Edits:
 *    X02.00  25-Aug-81   RBD    Major changes from 2 phase boggle.
 */

/* #define	biggerdebug	*/
/* #define bigdebug		*/
/* #define debug		*/

#include <stdio.h>

#define  UNUSED 0
#define  USED  1
/*
 * Static data structures
 */
char  board [5] [6];                   /* BOGGLE board letter layout */
int   flags [5] [5];                   /* "letter used" flags for board */
char  word  [18];                      /* Test word buffer */
char  dicwrd[18];                      /* Current dictionary word */
int maxw = 7;                          /* Max length word to generate */
int nwords = 0;                        /* No. of words generated */
long tstart, tstop;                    /* Start/stop times */
FILE *ofp;                             /* Output file */
FILE *dfp;                             /* Dictionary file */

/*
 * External functions which return other than integers
 */
extern char tolower();
extern long ftell();
extern long time();

/*
 * This turns off C's argv prompt
 */
#ifdef		decus
int $$narg = 1;
#endif

/*
 * Main program
 */
main(argc,argv)
int argc;
char *argv[];
   {
   register int row, col;
   char ch;
   long  dicpos;                       /* Dictionary file position */

#ifdef debug
   ofp = stdout;
#else
   if((ofp = fopen("BOGGLE.OUT", "w")) == NULL)
     error("Failed to open output file BOGGLE.OUT\n");
#endif

   if((dfp = fopen("BOGGLE.DIC", "r")) == NULL)
     error("Failed to open dictionary file BOGGLE.DIC\n");

   printf("Welcome to BOGGLE:\n");
   printf("My words will be written to the screen and to file BOGGLE.OUT\n\n");
   printf("Enter cube letters one row at a time:\n");
   for(row=0; row<5; row++)
      {
again:
      printf("Row %d: ", row);         /* Prompt for a row */
      gets(board[row]);                /* Get a row */
      for(col=0; col<5; col++)         /* Fold to upper case */
         {
         if(isalpha(board[row][col]) != TRUE)
            {
            printf("\"%c\" is not a letter!\n", board[row][col]);
            goto again;
            }
         else
            board[row][col] = tolower(board[row][col]);
         }
      }
   fprintf(ofp, "%c %c %c %c %c\n",board[0][0],board[0][1],board[0][2],
                             board[0][3],board[0][4]);
   fprintf(ofp, "%c %c %c %c %c\n",board[1][0],board[1][1],board[1][2],
                             board[1][3],board[1][4]);
   fprintf(ofp, "%c %c %c %c %c\n",board[2][0],board[2][1],board[2][2],
                             board[2][3],board[2][4]);
   fprintf(ofp, "%c %c %c %c %c\n",board[3][0],board[3][1],board[3][2],
                             board[3][3],board[3][4]);
   fprintf(ofp, "%c %c %c %c %c\n\n",board[4][0],board[4][1],board[4][2],
                             board[4][3],board[4][4]);
/*
 * Load first dictionary word.
 */
   dicpos = 0;
   fgetss(dicwrd, 18, dfp);
/*
 * Start words in ASCII order.
 */
   printf("\nOK ... here goes\n");
   tstart = time(0);                   /* Mark start time */
   for(ch = 'a'; ch <= 'z'; ch++)      /* ASCII dependent */
      {
      while(dicwrd[0] < ch)            /* Sync dictionary to start letter */
         {
         dicpos = ftell(dfp);          /* Save dict. position for start ltr */
         fgetss(dicwrd, 18, dfp);
         }
#ifdef debug
      printf("Checking for letter \'%c\'  dict at \"%s\"\n", ch, dicwrd);
#endif
      for(row = 0; row < 5; row++)
         for(col = 0; col<5; col++)
            if ((word[0] = board[row][col]) == ch)
               {
               fseek(dfp, dicpos, 0);  /* Resync dictionary file */
               clear();                /* Clear the flags board */
               flags[row][col] = USED; /* Mark starting cell used */
#ifdef debug
               printf("Starting [%d,%d] = \"%c\"\n", row, col, ch);
#endif
               extend(row, col, 0, dicpos); /* Gen/check words recursively */
               }
      }
   fclose(dfp);
#ifndef debug
   fclose(ofp);
#endif
   tstop = time(0);
   printf("\nI\'m finished. %d words generated in %ld sec.\n",
      nwords, tstop-tstart);
   }
/**** END OF MAIN PROGRAM ****/

/*
 * Clear out the flags board. Initialize all cells to UNUSED.
 */
clear()
   {
   register int row,col;

   for(row=0; row<5; row++)
      for(col=0; col<5; col++)
         flags[row][col] = UNUSED;
   }

/*
 * Form possible words by recursive descent.
 * On entry, 'index' is the string index in 'word' of the
 * terminating character.
 */
extend(row, col, index, dicpos)
int row, col, index;
long dicpos;
   {
   register int i, j;
   int		rowp1, colp1;
   register char ch;
   int cmpval;

   rowp1 = row + 1;
   colp1 = col + 1;
   if(index++ > maxw-2) return;            /* Word too long. (bump index) */
#ifdef debug
   printf("Extend:  Index = %d  Word = \"%s\"\n", index, word);
#endif
   for(ch = 'a'; ch <= 'z'; ch++)
      {
      word[index] = ch;                /* Add this letter to word */
      word[index+1] = '\0';
      while(ccmp(dicwrd, word, index+1) < 0) /* Advance dict. appropriately */
         {
         dicpos = ftell(dfp);          /* Save dict. position for start ltr */
         fgetss(dicwrd, 18, dfp);
         }
#ifdef bigdebug
      printf("   ch = \'%c\'  dict advanced to \"%s\"\n", ch, dicwrd);
#endif
      for(i = row-1; i <= rowp1; i++)
         {
         if(i<0 || i>4) continue;      /* Handle boundary conditions */
         for(j = col-1; j <= colp1; j++)
            {
#ifdef biggerdebug
	    printf(" row %d, col %d\n", i, j);
#endif
            if(j<0 || j>4) continue;   /* Handle boundary conditions */
#ifdef biggerdebug
		i, j, flags[i][j], i, j, board[i][j]);
#endif
            if(flags[i][j] == UNUSED && (board[i][j]) == ch)
               {
#ifdef debug
               printf("      cell [%d,%d]:\n", i, j);
               printf("         trial word is \"%s\"\n", word);
#endif
               fseek(dfp, dicpos, 0);  /* Back up to prev. start point */
               fgetss(dicwrd, 18, dfp);

               while((cmpval = ccmp(dicwrd, word, index+1)) < 0) /* Scan fwd. */
                  fgetss(dicwrd, 18, dfp);
#ifdef debug
               printf("         dict resync'd to \"%s\"\n", dicwrd);
#endif
               if(cmpval == 0)
                  {
                  if(dicwrd[index+1] == '\0')   /* If they match exactly */
                     {
                     fputss(dicwrd, ofp);       /* Write out the good word */
                     puts(dicwrd);
                     nwords++;                  /* Count a good word */
                     fgetss(dicwrd, 18, dfp);   /* Get another dict. word */
                     }
                  flags[i][j] = USED;        /* Mark this cell used */
                  extend(i, j, index, dicpos);/* Try to extend the word */
                  flags[i][j] = UNUSED;      /* Unmark the cell */
                  word[index+1] = '\0';      /* Chop the word back */
                  }
               }
            }
         }
      }
#ifdef debug
   printf("----- end extend ----\n");
#endif
   }                                   /**** WOW ****/

dummy() {}

/*
 * ccmp()
 *
 * Compare first n characters in strings.
 * return like strcmp().
 */
int ccmp(s1, s2, n)
register char *s1;
register char *s2;
int n;
   {
   register int diff;
   while(n--)
      {
      if((diff = *s1++ - *s2++) != 0) return(diff);
      }
   return(0);
   }