// main.cpp in WordSearch
// by DK, JP, CZ, and EM
// 1-Nov-00

// This code was developed in class, and is not fully completed
// (eg, it lacks sufficient comments, among other things).
// It has no warranty of any kind, of course.
// Use at your own risk.

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <io.h>

////////////////////////////////////////////////////////////////////
//------------------------Globals, Constants, and Other Neat Things
////////////////////////////////////////////////////////////////////

const char* INPUT_FILENAME = "c:\\words.txt";
const char* OUTPUT_FILENAME = "c:\\wordsearch.txt";

const int MAX_ITERATIONS = 100;

const int MAX_STRINGS = 1000;
const int MAX_STRING_LENGTH = 30;

const int MAX_ROWS = 100;
const int MAX_COLS = 100;

const int DIRS = 8;

int g_rows;
int g_cols;

char g_strings[MAX_STRINGS][MAX_STRING_LENGTH];
int g_stringCount;

char g_board[MAX_ROWS][MAX_COLS];

////////////////////////////////////////////////////////////////////
//------------------------Begin Random Code-----------------------//
////////////////////////////////////////////////////////////////////

// returns a random between 0 and 1
double random1()
{
        static bool seeded = false;
        if (seeded == false)
        {
                srand(time(NULL)); // seed the random # generator
                seeded = true;
        }
        return double(rand()) / RAND_MAX;
}

double random(double lo, double hi)
{
        if (hi < lo)
        {
                double temp = hi;
                hi = lo;
                lo = temp;
        }
        double range = hi - lo;
        return lo + range * random1();
}

int random(int lo, int hi)
{
        int result;
        do
        {
                result = int(random(double(lo),double(hi+1)));
        }
        while (result == (hi+1));
        return result;
}


////////////////////////////////////////////////////////////////////
//------------------------Begin Fairly UnRandom Code--------------//
////////////////////////////////////////////////////////////////////

// @TODO:  This is debug code, it will go away when we write our file stuff
const int TEMP_SIZE = 6;
char* g_strings_temp[TEMP_SIZE] = 
{"Four","Score","And","Seven","Years","Ago"};

void loadStrings()
{
        g_stringCount = 0;
        FILE *fp;

        fp = fopen(INPUT_FILENAME,"r");
        if (fp == NULL)
        {
                cout << "Could not open file '" << INPUT_FILENAME << "'.  Sorry." << endl;
				cout << "Hit 'Enter' to exit." << endl;
                getchar();
                exit(1);
        }

        while (!feof(fp))
        {
                int i = 0;
                char c;
				// eat whitespace
				while (c=getc(fp),((c == '\n') || (c == '\t') || (c == ' ')))
					; // do nothing
				// now put back the non-space
				if (feof(fp))
					break;
				ungetc(c,fp);

				// now get the word
                while (c=getc(fp),((c != '\n') && (c != ' ') && (c != EOF)))
                        g_strings[g_stringCount][i++] = toupper(c);
                // add null terminator
                g_strings[g_stringCount][i] = NULL;
                ++g_stringCount;
        }
}

void fillBoard()
{
        // fill empty spaces on board with random characters
        int row, col, count = 0;
        for (row=0; row<g_rows; row++)
        for (col=0; col<g_cols; col++)
                if (g_board[row][col] == NULL)
                {
                        ++count;
                        g_board[row][col] = 'A' + random(0,25);
                        // g_board[row][col] = '.';
                }
		cout << "Extra " << count << " spaces filled with random characters" << endl;
}

void printBoard()
{
        int row,col;
		FILE *fp;
		fp = fopen(OUTPUT_FILENAME,"w");
        if (fp == NULL)
        {
                cout << "Could not open file '" << OUTPUT_FILENAME << "'.  Sorry." << endl;
				cout << "Hit 'Enter' to exit." << endl;
                getchar();
                exit(1);
        }

		cout << "The following word search was generated by software developed in the" << endl
			 << "Introduction to Computer Science class at Sewickley Academy." << endl
			 << "For more information, see:  http://www.sewickley.org/"
			 << endl << endl;

		fprintf(fp,"The following word search was generated by software developed in the\n");
		fprintf(fp,"Introduction to Computer Science class at Sewickley Academy.\n");
		fprintf(fp,"For more information, see: http://www.sewickley.org/\n\n");

        // cout << endl << "Here is the " << g_rows << " x "
        //          << g_cols << " board:" << endl;
        for (row=0;row<g_rows;row++)
        {
                for (col=0;col<g_cols;col++)
				{
                        cout << g_board[row][col] << " ";
						fprintf(fp,"%c ",g_board[row][col]);
				}
				fprintf(fp,"\n");
                cout << endl;
        }

		// now print strings in puzzle
		fprintf(fp,"\nWords:\n");
		// 1. find longest string length
		int longest = 0, i;
		for (i=0;i<g_stringCount;i++)
		{
			int len = strlen(g_strings[i]);
			if (len > longest)
				longest = len;
		}
		int perLine = 80 / (longest + 5);
		for (i=0;i<g_stringCount;i++)
		{
			if (i % perLine == 0)
				fprintf(fp,"\n");
			fprintf(fp,"%s",g_strings[i]);
			for (int j=strlen(g_strings[i]);j<longest+5;j++)
				fprintf(fp," ");
		}
		fprintf(fp,"\n");

		fclose(fp);
		cout << endl << "This puzzle is also in file '"
			 << OUTPUT_FILENAME << "'" << endl;
}

