/**************************************************************************
***************************************************************************
**
**  hangmansolver.c
**
**  A program that might solve the game of hangman.  Written by Tyler
**  Wong (neoncap@sharkfeeder.com), though he may regret and deny it at 
**  some point in the future.
**
**  12.17.01
**
***************************************************************************
***************************************************************************/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define MAXMISSES     (6)


//**************************************************************************
//**
//** STRUCTURES
//**
//**************************************************************************


typedef struct TypeA {
 char word[16];
 struct TypeA* next;
} wordnode_type;

typedef struct TypeB {
 char pattern[16];
 char misses[9];
 long best;
 char bestletter;
 long listlength;
 struct TypeB* next;
} stratnode_type;

//**************************************************************************
//**
//** PROTOTYPES
//**
//**************************************************************************



int main (void) ;
long process (wordnode_type* wordlist, char* misses, char* waste, char* pattern, int level, long listlength, char* alphabet, long limit) ;
void getPattern(char* p, char* word, char c) ;
wordnode_type* addPattern (wordnode_type* plist, char* patt) ;
int isPatternListEmpty(wordnode_type* plist) ;
void clearList(wordnode_type* list) ;
void mergePatterns(char* z, char* a) ;
wordnode_type* makeNewWordList(wordnode_type* list, char* ptn, char c, long* count) ;
wordnode_type* makeWordNode (char* word) ;
void addToStratTable (char* pattern, char* misses, char bestletter, long best, long listlength) ;
stratnode_type* getStrat (char* pattern, char* misses) ;
stratnode_type* findStratNode (char* pattern, char* misses) ;
void sortString(char* s) ;
void clearStratTable (void) ;
void initStratTable (void) ;
long getHashVal (char* str) ;
void setAlphabet(char* alphabet, wordnode_type* wordlist) ;
void makeStratFile(wordnode_type* wordlist) ;
void MSFiteration(FILE* outfile, wordnode_type* wordlist, char* pattern, char* misses, long level) ;
long min (long x, long y) ;
void alphabetizeString (char* s) ;


//**************************************************************************
//**
//** MAIN
//**
//**************************************************************************


int WORDLEN = 0;

int main (void) {
 char s[100] = {0};
 char misses[9] = {0};
 char pattern[20] = {0};
 char waste[27] = {0};
 char alphabet[27] = {0};
 char temp[20];
 wordnode_type* wordlist;
 wordnode_type* ptr;
 FILE* dicfile;
 long wordlistlen = 0;
 long best = 0;

 if( (dicfile = fopen("testdic.txt", "r")) != NULL) {
  wordlist=NULL;
  printf("How many letters? ");
  WORDLEN = atol(fgets(s, 100, stdin));
  fgets(s, 90, dicfile);
  ptr=wordlist;
  while(!feof(dicfile)) {
   strcpy(s, strtok(s, " \n"));
   if(strlen(s)==WORDLEN) {
    if(wordlist==NULL) { wordlist=makeWordNode(s); ptr=wordlist; }
    else { ptr->next = makeWordNode(s); ptr = ptr->next; }
    wordlistlen++;
   }
   fgets(s, 90, dicfile);
  }  
  initStratTable();
  setAlphabet(alphabet, wordlist);
  best = process(wordlist, misses, waste, pattern, 0, wordlistlen, alphabet, wordlistlen);

  makeStratFile(wordlist);
  clearList(wordlist);
  clearStratTable();
  fclose(dicfile); 
 }
 else {
  printf("you fucked up\n");
 }
 printf("\ndone\n");
 return(0);
}

//**************************************************************************
//**
//** PROCESS
//**
//**************************************************************************

time_t LASTCHECK = 0;
time_t TIMENOW = 0; 

