/* having problems with:

this is a simple test that will figure things out
*/

/*============================================================
Decryptoquip version 5.0
(C) 1998 by Edwin Olson eolson@mit.edu 
============================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>

#include "d5.h"

#define BUFFSIZE 4096
#define D5_DEFAULTDICTIONARYNAME "dict.dat"

/*============================================================
functions private to decryptoquip
============================================================*/
D5_Word *D5_addWord(D5_Puzzle puzzle, char *inword);
char **D5_getWordDictionary(FILE *data, char pattern[], long *numwords);
long filelength(FILE *file);
void D5_makeWordPattern(char inword[], char pattern[]);
void D5_clearmap(char map[256]);
void D5_printBigMap(D5_Puzzle puzzle);
void copymap(char destmap[], char srcmap[]);
void D5_doSolution(D5_Puzzle puzzle, char map[]);
int D5_qsorthelper(const void *a, const void *b);
void D5_sortWords(D5_Puzzle puzzle);
int D5_solve(D5_Puzzle puzzle, int wordnumber, char map[], char mappedmap[]);
/*==========================================================*/
void D5_wordSolve(D5_Puzzle puzzle)
{

  /* sort the words in an advantageous way */

  /* begin solving */
  D5_solve(puzzle,0,puzzle->cluemap,puzzle->cluemappedmap);

}
/*==========================================================*/
float D5_getEstimatedEntropy(D5_Puzzle puzzle)
{
float entropy=0;
int i;

for (i=0;i<puzzle->numwords;i++)
  {
    entropy+=(log(puzzle->word[i].numdictwords)/log(2.0));
  }

return entropy;
}
/*==========================================================*/
float D5_getActualEntropy(D5_Puzzle puzzle)
{
return (log(puzzle->entropycount)/log(2.0));
}
/*===========================================================*/
void copymap(char destmap[], char srcmap[])
{
memcpy(&destmap['A'],&srcmap['A'],26);
}
/*===========================================================*/
void D5_doSolution(D5_Puzzle puzzle, char map[])
{
int pos;
char thechar;
char *outstring;
int  instringlen;

instringlen=strlen(puzzle->cipherstring);
outstring=malloc(instringlen+1);
if (outstring==NULL)
  {
    printf("out of memory");
    exit(0);
  }

/* we've finished, let's display our answer */
for (pos=0;pos<strlen(puzzle->cipherstring);pos++)
  {
    thechar=toupper(puzzle->cipherstring[pos]);
    
    if (isalpha(thechar) && isalpha(map[thechar]))
      outstring[pos]=map[thechar];
    else
      {
	if (!isalpha(map[thechar]) && isalpha(thechar))
	  /* we don't know what this letter should be */
	  outstring[pos]='_';
	else
	  /* it's punctuation or something */
	  outstring[pos]=thechar;
      }
  }

outstring[pos]='\0';
printf("%s\n",outstring); 

free(outstring);
}
/*==========================================================*/
void D5_sortWords(D5_Puzzle puzzle)
{

qsort(puzzle->word,puzzle->numwords,sizeof(D5_Word),D5_qsorthelper);

}
/*==========================================================*/
int D5_qsorthelper(const void *a, const void *b)
{
D5_Word *w1,*w2;

w1=(D5_Word*) a;
w2=(D5_Word*) b;

if (w1->score<w2->score)
	return -1;

if (w1->score==w2->score)
	return 0;

return 1;
}
/*==========================================================*/
int D5_solve(D5_Puzzle puzzle, int wordnumber, char map[], char mappedmap[])
{
char **dict, *thisword;
char ourmap[256],ourmappedmap[256];
int okay;
int dictw;
int numsolutions,pos;

/* this was lifted almost verbatim from version 4.0 */

dict=puzzle->word[wordnumber].dict;
thisword=puzzle->word[wordnumber].word;

if (!puzzle->word[wordnumber].use)
  {
    if (wordnumber>=(puzzle->numwords-1))
      {
	D5_doSolution(puzzle,map);
	return 1;
      }
    else
      return (D5_solve(puzzle,wordnumber+1,map,mappedmap));
  }

/* loop over the words and recurse over good solutions */

for (dictw=0;dictw<puzzle->word[wordnumber].numdictwords;dictw++)
  {
    puzzle->entropycount++;
    copymap(ourmap,map);
    copymap(ourmappedmap,mappedmap);

    okay=1;

    for (pos=0;pos<puzzle->word[wordnumber].len;pos++)
      {
	if (ourmap[(int) thisword[pos]]==dict[dictw][pos])
	  continue;

	if (ourmap[(int) thisword[pos]]==0 && !ourmappedmap[(int) dict[dictw][pos]])
	  {
	    ourmap[(int) thisword[pos]]=dict[dictw][pos];
	    ourmappedmap[(int) dict[dictw][pos]]=1;
	    continue;
	  }
	okay=0;
	break;
      }

    if (okay)
      {
	if (wordnumber>=(puzzle->numwords-1))
	  {
	    numsolutions++;
	    D5_doSolution(puzzle,ourmap);
	  }
	else
	  numsolutions+=D5_solve(puzzle,wordnumber+1,ourmap,ourmappedmap);
      }
  }
return (numsolutions);
}