void printStrings()
{
        cout << "Here are the " << g_stringCount << " words:" << endl;
        int i;
        for (i=0; i<g_stringCount;i++)
                cout << "   '" << g_strings[i] << "'" << endl;
}

// This returns the number of chars used when placing the string,
// and -1 if it is not at all placeable here.
int placeString(char* string, int row, int col, int dir, bool reallyPlace)
{
        int numChars = 0;
        unsigned int i;
        int rowSign, colSign;
        int thisDir = 0;

        // 1. set rowSign,colSign to (1,1), (1,0), (1,-1), etc,
        //    based on value of dir
        for (rowSign=-1;rowSign<=1;rowSign++)
        for (colSign=-1;colSign<=1;colSign++)
                if ((rowSign || colSign) && (thisDir++ == dir))
                        goto foundRowCol;

foundRowCol:
        // 2. Place string along this vector from row,col
        for (i=0;i<strlen(string);i++)
        {
                int row2 = row + i * rowSign;
                int col2 = col + i * colSign;
                // verify we're on the board
                if ((row2 < 0) || (row2 >= g_rows) ||
                        (col2 < 0) || (col2 >= g_cols))
                        // we ran off the board, so fail by returning -1
                        return -1;
                // verify target board position is either
                // empty or matches this character in the string
                bool positionEmpty = (g_board[row2][col2] == NULL);
                bool positionMatches = (g_board[row2][col2] == string[i]);

                if ((positionEmpty == false) && (positionMatches == false))
                        // position is occupied and it doesn't match,
                        // so we must fail and go home.
                        return -1;

                // Increment the number of characters if we do not
                // have a match
                if (positionMatches == false)
                        numChars++;

                // Place the character
                if (reallyPlace)
                        g_board[row2][col2] = string[i];
        }
        return numChars;
}

bool loadString(int i)
{
        char* string = g_strings[i];

        int col1 = random(0,g_cols-1);
        int row1 = random(0,g_rows-1);
        int dir1 = random(0,DIRS-1);

        bool foundOne = false;
        int bestCol, bestRow, bestDir, bestNumChars;

        int row, col, dir, rowDelta, colDelta, dirDelta;

        // Iterate over every row,col,dir to find best choice
        for (rowDelta=0; rowDelta<g_rows; rowDelta++)
        for (colDelta=0; colDelta<g_cols; colDelta++)
        for (dirDelta=0; dirDelta<DIRS;   dirDelta++)
        {
                row = (row1 + rowDelta) % g_rows;
                col = (col1 + colDelta) % g_cols;
                dir = (dir1 + dirDelta) % DIRS;

                int numChars = placeString(string,row,col,dir,false);
                if ((numChars >= 0) &&
                        ((foundOne == false) ||
                         (bestNumChars > numChars)))
                {
                        // We just found a better one than the one
                        // we have so far, if any
                        bestRow = row;
                        bestCol = col;
                        bestDir = dir;
                        bestNumChars = numChars;
                        foundOne = true;
                }
        }

        // Place it in the best location, if any
        if (foundOne)
        {
                placeString(string,bestRow,bestCol,bestDir,true);
                return true;
        }
        else
                return false;
}

bool loadBoard()
{
        // Repeatedly try to loadBoard until maxIterations
        int iteration;
        for (iteration=0; iteration<MAX_ITERATIONS; iteration++)
        {
                bool loadStringFailed = false;

                // first, load board with NULL character
                int row, col;
                for (row=0; row<g_rows; row++)
                for (col=0; col<g_cols; col++)
                        g_board[row][col] = (char) NULL;

                // load the board with the strings in g_strings[];
                int i = random(0,g_stringCount-1);
                int iDelta;
                for (iDelta=0; iDelta<g_stringCount; iDelta++)
                {
                        if (loadString((i + iDelta) % g_stringCount) == false)
                        {
                                loadStringFailed = true;
                                break;
                        }
                }

                // Woohoo!  We've done it!
                if (loadStringFailed == false)
                        return true;
        }
        // Urk.  No such luck over MAX_ITERATIONS attempts
        return false;
}


////////////////////////////////////////////////////////////////////
//------------------------Main()
////////////////////////////////////////////////////////////////////

void mainWordSearch()
{
        loadStrings();
        printStrings();
        g_rows = g_cols = 4;
        while (!loadBoard())
        {
                g_rows++;
                g_cols++;
        }
        fillBoard();
        printBoard();
		cout << "Hit 'Enter' to exit." << endl;
        getchar();
}