#include <errno.h>
#include <stdlib.h>
#include <stdio.h>

#define CXBOGGLE 4
#define CYBOGGLE 4
#define MAXWORDLEN 80

typedef struct xDictInfo {
  int terminal; /* 0 = previous (to this) does not terminate validly here */
                /* 1 = previous (to this) does terminate validly here */
  char letter;
  struct xDictInfo *next[26];
  struct xDictInfo *up;
} dictInfo;

typedef struct xStrList {
  struct xStrList * next;
  char *word;
} strList;

dictInfo * globalDict = NULL;
char globalBoggle[CXBOGGLE*CYBOGGLE];
strList * globalAnswers = NULL;

dictInfo * createEntry(void);
void createDict(FILE * wordsFile);
void eatspace(char * word);
int fixWord(char * word);
void addWordToDict(char * word);
void storeMatch(dictInfo * match);
int alreadyThere(char * word);
void searchBoggle(int move, dictInfo * lastLetter, int cletters);

int main(int argc, char *argv[]) {
  int retval=0, i;
  char * wordFileName = "/usr/share/dict/words";
  FILE * wordFile;
  FILE * boggleFile;
  strList * answers;

  /* Initialize root of dictionary */
  globalDict = createEntry();

  if(argc != 2 && argc != 3) {
    printf("Deboggle takes two arguments, of the following form:\n"
	   "  deboggle <boggle> [<dict>]\n");
    retval = EINVAL;
  }
  else {
    int read_letters=0;
    int ch;
    if(argc==3) wordFileName = argv[2];

    /* open and read the boggle */
    if((boggleFile = fopen(argv[1], "r")) == NULL) {
      perror("Could not open Boggle File");
      exit(-1);
    }

    while( (read_letters < CXBOGGLE*CYBOGGLE) && 
	   (ch = fgetc(boggleFile))!=EOF ) {
      if(isalpha(ch)) globalBoggle[read_letters++] = tolower(ch);
    }
    
    if(read_letters < CXBOGGLE*CYBOGGLE) {
      printf("Boggle file does not contain a full %dx%d boggle!\n", 
	     CXBOGGLE, CYBOGGLE);
      exit(-1);
    }
    
    fclose(boggleFile);

    /* open and read the word file */
    if((wordFile = fopen(wordFileName, "r")) == NULL) {
      perror("Could not open Word File");
      exit(-1);
    }
    createDict(wordFile);
    fclose(wordFile);

    /* search the boggle for words */
    for(i=0; i<CXBOGGLE*CYBOGGLE; i++)
      searchBoggle(i, globalDict, 0);

    /* print out the results */
    for(answers=globalAnswers; answers!= NULL; answers = answers->next)
      printf("%s\n", answers->word);
  }

  return retval;
}

dictInfo * createEntry(void) {
  dictInfo * retval;

  if ( (retval = malloc(sizeof(*retval))) == 0 ) {
    exit(ENOMEM);
  }

  retval->letter = '\0';
  retval->terminal = 0;
  bzero(&retval->next, sizeof(retval->next));
  retval->up = 0;

  return retval;
}

void eatspace(char * word) {
  char * from;
  from = word;
  while(*from != '\0' && isspace(*from)) from++;
  while(!isspace(*from)) *word++ = *from++;
  
  *word = '\0';
  return;
}

int fixWord(char * word) {
  int good = 1;

  eatspace(word);

  while(*word!='\0') {
    if( (*word < 'a') || (*word > 'z') ) {
       good = 0;
       break;
    }
    word++;
  }

  return good;
}

void createDict(FILE * wordsFile) {
  char wordBuf[MAXWORDLEN];
  while(fgets(wordBuf, MAXWORDLEN, wordsFile) ) {
    if(fixWord(wordBuf)) {
      addWordToDict(wordBuf);
    }  /* word qualified for insertion */
  } /* got another line */
}

/* takes a string of the form [a-z]* */
void addWordToDict(char * word) {
  dictInfo * pDict = globalDict;
  if(*word == '\0') return;
  for(;*word != '\0'; word++) {
    if(pDict->next[*word-'a']==NULL) {
      pDict->next[*word-'a'] = createEntry();
      pDict->next[*word-'a']->letter = *word;
      pDict->next[*word-'a']->up = pDict;
    }
    pDict = pDict->next[*word-'a'];
  }
  pDict->terminal = 1;
}

/* given the point in the dictionary tree where a match has occurred,
   storeMatch() extracts said word and adds it to the found words list.
*/
void storeMatch(dictInfo * match) {
  int len;
  dictInfo *p;
  char * word, *s;

  /* get Length of word matching */
  for(len=0, p=match; p!=NULL; p=p->up, len++) {/*nothing*/}

  word = malloc(len);
  s = word+(len-1);
  *s = '\0';

  for(p=match; p->up != NULL; p=p->up) {
    *--s = p->letter;
  }
  
  if(alreadyThere(word)) free(word);
  else {
    strList * pList = malloc(sizeof(*pList));
    if(pList==NULL) { perror("Out of Memory"); exit(ENOMEM);}
    pList->next = globalAnswers;
    pList->word = word;
    globalAnswers = pList;
  }
  return;
}

/* returns whether a given string is already in the matched list */
int alreadyThere(char * word) {
  strList * pList = globalAnswers;

  for(pList=globalAnswers; pList != NULL; pList = pList->next)
    if(strcmp(pList->word, word)==0)
      return 1;

  return 0;
}


/* arguments: move - the move this invocation is supposed to make, should
	             be a valid next position, but we will check to see if 
		     it's been used yet.
	      lastLetter - the node in matching we got to on last call
	      cletters - number of letters matched before us
*/
   
void searchBoggle(int move, dictInfo * lastLetter, int cletters) {
  char chStolen;

  chStolen = globalBoggle[move];
  globalBoggle[move] = '\0';

  if(chStolen != '\0' && lastLetter->next[chStolen-'a'] != NULL) {
    cletters++; /* how many letters we know have */
    lastLetter = lastLetter->next[chStolen-'a'];
    if(cletters >= 3 && lastLetter->terminal)
      storeMatch(lastLetter);

    /* Now continue with possible extensions to this path */
    {
      int topOK, botOK, leftOK, rightOK;
      topOK   = (move >= CXBOGGLE);
      botOK   = (move < CXBOGGLE*(CYBOGGLE-1));
      leftOK  = ((move%CXBOGGLE) != 0);
      rightOK = ((move%CXBOGGLE) != CXBOGGLE-1);
      
      if(topOK) {
	if(leftOK)  searchBoggle(move-CXBOGGLE-1, lastLetter, cletters);
	if(rightOK) searchBoggle(move-CXBOGGLE+1, lastLetter, cletters);
	searchBoggle(move-CXBOGGLE, lastLetter, cletters);
      }
      if(botOK) {
	if(leftOK)  searchBoggle(move+CXBOGGLE-1, lastLetter, cletters);
	if(rightOK) searchBoggle(move+CXBOGGLE+1, lastLetter, cletters);
	searchBoggle(move+CXBOGGLE, lastLetter, cletters);
      }
      if(leftOK)  searchBoggle(move-1, lastLetter, cletters);
      if(rightOK) searchBoggle(move+1, lastLetter, cletters);
    }
  }

  globalBoggle[move] = chStolen;
  
  return;
}