Code:
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
/* the maximal lentgh of the user input allowed. */
#define MAX_STRING_LENGTH 256
/* the file name of the dictionary file. */
#define DICTIONARY_FILENAME "dictionary.in"
/* read in the dictorany text file, and create an in-memory dictitonary.
* 2nd parameter is the number of words in the dictionary, read from the 1st line of the file;
* the return points to the in-memory array of strings.
*/
char** createDictionary(char* dictFileName, int* wordsCount);
/* free up the space of the in-memory dictionary. */
void freeDictionary(char** pDictionary, int wordsCount);
/* search the dictionary (range from istart to iend) to decide whether the word exists or not: binary search.
* if hit, return 1; otherwise 0.
*/
int searchAword(char* pWord, char** pDictionary, int istart, int iend);
/* swap two characters in a word. */
void swapChar(char* pWord, int iPos1, int iPos2);
/* try all the permutations of the pWord, of which the first nfix characters
* are fixed in the original order and all the rest characters are arbitrarily permuted.
* Thus, start by recursivePermuteLookup(word, 0): this will list all possible permutations,
* especially for each permutation, lookup in dictionary to find whether it is hit or not.
* The return of the function is the number of valid permutation.
*/
int recursivePermuteLookup(FILE *ifOut, char* pWord, int nfix, char** pDictionary, int wordsCount, char* pOriginalWord);
/* main function. */
int main(){
int wordsCount = 0;
char** pDictionary = NULL;
char userInput[MAX_STRING_LENGTH];
char tempstore[MAX_STRING_LENGTH];
/* create in-memory dictionary. */
pDictionary = createDictionary(DICTIONARY_FILENAME, &wordsCount);
//Read in test words.
int cases, i;
FILE *ifp, *ifOut;
ifp = fopen ("dictionary.in", "r");
ifOut = fopen("dictionary2.out", "w");
fscanf (ifp, "%d", &cases);
for (i = 0; i < cases; i++){
fscanf (ifp, "%s", userInput);
fprintf(ifOut, "Jumble #%d:\n", i+1);
strlwr(userInput); // lower case.
strcpy(tempstore, userInput); // keep the original word, for output purpose.
int countHits = recursivePermuteLookup(ifOut, userInput, 0, pDictionary, wordsCount, tempstore); // permute + lookup.
if (countHits == 0){
printf("Sorry, no permutations of %s form a word.\n", tempstore); // print this statement if no hits.
}
fprintf(ifOut, "\n");
}
/* destroy the dictionary. */
freeDictionary(pDictionary, wordsCount);
printf("Thanks for using the Jumble Solver!\n");
fclose(ifp);
system("PAUSE");
return 0;
}
char** createDictionary(char* dictFileName, int* wordsCount){
char** pDictionary = NULL;
FILE* pDictFile = fopen(dictFileName, "r"); // open file.
if (pDictFile != NULL){
/* read the 1st line, get to know how many words in the dictionary. */
fscanf(pDictFile, "%d\n", wordsCount);
/* create in-memory array, each entry points to one word. */
pDictionary = (char **)malloc(*wordsCount * sizeof(char *));
int vi = 0;
int wordLength = 0;
char word[MAX_STRING_LENGTH];
for (vi = 0; vi < *wordsCount; vi++){
fscanf(pDictFile, "%s\n", word); // read in one word.
wordLength = strlen(word) + 1;
pDictionary[vi] = (char *)malloc(wordLength); // create a block to hold the word.
memset(pDictionary[vi], 0, wordLength);
strcpy(pDictionary[vi], word); // copy the word to the memory block.
memset(word, 0, MAX_STRING_LENGTH);
}
fclose(pDictFile); // close file.
}
return pDictionary;
}
void freeDictionary(char** pDictionary, int wordsCount){
int vi = 0;
for (vi = 0; vi < wordsCount; vi++){
free(pDictionary[vi]);
pDictionary[vi] = NULL;
}
free(pDictionary);
}
int searchAword(char* pWord, char** pDictionary, int istart, int iend){
if (istart == iend){
return ((strcmp(pWord, pDictionary[istart])) == 0); // Only 1 word left, is it a hit...
}
else if (istart == (iend - 1)){
/* 2 words left, check any hit... */
return (((strcmp(pWord, pDictionary[istart])) == 0) || ((strcmp(pWord, pDictionary[iend])) == 0));
}
else{
/* binary search: check the word in the middle to decide goto which branch (left/right). */
int imiddle = (int)(floor((istart + iend) / 2));
int compareResult = strcmp(pWord, pDictionary[imiddle]);
if (compareResult == 0){
/* the middle happens to be an exact match. */
return 1;
}
else if (compareResult > 0){
/* pWord is greater than the middle, goes to the right branch. */
return searchAword(pWord, pDictionary, imiddle, iend);
}
else{
/* pWord is smaller than the middle, goes to the left branch. */
return searchAword(pWord, pDictionary, istart, imiddle);
}
}
}
void swapChar(char* pWord, int iPos1, int iPos2){
char tempchar = pWord[iPos1];
pWord[iPos1] = pWord[iPos2];
pWord[iPos2] = tempchar;
}
int recursivePermuteLookup(FILE *ifOut, char* pWord, int nfix, char** pDictionary, int wordsCount, char* pOriginalWord){
int countHits = 0;
if (nfix == strlen(pWord)){
int i........ = searchAword(pWord, pDictionary, 0, wordsCount - 1);
if (i........ == 1){
countHits++;
fprintf(ifOut, "A permutation of %s that is a valid word is %s.\n", pOriginalWord, pWord);
}
}
else{
int vi = 0;
/* from the next position, recursive/swap. */
for (vi = nfix; vi < strlen(pWord); vi++){
swapChar(pWord, nfix, vi); // swap two characters.
countHits = countHits + recursivePermuteLookup(ifOut, pWord, nfix + 1, pDictionary, wordsCount, pOriginalWord); // recursive lookup.
swapChar(pWord, vi, nfix); // swap back.
}
}
return countHits;
}
Originally Posted by gokutrnks
