/*
 * By: Sir, Rohan, and Matt
 * Purpose: Random wordsearch generator
 * Date: 11/8/2011
 */

/*
	(this comment is the note/flowchart/whatever structured document he wants to refer to how it works)

	Design:

	 - Store the wordsearch as a multidensional array. Passed between functions using the weirdo syntax
	   in the prototypes:  char(* board)[25]

	 - Store each word in an array of pointers to character arrays. Rather than using strcpy and strcmp
	   and so on, I'll just pass pointers arround since it requires less effort and function calls, 

	 - For code readability, we'll label and refer to each of our directionals using a human readable 
	   enum
	

	Flow: 

	1) Declare variables
	   - Set certain ones to NULL appropriately

	2) Get words from user
	   - While ensuring they don't give us garbage,
	   - letting them stop by giving a # sign instead,
	   - also letting them input no numbers so we can 
	   - give a unsolvable word search with just random letters
	
	3) Place words on the wordsearch, if any
	   - Randomly try one of the 8 directions for each word. If the direction we
	   - chose randomly has bad random coordinates (as in they overlap with another word),
	   - randomly try again. I have it set up so the directions we randomly choose won't hit borders
	
	4) Sort the words list so we can display them in alphabetical order.
	
	5) List the words in alphabetical order


*/

// Path to the file we'll output to
#define FILE_PATH "output.txt"

// Get our input/output libraries
#include <stdio.h>

// Used for certain string functions
#include <string.h>

// So we can use true/false instead of 1/0
#include <stdbool.h>

// We need malloc
#include <stdlib.h>

// For seeding the random number generator
#include <time.h>

// Store directional here....
enum {TOP, DOWN, LEFT, RIGHT, TOP_LEFT, TOP_RIGHT, DOWN_LEFT, DOWN_RIGHT} direction;

// Make a random number inclusively between min and max. This is used for the random directional,
// random row number, and random column number.
int generateRandomNumber(int min, int max);

// Get our maximum of 16 words from the user...
void getWords(char **words, int *numWords, char *currentWord);

// Alphabetically sort the words so we can list them later
void sortWords(char **words, int numWords, char *currentWord);

// Place the words on the board, randomly of course...
void placeWords(char **words, int numWords, char(* board)[25]);

// Fill in remaining blanks with random letters....
void fillInBlanks(char(* board)[25]);

// Free the ram our words multidimensional array used
void freeWordRam(char **words);