/*==========================================================*/
void D5_letterAnalyze(D5_Puzzle puzzle)
{
int a,b,c;
char thismap[26][26];
int x,y,okay;
int wordsnow,lastwordsnow=-1;
int done=0;

/* initialize the puzzle's map -- change to reflect clues!!*/
for (a=0;a<26;a++)
  for (b=0;b<26;b++)
    puzzle->bigmap[a][b]=1;

wordsnow=puzzle->totalwordsloaded;

/* D5_printBigMap(puzzle); */

while (!done)
  {
    /* perform the map manipulation */
    for (a=0;a<puzzle->numwords;a++)
      {
	if (!puzzle->word[a].use)
	  continue;

	/* create a temporary map */
	for (x=0;x<26;x++)
	  for (y=0;y<26;y++)
	    thismap[x][y]=0;
	
	for (b=0;b<puzzle->word[a].numdictwords;b++)
	  {
	   for (c=0;c<puzzle->word[a].len;c++)
	     thismap[puzzle->word[a].word[c]-'A'][puzzle->word[a].dict[b][c]-'A']=1;
	  }

	for (b=0;b<puzzle->word[a].len;b++)
	  {
	    for (c=0;c<26;c++)
	      puzzle->bigmap[puzzle->word[a].word[b]-'A'][c]=
		puzzle->bigmap[puzzle->word[a].word[b]-'A'][c] &
		thismap[puzzle->word[a].word[b]-'A'][c];
	  }
      }
    
    /* elminate words in dictionary */
    for (a=0;a<puzzle->numwords;a++)
	for (b=0;b<puzzle->word[a].numdictwords;b++)
	  {
	    okay=1;
	    for (c=0;c<puzzle->word[a].len;c++)
	      {
		if (puzzle->bigmap[puzzle->word[a].word[c]-'A'][puzzle->word[a].dict[b][c]-'A']==0)
		  {
		    okay=0;
		    break;
		  }
	      }

	    if (!okay)
	      {
		wordsnow--;
		/* printf("Elminated %s\n",puzzle->word[a].dict[b]); */
		free(puzzle->word[a].dict[b]);
		puzzle->word[a].dict[b]=puzzle->word[a].dict[puzzle->word[a].numdictwords-1];
		puzzle->word[a].numdictwords--;
	      }
	  } 
    /* printf("\ndown from %i words to %i\n",puzzle->totalwordsloaded,wordsnow); */
    /*    D5_printBigMap(puzzle); */

    if (wordsnow==lastwordsnow)
      done=1;
    
    lastwordsnow=wordsnow;
  }
}
/*==========================================================*/
void D5_printBigMap(D5_Puzzle puzzle)
{
int a,b;

for (a=0;a<26;a++)
  {
    printf("%c: ",a+'A');

    for (b=0;b<26;b++)
      {
	if (puzzle->bigmap[a][b])
	  printf("%c",b+'A');
	else
	  printf(" ");
      }
    printf("\n");
  }
}