long process (wordnode_type* wordlist, char* misses, char* waste, char* pattern, int level, long listlength, char* alphabet, long limit) {
 wordnode_type* newwordlist = NULL;
 wordnode_type* patternlist = NULL;
 wordnode_type* ptr = NULL;
 wordnode_type* ptnptr = NULL;
 stratnode_type* stratnode;
 char temp[10] = {0};
 char newpattern[20] = {0};
 char newmisses[9] = {0};
 char newwaste[27] = {0};
 char newalphabet[27] = {0};
 char c, bestletter;
 long best;
 long newlistlength;
 long duds;
 int i, x, isLetterDead, y;
 long runningtotal=0;

 strncpy(newwaste, waste, 26);
 
// if(level < 3) {
//  printf("\npr %d  (%s)/(%s)   LL: %d  L: %d   %s", level, pattern, misses, listlength, limit, alphabet);
// }

 if(listlength > 12 && (stratnode=getStrat(pattern, misses)) != NULL) {
  best = stratnode->best;
  bestletter = stratnode->bestletter;
 }
 else {
	best=0;
  if(level==0) {   y=8;  }
  else {
   y = 7+level-strlen(misses);
  }
	for(i=0;i<min(y, 26) && listlength>best;i++) {
	 runningtotal=0;
	 c = alphabet[i];

   if( strchr(misses, c) == NULL && strchr(pattern, c) == NULL && strchr(newwaste, c) == NULL) {
	  clearList(patternlist);
	  patternlist = NULL;
	  ptr = wordlist;
	  while(ptr != NULL) {
	   getPattern(newpattern, ptr->word, c);
	    ptnptr = addPattern(patternlist, newpattern);
	   if(patternlist==NULL) { patternlist=ptnptr; };
	   ptr = ptr->next;
	  }
	  if(isPatternListEmpty(patternlist)) {
	   sprintf(newwaste, "%s%c\0", newwaste, c);   
	  }
	  else {
	   runningtotal = 0; duds=0; isLetterDead=0; newlistlength=0;
	   ptnptr = patternlist;
	   while(ptnptr != NULL && !isLetterDead) {
	    x=0;
	    strncpy(newmisses, misses, 9);
	    strncpy(newpattern, ptnptr->word, 20);
	    if(strlen(newpattern)==0) {
	     sprintf(newmisses, "%s%c\0", newmisses, c);
	    }
	    if(strlen(newmisses) < MAXMISSES) {
	     clearList(newwordlist);
	     newlistlength=0;
	     newwordlist = makeNewWordList(wordlist, newpattern, c, &newlistlength);
	     mergePatterns(newpattern, pattern);
	     if(newlistlength==1) {
	      x=1;
	     }
	     else {
        setAlphabet(newalphabet, newwordlist);

	      x = process(newwordlist, newmisses, newwaste, newpattern, level+1, newlistlength, newalphabet, min(listlength-best,limit)-duds);
	     }
	    }
	    else {
	     x=0;
	    }   
	    runningtotal += x;
	    duds += (newlistlength-x);
	    if(duds>=(listlength-best) || duds>=limit) {
	     isLetterDead=1;
	    }
	    ptnptr = ptnptr->next;
	   }
     if(isLetterDead) {
      runningtotal=0;
     }
	   if(best<runningtotal) { 
	    best=runningtotal; bestletter=c; 
	   }
	  }
   }
  }
  if(listlength > 12 && best>0) {
   addToStratTable(pattern, misses, bestletter, best, listlength);
  }
 }
 clearList(patternlist);
 clearList(newwordlist);
 return(best);
} 
 
 
 
 
//**************************************************************************
//**************************************************************************
//**
//** LIST FUNCTIONS
//**
//**************************************************************************
//**************************************************************************


//**************************************************************************
//** getPattern
//**************************************************************************


void getPattern(char* p, char* word, char c) {
 int found;
 int x;
 x=0; found=0;
 while(word[x] != '\0' && x < 30) {
  if(word[x]==c) { p[x]=c; found=1; }
  else { p[x]='-'; }
  x++;
 }
 p[x]='\0';
 if(!found) { p[0]='\0'; }
}

//**************************************************************************
//** addPattern
//**************************************************************************

wordnode_type* addPattern (wordnode_type* plist, char* patt) {
 wordnode_type* curr;
 wordnode_type* prev;
 curr=plist;
 prev=NULL;
 while(curr !=NULL && strcmp(curr->word, patt)!=0) { 
  prev = curr;
  curr = curr->next;
 }
 if(curr==NULL) {
  curr = makeWordNode(patt); 
  if(prev!=NULL) { prev->next = curr; }
 }
 return(curr);
}

//**************************************************************************
//** isPatternListEmpty
//**************************************************************************