// Start us off
int main () {

	// Periodically used for counting and stuff
	int i, j;

	// Our board
	char board[70][25];

	// Initialize it with each character being a NULL byte, so we know that they're blank so we can
	// fill them in with random crap later..
	for (i = 0; i < 70; ++i) 
		for (j = 0; j < 25; ++j)
			board[i][j] = '\0';

	// Store our 16 words. Each element in this list is a 
	// pointer to a character array, which is what strings are. 
	// Set them all to NULL originally
	char *words[16] = {NULL};

	// Store the number of words we actually have here
	int numWords;

	// Store pointer to current word here. Initializing it as NULL so the compiler doesn't give a warning
	// for passing an unitialized variable to a function
	char *currentWord = NULL;

	// Get our words. Pass the word list, the number of words by reference so we 
	// can edit it, and the currentWord pointer which we'll use as a temporary placeholder
	getWords(words, &numWords, currentWord);

	// Place our words we got above in the wordsearch. Pass the word list, the number of words,
	// the current word placeholder, and the wordsearch
	placeWords(words, numWords, board);

	// Fill in remaining blanks with a random letter
	fillInBlanks(board);

	// Time to start outputting stuff. Attempt opening the file to save them as. I'll just recreate it each time
	FILE *file = fopen(FILE_PATH, "w");

	// Did that not work for whatever reason?
	if (file == NULL)
		printf("I couldn't open your file to write a copy of the wordsearch to, sorry.\n");
	
	// Kind of a cool header type thing
	printf("\n\n%40s\n", "Word Search!");

	// File, too
	if (file != NULL)
		fprintf(file, "\n\n%40s\n", "Word Search!");

	// Show the wordsearch! Each line:
	for (j = 0; j < 25; ++j) {
		
		// Each character in that row
		for (i = 0; i < 70; ++i)  {

			// This character
			printf("%c", board[i][j]);

			// To the file too, if it is up
			if (file != NULL)
				fprintf(file, "%c", board[i][j]);
		}

		// Put a newline at the end of the line, so it's a box
		printf("\n");

		// To the file too, if it isn't broken
		if (file != NULL)
			fprintf(file, "\n");
	}

	// Sort them for listing easily, utilizing our currentWord char pointer yet again,
	// except this time as a tmp buffer. For this, we're keeping things simple and using a 
	// bubblesort algorithm. (wiki that)
	// Pass the word list, number of words, and current word placeholder since we'll need it
	sortWords(words, numWords, currentWord);

	// No words entered? meh..
	if (numWords == 0) {
		printf("\nYou didn't give me any words to use, so I gave you infinitely random junk\n");

		// Tell the file as well
		if (file != NULL)
			fprintf(file, "\nYou didn't give me any words to use, so I gave you infinitely random junk\n");
	}
	
	// Otherwise show them, nicely
	else {

		// Say so!
		printf("\n\nWords used(%d):\n", numWords);

		// To the file too, if we can
		if (file != NULL)
			fprintf(file, "\n\nWords used(%d):\n", numWords);

		// List them in two columns, now that they're sorted
		for (i = 0; i < numWords; ++i) {

			// Don't list NULL words, duh
			if (words[i] == NULL)
				continue;

			// Write out this line, with the second column if we have another word for it
			printf("%10s\t%10s\n", words[i], i < numWords && words[i+1] != NULL ? words[i + 1] : "");

			// Send this column to the file if we have it
			if (file != NULL)
				fprintf(file, "%10s\t%10s\n", words[i], i < numWords && words[i+1] != NULL ? words[i + 1] : "");

			// If we had a word for the next column, increment it again
			if (i < numWords && words[i+1] != NULL)
				++i;
		}
	}

	// Won't need the file again. Close it if we were able to open it
	if (file != NULL)
		fclose(file);

	// Free the ram for each
	freeWordRam(words);

	// Wait here
	system("pause");

	return 0;
}

void getWords(char **words, int *numWords, char *currentWord) {

	// Ask until we definitely have 16. 
	for (*numWords = 0; *numWords < 16; ) {
		// Ask for it...
		printf("Enter word number %d, or # to end: ", *numWords + 1);

		// Allocate ram for this round
		currentWord = (char*)malloc(sizeof(char)*11);

		// Did that not work?
		if (currentWord == NULL) {
			printf("Couldn't allocate ram for word. Sorry. Giving you random characters instead.\n");
			return;
		}
		
		// Get their response
		scanf("%10s", currentWord);

		// We're not adding more words by choice, as in they only typed a #? :(
		if (currentWord[0] == '#' && strlen(currentWord) == 1) {

			// Say so
			printf("Okay, not asking for more words. Word count is %d\n", *numWords);

			// Don't leak ram; free that
			free(currentWord);

			// Don't leave dead pointers not labeled as dead...
			currentWord = NULL;

			// End loop here
			break;
		}

		// They didn't give us a word at most 10 chars
		if (strlen(currentWord) == 0 || strlen(currentWord) > 10) {

			// Say so
			printf("That wasn't correct. If you want to, say #. Asking again..\n");

			// Kill ram for that word since we manually did it
			free(currentWord);

			// So we won't try and free() it later
			currentWord = NULL;

			// Ask again
			continue;
		} 

		// Okay, at this point they gave us a valid word. This code won't hit if they 
		// break; or continue; above

		// Move pointer from currentWord to our entry for the word array for this word
		words[*numWords] = currentWord;

		// We're worthy of increasing the number of words now
		++*numWords;
	}
}