/*==========================================================*/
void D5_setCipherString(D5_Puzzle puzzle, char *in)
{
int len;
int pos,wordpos;
char wordbuffer[BUFFSIZE];
D5_Word *word;

len=strlen(in);
puzzle->cipherstring=malloc(len+1);
memcpy(puzzle->cipherstring,in,len+1);

pos=0;

/* form words and deal with them! */
while (pos<len)
	{
	wordpos=0;
	
	while (!isalpha(in[pos]) && pos<len && len!=0)
		pos++;
		
	while (!isspace(in[pos]) && pos<len)
		{
		if (isalpha(in[pos]))
		    wordbuffer[wordpos++]=toupper(in[pos]);

		pos++;
		}

	wordbuffer[wordpos]=0;

	word=D5_addWord(puzzle,wordbuffer);
	if ((pos-wordpos-1)>=0 && in[pos-wordpos-1]=='~')
	  word->use=0;
	}
}
/*==========================================================*/
D5_Word *D5_addWord(D5_Puzzle puzzle, char *inword)
{
int len;
int loop;

if (puzzle->file==NULL)
  {
  puzzle->file=fopen(puzzle->dictionaryname,"r");

  if (puzzle->file==NULL)
    {
    printf("Can't open dictionary file!\n");
    exit(0);
    }
  }

/* do not add duplicate words */
for (loop=0;loop<puzzle->numwords;loop++)
  if (!strcmp(puzzle->word[loop].word,inword))
    return (&puzzle->word[loop]);

puzzle->word=realloc(puzzle->word,sizeof(D5_Word)*(puzzle->numwords+1));

len=strlen(inword);
puzzle->word[puzzle->numwords].len=len;
puzzle->word[puzzle->numwords].word=malloc(len+1);
puzzle->word[puzzle->numwords].pattern=malloc(len+1);
memcpy(puzzle->word[puzzle->numwords].word,inword,len+1);
D5_makeWordPattern(inword,puzzle->word[puzzle->numwords].pattern);

puzzle->word[puzzle->numwords].use=1;
puzzle->word[puzzle->numwords].dict=D5_getWordDictionary(puzzle->file,puzzle->word[puzzle->numwords].pattern,&puzzle->word[puzzle->numwords].numdictwords);
puzzle->word[puzzle->numwords].score=pow(puzzle->word[puzzle->numwords].numdictwords,1/((float) puzzle->word[puzzle->numwords].len));

/* printf("*%s*\n",inword); */
/* for (len=0;len<puzzle->word[puzzle->numwords].numdictwords;len++)
  printf("\t%s==\n",puzzle->word[puzzle->numwords].dict[len]);
  */
puzzle->totalwordsloaded+=puzzle->word[puzzle->numwords].numdictwords;
puzzle->numwords++;

return(&puzzle->word[puzzle->numwords-1]);
}

/*==========================================================*/
void D5_setClueString(D5_Puzzle puzzle, char *in)
{
  int len;
  int a;
  
  len=strlen(in);
  puzzle->cluestring=malloc(len+1);
  memcpy(puzzle->cluestring,in,len+1);
  
  D5_clearmap(puzzle->cluemap);
  D5_clearmap(puzzle->cluemappedmap);
  
  for (a=0;a<len;a++)
    {
      if (in[a]=='=' && a>0 && a<(len-1))
	{
	  puzzle->cluemap[toupper(in[a-1])]=toupper(in[a+1]);
	  puzzle->cluemappedmap[toupper(in[a+1])]=1;
	}
      
    }
}
/*============================================================
Create Puzzle
============================================================*/
D5_Puzzle D5_createPuzzle(void)
{
D5_Puzzle newpuzzle;

newpuzzle=calloc(sizeof(D5_PuzzleObject),1);
newpuzzle->cipherstring=NULL;

newpuzzle->dictionaryname=malloc(strlen(D5_DEFAULTDICTIONARYNAME)+1);
strcpy(newpuzzle->dictionaryname,D5_DEFAULTDICTIONARYNAME);

newpuzzle->file=NULL;
newpuzzle->word=NULL;
newpuzzle->numwords=0;
newpuzzle->totalwordsloaded=0;
newpuzzle->entropycount=0;

return(newpuzzle);
}

