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

#define WORDNUM 5757 /* Total number of words */
#define	HASH_SIZE WORDNUM*10+1 /* Size of hash table */
#define TRUE 1
#define FALSE 0

typedef struct StrListElement
{	
	int value; /*Index of the word in array "wordlist" */
	struct StrListElement* next;
} StrListElement;

int readInput(FILE* fin, char words[][6]);
int hash(char* word);
void constructHashTable(char inputwords[WORDNUM][6], StrListElement* hashtable[HASH_SIZE]);
void createNeighbors(char word[5], char neighbors[25*5][6]);
int searchHashTable( StrListElement* hashtable[HASH_SIZE], char hashed_words[WORDNUM][6], char* word);
void cleanHashTable(StrListElement* hashtable[HASH_SIZE]);

int main()
{
	int i, j;
	FILE* fin;
	FILE* fout;
	char wordlist[WORDNUM][6]; /* Array of words(one more slot for each word specifying the end of a string) */
	char neighbor_words[25*5][6]; 
	int is_valid_neighbor[25*5];
	int num_valid_neighbors;
	char word[5];
	char neighbor[5];	
	/*Hash table of all words. Words with the same hash values are stored in a singly linked list */
	StrListElement* hashtable[HASH_SIZE]; 

	/* Open and read words from input file into an arra */
	fin = fopen("words.dat","r");
	if(fin == NULL)
	{	
		fprintf(stdout,"Failed to open input file.\n");
		exit(-1);
	}	
	readInput(fin, wordlist);

	
	/* Add these words into a hash table */
	constructHashTable(wordlist,hashtable);


	/* Search neighbors for each word and write to output file */
	fout = fopen("output.txt","w+t");
	if(fout == NULL)
	{	
		fprintf(stdout,"Failed to open output file.\n");
		exit(-1);
	}

	for(i = 0; i < WORDNUM; i++)
	{
		strcpy(word, wordlist[i]);

		/* Create 125 neighbors of the current word*/
		createNeighbors(word,neighbor_words);

		num_valid_neighbors = 0;
		
		/* Search hash table to for valid neighbor words*/
		num_valid_neighbors = 0;
		for(j = 0; j < 125; j++)
		{
			is_valid_neighbor[j] = FALSE;
			strcpy(neighbor, neighbor_words[j]);

			if(searchHashTable(hashtable, wordlist, neighbor) == TRUE)
			{
				is_valid_neighbor[j] = TRUE; 
				num_valid_neighbors ++;
			}
		}

		fprintf(fout,"%s has %d neighbors: ",word, num_valid_neighbors);
		for(j = 0; j < 125; j++)
		{
			if(is_valid_neighbor[j] == TRUE )
			{
				fprintf(fout,"%s ",neighbor_words[j]);
			}			
		}
		fprintf(fout,"\n");
	}

	
	/* Free allocated space for hash table */
	cleanHashTable(hashtable); 		
	
	return 0;
}

/* Read all words from input file */
int readInput(FILE* fin, char words[][6])
{	
	int count = 0;
	char curword[5];	

	/* Initialize all words to be null strings */
	memset(words,'\0', sizeof(words));

	/* Read words from opened file */
	while(fscanf(fin,"%s", curword) != EOF)
	{		
		strcpy(words[count++], curword);		
	}

	return count;
}


/* Compute the hash value of given 5-letter word*/
int hash(char* word)
{
	unsigned int value; 
	/* Maximum unsigned int is 4294967295, so the hash value(<26^6=308915776) will not overflow. */ 	
	
	if( strlen(word) < 5)
	{	printf("Incorrect input to hash function: %d\n",strlen(word));
		exit(-1);
	}

	value = 26*26*26*26*(word[4]-97) +
			26*26*26*(word[3]-97) +
			26*26*(word[2]-97) +
			26*(word[1]-97) +
			(word[0]-97);
	
	return ( value % HASH_SIZE);
}


/* Transfer all the words from array into a hash table*/
void constructHashTable(char inputwords[WORDNUM][6], StrListElement* hashtable[HASH_SIZE])
{
	int i;
	StrListElement* list_ptr;
	StrListElement* cur_ptr;

	/* Initialize the hash table */
	for ( i = 0; i < HASH_SIZE; i++)
		hashtable[i] = NULL;

	for(i = 0; i < WORDNUM; i++)
	{
		/* Create a linked list element for currrent word and 
		add it to the hash table based on the its hash value */
		cur_ptr = (StrListElement*) malloc (sizeof(StrListElement));
		cur_ptr->value = i;				
		
		list_ptr = hashtable[hash(inputwords[i])];
		cur_ptr->next = list_ptr;
		hashtable[hash(inputwords[i])] = cur_ptr;		
	}
}


/* Search the hash table for a given word*/
int searchHashTable( StrListElement* hashtable[HASH_SIZE], char hashed_words[WORDNUM][6], char* word)
{
	int hash_value;
	StrListElement* list_ptr;

	/* Compute the hash value of the given word */
	hash_value = hash(word);

	/* Search the singly linked list of words having same hash value as the given word*/
	list_ptr = hashtable[hash_value];
	while(list_ptr != NULL && strcmp(hashed_words[list_ptr->value], word)!=0 )
	{
		list_ptr = list_ptr->next;
	}

	if(list_ptr==NULL)
		return FALSE;
	else
		return TRUE;	
}


/* Generate the 125 potential neighbors of a given 5 letter word */
void createNeighbors(char word[5], char neighbors[25*5][6])
{
	int count = 0;
	char c;
	int i, j;
	
	for(i = 0; i < 5; i++)
	{		
		for(j = 0; j< 26; j++)
		{
			c = j + 97;
			if( c == word[i]) //only use letter different from word[i]
				continue;
			
			strcpy(neighbors[count], word);			
			neighbors[count][i] = c; /* Created a word differing from word by 1 letter*/			
			count++;
		}
	}	
}

/* Free allocated space for hash table*/
void cleanHashTable(StrListElement* hashtable[HASH_SIZE])
{
	int i; 
	StrListElement* list_ptr;
	StrListElement* temp_ptr;

	for (i = 0; i < HASH_SIZE; i++)
	{
		list_ptr = hashtable[i];
		while(list_ptr != NULL)
		{	
			temp_ptr = list_ptr->next;
			free(list_ptr);
			list_ptr = temp_ptr;
		}
	}
}