// Sort words
void sortWords(char **words, int numWords, char *currentWord) {

	// If we have no words, and will just be outputting random letters, end here now
	if (numWords == 0)
		return;

	// So we know when to stop sorting
	bool sortingDone;

	// Iterator used to go through the word list, over and over again
	int i;

	// Go until we didn't need to fix something, which means it's sorted
	for (sortingDone = false; !sortingDone; ) {

		// Start off thinking we're sortingDone
		sortingDone = true;

		// GO through each word
		for (i = 0; i < numWords; ++i) {
			
			// At this point I only care about the first letter of each word...
			
			// If this word isn't the last word in the list and the one
			// right before it is bigger, flip them
			if (
				i != 0 &&	// Can't look for one before if we're the first	
				words[i] != NULL && // Make sure this isn't a dead word anyway
				words[i-1] != NULL && // Make sure next one isn't a dead word
				words[i][0] < words[i-1][0]) // Actually do letter comparison here...
			{
				
				// Set the tmp word....
				currentWord = words[i];

				// Set current value to the next one, since it's higher
				words[i] = words[i-1];

				// Set next value to current value since it's lower
				words[i-1] = currentWord;

				// No, we weren't done. Make sure we go around at least once more..
				sortingDone = false;
			}
		}
	}
}

// Place words randomly on the wordsearch
void placeWords(char **words, int numWords, char(* board)[25]) {

	// Used to interating and setting tmp stuff and so on
	int 
		i, // Usually row number incrementer
		j, // Usually column number incrementer
		w, // Current word
		p, // Position in current word
		length, // Length of current word
		randR, // Randomly generated row number
		randC; // Randomly generated column number
	
	// When to know to stop trying to find a spot for the the current word
	bool decided;

	// Go through each of the words
	for (w = 0; w < numWords; ++w) {
		
		// This word should never be nonexistant, because numWords should stop right before the 
		// empty words occur. However, try to be protected against the unexpected if something goes 
		// terribly wrong...
		if (words[w] == NULL)
			continue;

		// Localiwe this since we'll use it more than once
		length = strlen(words[w]);

		// Try and try until we have a free parking space for this piece
		for (decided = false; !decided; ) {

			// If we couldn't find a space, this will be set to false and the loop will
			// run again for this word
			decided = true;

			// Which direction? Grab a key from that enum starting with the first and last
			// of the 8 directions, so it's random
			switch (generateRandomNumber(TOP, DOWN_RIGHT)) { 

				// From bottom going up
				case TOP: 

					// ranges for going up from down
					randR = generateRandomNumber(length, 24);
					randC = generateRandomNumber(0, 69);

					// check and see this path works
					for (i = randR, p = length - 1; i > length; --i, --p) {

						// if we run across a nonblank character position that isn't
						// the same letter we won't work
						if (board[randC][i] != '\0' && board[randC][i] != words[w][p]) {
							// Label this as a failure
							decided = false;

							// Duck out now
							break;
						}
					}

					// We didn't break, so fill this word in its slot using above path
					if (decided) 
						for (i = randR, p = 0; p < length ; --i, ++p)
							board[randC][i] = words[w][p];
				break;

				// From top going down
				case DOWN: 
					// Get numbers hopefully in range for DOWN! (correct)
					randR = generateRandomNumber(0, 24 - length);
					randC = generateRandomNumber(0, 69);
							
					// This row..
					for (i = randR, p = 0; p < length; ++i, ++p) {

						// Stop and say this was a failure if the current character is not a blank or is
						// part of another word that isn't this letter, by chance
						if (board[randC][i] != '\0' && board[randC][i]
							!= words[w][p]) {
							decided = false;
							break;
						}
					}


					// If above never turned decided false, this is good
					if (decided)  
						for (i = randR, p = 0; p < length; ++i)
							board[randC][i] = words[w][p++];
				break;

				// From right going left
				case LEFT: 
					randR = generateRandomNumber(0, 24);
					randC = generateRandomNumber(length, 69);

					for (i = randC, p = 0; i < 70 && p < length; ++i, ++p) {
						if (board[i][randR] != '\0' && board[i][randR] !=
							words[w][p]) {
							decided = false;
							break;
						}
					}

					if (decided) 
						for(i = randC, p = length - 1; p > -1; i++) 
							board[i][randR] = words[w][p--];
				break;

				// From left going right
				case RIGHT: 
					randR = generateRandomNumber(0, 24);
					randC = generateRandomNumber(0, 69 - length);

					for (i = randC, p = 0; i < 70 && p < length; ++i, ++p) {
						if (board[i][randR] != '\0' && board[i][randR] !=
							words[w][p]) {
							decided = false;
							break;
						}
					}

					if (decided) 
						for(i = randC, p = 0; p < length; ++i, ++p)
							board[i][randR] = words[w][p];
				break;

				// Going diagonally top to left
				case TOP_LEFT: 
					randR = generateRandomNumber(length, 24);
					randC = generateRandomNumber(length, 69);
					for (
						i = randR, j = randC, p = 0;
						i > -1 && j > -1 && p < length;
						--i, --j, ++p)
					{
						if (board[j][i] != '\0' && board[i][j] != words[w][p]) {
							decided = false;
							break;
						}
					}
					if (decided) 
						for (i = randR, j = randC, p = 0; p < length; --i, --j, ++p) 
							board[j][i] = words[w][p];
				break;

				// Going diagonally top to right
				case TOP_RIGHT:
					randR = generateRandomNumber(length, 24);
					randC = generateRandomNumber(0, 69 - length);
					for (
						i = randR, j = randC, p = 0;
						i > -1 && j < 70 && p < length;
						--i, ++j, ++p)
					{
						if (board[j][i] != '\0' && board[i][j] != words[w][p]) {
							decided = false;
							break;
						}
					}
					if (decided) 
						for (i = randR, j = randC, p = 0; p < length; --i, ++j, ++p) 
							board[j][i] = words[w][p];
				break;

				// Going diagonally down to left
				case DOWN_LEFT: 
					randC = generateRandomNumber(length, 69);
					randR = generateRandomNumber(0, 24 - length);
					for (
						i = randR, j = randC, p = 0;
						i < 25 && j > -1 && p < length;
						++i, --j, ++p)
					{
						if (board[j][i] != '\0' && board[i][j] != words[w][p]) {
							decided = false;
							break;
						}
					}
					if (decided) 
						for(i = randR, j = randC, p = 0; p < length; ++i, --j, ++p) 
							board[j][i] = words[w][p];
				break;

				// Going diagonally down to right
				case DOWN_RIGHT: 
					randR = generateRandomNumber(0, 24 - length);
					randC = generateRandomNumber(0, 69 - length);
					for (
						i = randR, j = randC, p = 0;
						i < 25 && j < 70 && p < length;
						++i, ++j, ++p)
					{
						if (board[j][i] != '\0' && board[i][j] != words[w][p]) {
							decided = false;
							break;
						}
					}
					if (decided) 
						for(i = randR, j = randC, p = 0; p < length; ++i, ++j, ++p) 
							board[j][i] = words[w][p];
				break;
			}
		}
	}
}