/*============================================================
d5_getWordDictionary
============================================================*/
char **D5_getWordDictionary(FILE *data, char pattern[], long *numwords)
{
char buffer[BUFFSIZE],thispattern[BUFFSIZE];
long pos,a,wordlen,thiswordlen,lastpos;
long high,low;
int compare;
char **dict;

high=filelength(data);
low=0;
lastpos=-1;
wordlen=strlen(pattern);

loop: 
	{
	pos=(high+low)/2;
	if (pos==lastpos)
		{
		*numwords=0;
		return(calloc(1,sizeof(char*)));	
		}
	
	lastpos=pos;
	
	fseek(data,pos,SEEK_SET);

	fgets(buffer,BUFFSIZE,data); /* this line may be incomplete */

	*numwords=0;
	while (*numwords==0)
		{
		fgets(buffer,BUFFSIZE,data); /* this line should be complete */

		*numwords=atoi(buffer);
		}

	fgets(buffer,BUFFSIZE,data); /* this should be the first word */
	thiswordlen=strlen(buffer);
	while (!isalpha(buffer[thiswordlen]))
		buffer[thiswordlen--]='\0';
	
	D5_makeWordPattern(buffer,thispattern);

	compare=strcmp(pattern,thispattern);
	/*	printf("looking for: %s\n\tfound: %s\n",pattern,thispattern); */

	if (compare<0)
		{
		high=pos;
		goto loop;
		}
	
	if (compare>0)
		{
		low=pos;
		goto loop;
		}
	}

/* printf("GOT %i WORDS\n",*numwords); */

dict=calloc(*numwords+1,sizeof(char*));
if (dict==NULL)
	{
	printf("out of memory\n");
	exit(0);
	}
	
a=0;

while (a<*numwords)
	{
	dict[a]=malloc(wordlen+1);
	if (dict==NULL)
		{
		printf("out of memory\n");
		exit(0);
		}
		
	memcpy(dict[a],buffer,wordlen+1);
	dict[a][thiswordlen+1]=0;
	fgets(buffer,BUFFSIZE,data);
	a++;
	}
	
return(dict);
}
/*============================================================
FileLength
returns the size of a file in bytes
============================================================*/
long filelength(FILE *file)
{
long pos;
long origpos;

/*struct stat statbuf;

fstat(fileno(file),&statbuf);
return statbuf.st_size;
*/
origpos=ftell(file);

fseek(file,0,SEEK_END);
pos=ftell(file);

fseek(file,origpos,SEEK_SET);

return (pos);
}

/*============================================================
clearmap
zeros the elements of map from 'A' to 'Z'
Isolated so it can be hand written/ assembly, etc.
============================================================*/
void D5_clearmap(char map[256])
{
memset(&map['A'],0,26);
}

/*============================================================
MakeWordPattern
provided an inword, it returns a letter pattern, e.g. 
HELLO -> ABCCD
============================================================*/
void D5_makeWordPattern(char inword[], char pattern[])
{
char nextletter='A';
char map[256];
int pos;

D5_clearmap(map);

pos=0;

while (inword[pos]!='\0')
	{
	if (map[(int) inword[pos]]==0)
		{
		map[(int) inword[pos]]=nextletter;
		nextletter++;
		}

	pattern[pos]=map[(int) inword[pos]];
	pos++;
	}

pattern[pos]='\0';
}