int isPatternListEmpty(wordnode_type* plist) {
 int retval, count;
 char temp[50] = {0};
 wordnode_type* ptr;
 ptr=plist;
 retval=0; count=0;
 while(ptr!=NULL && count<2) {
  strncpy(temp, ptr->word, 20);
  ptr=ptr->next;
  count++;
 }
 if(count<2 && strlen(temp)==0) {
  retval=1;
 }
 return(retval);
}


//**************************************************************************
//** clearList
//**************************************************************************

void clearList(wordnode_type* list) {
 wordnode_type* curr;
 wordnode_type* prev;
 
 curr=list;
 prev=NULL;
 while(curr!=NULL) {
  prev=curr;
  curr=curr->next;
  free(prev);
 }
}



//**************************************************************************
//** mergePatterns
//**************************************************************************

void mergePatterns(char* z, char* a) {
 int i, done;
 char temp[50] = {0};
 i=0; done=0;
 if(strlen(z)==0) { strncpy(z, a, 20); }
 else if(strlen(a)>0) {
  strncpy(temp, a, 20);
  do  {
   if(z[i]!='-') {
    temp[i] = z[i];
   }
   i++;
  } while(z[i]!='\0' && i < 50);
  strncpy(z, temp, 20);
 }
}



//**************************************************************************
//** makeNewWordList
//**************************************************************************

wordnode_type* makeNewWordList(wordnode_type* list, char* ptn, char c, long* count) {
 int ok, x, noptn;
 char wc;
 wordnode_type* retval;
 wordnode_type* newptr;
 wordnode_type* curr;
 wordnode_type* prev;
 curr=list;
 prev=NULL;
 newptr=NULL;
 retval=NULL;
 if(strlen(ptn)==0) { noptn=1; } else { noptn=0; }
 while(curr!=NULL) {
  ok=0;
  if(noptn) { 
   if(strchr(curr->word, c)==NULL) { ok=1; }
  }
  else {
   ok=1; x=0;
   while(ptn[x] != '\0' && ok && x<50) {
    wc = curr->word[x];
    if( (ptn[x] != '-' && ptn[x] != wc) || (ptn[x]=='-' && wc==c) ) {
     ok=0;
    }
    x++;
   }
  }
  if(ok) {
   *count += 1; 
   if(newptr==NULL) {
    newptr = makeWordNode(curr->word);
    retval = newptr;
   }
   else {
    newptr->next = makeWordNode(curr->word);
    newptr = newptr->next;
   }
  }
  prev=curr;
  curr=curr->next;
 }
 return(retval);
}

    

//**************************************************************************
//** makeWordNode
//**************************************************************************


wordnode_type* makeWordNode (char* word) {
 wordnode_type* newnode;
 char temp[10];
 newnode = (wordnode_type*)malloc(sizeof(wordnode_type));
 if(newnode==NULL) {
  printf("word node failed allocation\n");
  fgets(temp, 9, stdin);
 }
 strncpy(newnode->word, word, 20);
 newnode->next = NULL;

 return(newnode);
}



//**************************************************************************
//**************************************************************************
//**
//** Strategy Tree
//**
//**************************************************************************
//**************************************************************************

//**************************************************************************
//** addToStratTable
//**************************************************************************

#define PRIME_A  (5003)

stratnode_type* strathead[PRIME_A] = {0};

void addToStratTable (char* pattern, char* misses, char bestletter, long best, long listlength) {
 stratnode_type* curr;
 stratnode_type* prev;
 stratnode_type* newnode;
 char temp[27] = {0};
 char hashstr[100] = {0};
 long hashval;

 strncpy(temp, misses, 9);
 sortString(temp);
 sprintf(hashstr, "%s%s\0", pattern, temp);
 hashval=getHashVal(hashstr); 
 curr=strathead[hashval];
 prev=NULL;
 while(curr != NULL && 
       ( ( strcmp(pattern, curr->pattern)>0 ) || 
         ( ( strcmp(pattern, curr->pattern)==0 ) && ( strcmp(temp, curr->misses)>0 )
         )
       )
      ) {
  prev=curr;
  curr=curr->next;
 }
 newnode = (stratnode_type*)malloc(sizeof(stratnode_type));
 if(newnode==NULL) {
  printf("strat node failed allocation, exit immediately\n");
  fgets(temp, 9, stdin);
 }
 strcpy(newnode->pattern, pattern);
 strcpy(newnode->misses, temp);
 newnode->bestletter = bestletter;
 newnode->best = best;
 newnode->listlength = listlength;
 newnode->next = curr;
 if(prev==NULL) {
  strathead[hashval] = newnode;
 }
 else {
  prev->next=newnode;
 }
}