// Fill blank spots with random junk
void fillInBlanks(char(* board)[25]) {

	// Variables we'll use to go through the multidimensional array
	int i, j;

	// Every column
	for (i = 0; i < 70; ++i) 
		
		// Every row
		for (j = 0; j < 25; ++j)
			
			// Is this particular spot a null character? Make it something else instead...
			if (board[i][j] == '\0')

				// This makes this spot a genuinely random letter
				//board[i][j] = (char)generateRandomNumber(97, 122); 
				
				// However for testing purposes we'll just use a heiphen so we can ensure we wroute our
				// stuff correctly
				board[i][j] = '-'; 
}

// Since we manually allocated ram with malloc(), we need to free() them too to avoid memory leaks...
void freeWordRam(char **words) {

	// We use this to go through the list
	int i;

	// Go through it
	for (i = 0; i < 16; ++i) {

		// Skip nonexistant or already freed words
		if (words[i] == NULL) 
			continue;

		// Free it
		free(words[i]);

		// It's good practice to set dead pointers to NULL, even if 
		// you won't necessarily use them again
		words[i] = NULL;
	}
}

// Give me a random number between min and max (inclusive)
int generateRandomNumber(int min, int max) {

	// Call it with the seed value incremented each time
	static int counter = 0;

	// First time we call it, counter will be set to time(NULL) which is the seconds since
	// Jan 1, 1970. For each subsequent time, it will be one number higher, so we get a really random
	// value
	srand(counter == 0 ? (counter = (unsigned) time(NULL)) : ++counter);
	
	// Give me a random number, according to my passed 
	// specifications.
	return min + rand() % (max - min + 1);
}