//**************************************************************************
//** findStrat
//**************************************************************************


stratnode_type* getStrat (char* pattern, char* misses) {
 stratnode_type* curr;
 stratnode_type* retval;
 char temp[27];
 strncpy(temp, misses, 9);
 sortString(temp);

 curr = findStratNode(pattern, temp);
 if(curr!=NULL && strcmp(pattern, curr->pattern)==0 && strcmp(temp, curr->misses)==0) {
  retval = curr;
 }
 else {
  retval = NULL;
 }
 return(retval);
}


//**************************************************************************
//** findStratNode
//**************************************************************************

stratnode_type* findStratNode (char* pattern, char* misses) {
 stratnode_type* curr;
 stratnode_type* prev;
 stratnode_type* retval;
 char temp[27];
 char hashstr[100];
 long hashval;
 int  x;
 strncpy(temp, misses, 9);
 sprintf(hashstr, "%s%s\0", pattern, temp); 
 hashval=getHashVal(hashstr);
 curr=strathead[hashval];
 prev=NULL;
 while(curr != NULL && 
       ( ( strcmp(pattern, curr->pattern)>0 ) || 
         ( ( strcmp(pattern, curr->pattern)==0 ) && ( strcmp(temp, curr->misses)>0 )
         ) 
       )     
      )  {
  prev=curr;
  curr=curr->next;
 }
 retval = curr;
 return(retval);
}


//**************************************************************************
//** getHashVal
//**************************************************************************

long getHashVal (char* str) {
 int x;
 long retval;
 retval=0;
 for(x=0;x<strlen(str);x++) {
  retval += (pow(2,x) * (str[x]-44));
 }
 if(retval < 0) {   retval *= -1;  printf("GHV: something went awry!");  }
 retval %= PRIME_A; 
 return(retval);
}



//**************************************************************************
//** sortString
//**************************************************************************

void sortString(char* s) {
 char t;
 int len, i, j;
 len=strlen(s);
 for(i=0;i<len-1;i++) {
  for(j=i+1;j<len;j++) {
   if(s[i] > s[j]) {
    t=s[i]; s[i]=s[j]; s[j]=t;
   }
  }
 }
}


//**************************************************************************
//** clearStratTable
//**************************************************************************
 
void clearStratTable (void) {
 int i;
 stratnode_type* curr;
 stratnode_type* prev;
 for(i=0;i<PRIME_A;i++) {
  curr = strathead[i];
  prev = NULL;
  while(curr!=NULL) {
   prev=curr; curr=curr->next; free(prev);
  }
 }
}


//**************************************************************************
//** initStratTable
//**************************************************************************

void initStratTable (void) {
 int i;
 for(i=0;i<PRIME_A;i++) {
  strathead[i] = NULL;
 }
}




//**************************************************************************
//** makeStratFile
//**************************************************************************


void makeStratFile(wordnode_type* wordlist) {
 FILE* outfile;
 char filestr[50] = {0};
 sprintf(filestr, "strat.%dletter.txt\0", WORDLEN);
 if( (outfile=fopen(filestr, "w"))==NULL) {
  printf("outfile won't open, you tard\n");
 }
 else {
  MSFiteration(outfile, wordlist, "\0", "\0", 0);
 }
 fclose(outfile);
}





//**************************************************************************
//** MSFiteration
//**************************************************************************


void MSFiteration(FILE* outfile, wordnode_type* wordlist, char* pattern, char* misses, long level) {
 stratnode_type* strat = NULL;
 wordnode_type* patternlist = NULL;
 wordnode_type* ptr = NULL;
 wordnode_type* ptnptr = NULL;
 wordnode_type* newwordlist = NULL;
 char newpattern[20];
 char newmisses[20];
 char temp[20];
 char spaces[50] = {0}; 
 char pstr[20] = {0};
 char mstr[10] = {0};
 int i;
 char bestletter;
 long best;
 long listlength;
 long newlistlength;
 for(i=0;i<(level);i++) {
  sprintf(spaces, "%s  \0", spaces);
 }
 strat=getStrat(pattern, misses);
 if(*pattern==0) { strcpy(pstr, "**\0"); }
 else  { strcpy(pstr, pattern); }
 if(*misses==0) { strcpy(mstr, "**\0"); }
 else  { strcpy(mstr,misses); alphabetizeString(mstr); }
 if(strlen(misses) < MAXMISSES && strat != NULL) {
  bestletter = strat->bestletter;
  best = strat->best;
  listlength = strat->listlength;
  fprintf(outfile, "%s%d. [%s, %s]    [%c]    [%d/%d]\n", spaces, level, pstr, mstr, bestletter, best, listlength);
	clearList(patternlist);
	patternlist = NULL;
  ptr = wordlist;
	while(ptr != NULL) {
	 getPattern(newpattern, ptr->word, bestletter);
	 ptnptr = addPattern(patternlist, newpattern);
	 if(patternlist==NULL) { patternlist=ptnptr; };
	 ptr = ptr->next;
  }
  newlistlength=0;
	ptnptr = patternlist;
	while(ptnptr != NULL) {
	 strncpy(newmisses, misses, 9);
	 strncpy(newpattern, ptnptr->word, 20);
	 if(strlen(newpattern)==0) {
	  sprintf(newmisses, "%s%c\0", newmisses, bestletter);
	 }
	 clearList(newwordlist);
 	 newlistlength=0;
	 newwordlist = makeNewWordList(wordlist, newpattern, bestletter, &newlistlength);
	 mergePatterns(newpattern, pattern);
	 MSFiteration(outfile, newwordlist, newpattern, newmisses, level+1);  
   ptnptr = ptnptr->next;
  } 	
 }
 else {
  fprintf(outfile, "%s%d. [%s, %s]    \n", spaces, level, pstr, mstr);
  ptr = wordlist;
  while(ptr!=NULL) {
   fprintf(outfile, "%s %s\n", spaces, ptr->word);
   ptr=ptr->next;
  }
 }
 clearList(newwordlist);
 clearList(patternlist);
}




//**************************************************************************
//**************************************************************************
//**
//** setAlphabet
//**
//**************************************************************************
//**************************************************************************



void setAlphabet(char* alphabet, wordnode_type* wordlist) {
 wordnode_type* ptr;
 long Lcount[27] = {0};
 char tempstr[27] = {0};
 char temp[10] = {0};
 int x,y,i, j;
 char t;
 long n;
 strcpy(tempstr, "ABCDEFGHIJKLMNOPQRSTUVWXYZ\0");
 ptr=wordlist;
 while(ptr!=NULL) {
  for(i=0;i<26;i++) {
   if(strchr(ptr->word, tempstr[i])!=NULL) {
    Lcount[tempstr[i]-65] += 1;
   }
  }
  ptr=ptr->next;
 }
 for(x=0;x<25;x++) {
  for(y=x+1;y<26;y++) {
   if(Lcount[x] < Lcount[y]) {
    t = tempstr[x]; tempstr[x] = tempstr[y]; tempstr[y] = t;
    n = Lcount[x]; Lcount[x] = Lcount[y]; Lcount[y] = n;
   }
  }
 }
 strncpy(alphabet, tempstr, 26);
}  



//**************************************************************************
//**************************************************************************
//**
//** min
//**
//**************************************************************************
//**************************************************************************

long min (long x, long y) {
 long retval;
 if(x<y) { retval=x; } else { retval=y; }
 return(retval);
}



//**************************************************************************
//**************************************************************************
//**
//** alphabetizeString
//**
//**************************************************************************
//**************************************************************************


void alphabetizeString (char* s) {
 int x, y, len;
 char t;
 len = strlen(s);
 for(x=0;x<len-1;x++) {
  for(y=x+1;y<len;y++) {
   if(s[x]>s[y]) {
    t = s[x]; s[x] = s[y], s[y]=t;
   }
  }
 }
}