// trolls.c - multifunction programm for support of problem C in IPSC 2000
//

/////////////////////////////////////////////////////////////////////////////
// Trolls
//
// This programm has 3 defferent functions:
//    Generating imputs for the problem    (run: trolls.exe g1000 file.txt)
//    Analyzing given problem to help solve it (run: trolls.exe r file.txt)
//    The automatic judge                      (run: trolls.exe j file.txt)
//
// The main procedure only tests which parameter has been used and runs
// separate procedures for each of this functions:
//    GenerateImput, GenerateReport, Judge
// See this functions for further documentation.
//

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

#define sCODE	30050			// maximal size of the forest
#define nCHARS  10				// number of generated letters

#define sLINE	76				// split output into lines of this length
#define sTROLL 100				// maximum size of a troll
								// (in judge process -not in analyze process)

char strWord[sCODE];			// analyzed troll
int cTab[sCODE];				// count-of-words table
int cBeg[sCODE];				// "
int cEnd[sCODE];				// "
char strTroll[sTROLL];			// judged troll

char strInfile[100];			// input file name

char strCode[sCODE];			// THE FOREST
int CodeLength;					// actual length of the forest

// Propability table for generating the forest: propability of the next
// letter is dependend from the last letter
int prop[][10] = {
					{  3, 14,  1,  1,  1,  0,  1,  0,  2,  0 },
					{ 13,  2,  1,  1,  1,  0,  0,  0,  0,  0 },
					{  1,  1,  3, 13,  3,  0,  0,  2,  1,  0 },
					{  1,  1,  1,  2, 13,  0,  0,  1,  0,  1 },
					{  1,  1, 14,  2,  3,  1,  0,  0,  0,  0 },
					{  1,  1,  0,  1,  0,  0, 13,  0,  1,  0 },
					{  2,  0,  1,  0,  0, 14,  0,  0,  0,  0 },
					{  1,  0,  0,  2,  0,  0,  0,  0, 13,  0 },
					{  0,  1,  0,  0,  0,  0,  0,  0,  0, 13 },
					{  0,  0,  1,  1,  1,  0,  1, 14,  0,  0 },
					};

// Forwards
void Judge( char *strFilename );
void GenerateInput( int szGenerate, char *strFilename );
void GenerateReport( char *strFilename );
int LoadFromFile( char *strFilename );
int OutputToFile( char *strFilename);
void ChangeExtension( char *strFilename, char *strExt );
void PrintHelp( void );

/////////////////////////////////////////////////////////////////////////////
// main

int main(int argc, char* argv[])
{
	int szGenerate = -1;

	// What function do we want from this program
	//   
	//  - generate imput			g,c
	//  - write report from imput	r
	//  - ipsc automatic judge		j

	srand((unsigned)time( NULL ));

	if (argc <= 2)
	{
		printf("Error: To few arguments.\n\n");
		PrintHelp();
		return 0;
	}

	// store the input file name
	strcpy(strInfile,argv[2]);

	// switch deciding upon the first parameter
	switch(argv[1][0])
	{
	case 'g':
	case 'c':
		// g - generate
		// c - generate, report

		// Get size of generated imput
		if (1 != sscanf(&argv[1][1],"%d",&szGenerate))
		{
			printf("Error: Invalid argument format.\n\n");
			PrintHelp();
			return 0;
		}
		if (szGenerate < 0)
		{
			printf("Error: Invalid argument format (should generate file of length: %d.\n\n",szGenerate);
			PrintHelp();
			return 0;
		}
		if (szGenerate >= sCODE - 1)
		{
			printf("Error: File to generate too long: %d.\n\n",szGenerate);
			PrintHelp();
			return 0;
		}

		// Generate imput - FUNCTION CALL
		GenerateInput(szGenerate,strInfile);

		// Stop if 'g' continue if 'c'
		if (argv[1][0] == 'g')
			break;
	case 'r':
		// Generate report - FUNCTION CALL
		GenerateReport(strInfile);
		break;
	case 'j':
		// Automatic judge - FUNCTION CALL
		Judge(strInfile);
		break;
	default:
		// bla, bla ... we did not understood
		printf("Error: Invalid argument '%c'.\n\n",argv[1][0]);
		PrintHelp();
		return 0;
	}

	return 0;
}

/////////////////////////////////////////////////////////////////////////////
// Judge procedure

// Counts the number of appereances of word strWord in global strCode
int CountWord( char *strWord )
{
	int count;
	char *pAct = strCode;

	// if counting a blank word - return some enormous number
	if (strWord[0] == '\0')
		return(123000000);

	for(count=0;pAct = strstr(pAct,strWord);count++,pAct++);

	return(count);
}

// Judges the answer at stdin, strFilename is the forest definition
// filename.ans is the Troll specification
void Judge( char *strFilename )
{
	FILE *fin;
	int TrollCount,GuessCount,TrollCount2;

	// loads forest in global strCode
	if (!LoadFromFile(strFilename))
		return;

	// reads the quessed word from stdin
	if (NULL == fgets(strWord,sCODE,stdin))
	{
		printf("ERROR: Error reading from stdin.\n\n");
		return;
	}

	// deletes '\n' character from the end (if appended)
	if (strWord[strlen(strWord)-1] == '\n')
		strWord[strlen(strWord)-1] = '\0';

	// opens .ans file
	ChangeExtension(strFilename,".ans");
	fin = fopen(strFilename,"rt");

	if (fin == NULL)
	{
		printf("ERROR: Could not open answer file '%s'\n\n",strFilename);
		return;
	}

	// reads the Troll and ist count
	TrollCount = -1;
	if (2 != fscanf(fin,"%[^ ] %d",strTroll,&TrollCount))
	{
		printf("ERROR: Error reading from answer file '%s'\n\n",strFilename);
		fclose(fin);
		return;
	}

	fclose(fin);

	if (!strcmp(strTroll,strWord))
	{
		// guess correct
		printf("OK");
		return;
	}

	// Counts Trolls and guessed words
	GuessCount = CountWord(strWord);
	TrollCount2 = CountWord(strTroll);

	// Error .ans file and counted count mismatch
	if (TrollCount != TrollCount2)
	{
		printf("WARNING: How much Trolls?\n\n");
	}

	if (TrollCount > GuessCount)
	{
		printf("There are more Trolls than '%s's in my forest.",strWord);
		return;
	}

	if (TrollCount < GuessCount)
	{
		printf("There are less Trolls than '%s's in my forest.",strWord);
		return;
	}

	// TrollCount == GuesCount - invalid problem
	printf("ERROR: '%s' is in input the same times as Trolls\n\n");
}

/////////////////////////////////////////////////////////////////////////////
// Input generation procedure

void GenerateInput( int szGenerate, char *strFilename )
{
	int i,j,rnd;
	char ch;
	int LineSum;
	int iLine;

	CodeLength = szGenerate;

	//DEPENDED DISTRIBUTION

	// Generate first character - uniform distribution, 
	//    no static propabilities computed ;-)
	ch = rand() % nCHARS;
	ch += 'a';

	strCode[0] = ch;

	// Generete the rest of the forest
	for(i=1;i<CodeLength;i++)
	{
		iLine = strCode[i-1]-'a';

		// Compute the sum of numbers in line iLine of the prop. matrix
		LineSum = 0;

		for(j=0;j<nCHARS;j++)
			LineSum += prop[iLine][j];

		// random
		rnd = rand() % LineSum;

		rnd -= prop[iLine][0];

		// find the interval of this random value
		for(j=0;rnd >= 0;j++,rnd-=prop[iLine][j]);

		strCode[i] = j + 'a';
	}
	
	/*
	UNIFORM DISTRIBUTION STRING GENERATION
	for(i=0;i<CodeLength;i++)
	{
		char ch = rand() % nCHARS;
		ch += 'a';

		strCode[i] = ch;
	}*/

	strCode[CodeLength] = '\0';

	// Write the output file
	OutputToFile(strFilename);
}

/////////////////////////////////////////////////////////////////////////////
// Report generation procedure

void GenerateReport( char *strFilename )
{
	int i;
	FILE *fout;
	int iBeg,iEnd;
	int *IndArray,*IndArray2;
	int sIndArray;
	int count;
	int iAct;
	int *p;
	int UniCount;
	int num;

	// Load the forest into the global strCode
	if (!LoadFromFile(strFilename))
		return;

	// Change extension of file to .rep
	ChangeExtension(strFilename,".rep");

	fout = fopen(strFilename,"wt");

	if (fout == NULL)
	{
		printf("ERROR: Failed to open output file '%s'.\n\n",strFilename);
		return;
	}

	// REPORT: the size of the forest
	fprintf(fout,"Size of the forest: %i\n\n",CodeLength);

	// Create cTab[i]: how much words rapeat i times (muliplied by i)
	// EFFECTIVE ALGORITHM

	// Clear the cTab
	for(i=0;i<sCODE;i++)
		cTab[i] = 0;

	IndArray = (int *)malloc(sizeof(int)*sCODE);
	IndArray2 = (int *)malloc(sizeof(int)*sCODE);

	// For all letters in the forest - iBeg is the begining of the analyzed
	// word
	for(iBeg=0;iBeg<CodeLength;iBeg++)
	{
		printf("Progress: %i%%        \r",iBeg*100/CodeLength);

		// Now the analyzed word has zero length
		strWord[0] = '\0';

		// Initialize the array of valid indices - this array points to all
		// indices where the word strWord can be found (it ends there)
		for(i=0;i<CodeLength;i++)
			IndArray[i] = i;
		sIndArray = CodeLength;

		// Add letters to the analyzed word - one by one
		// iEnd - index of the end of the analyzed word
		for(iEnd=iBeg;iEnd<CodeLength;iEnd++)
		{
			// Add new letter to strWord
			strWord[iEnd-iBeg] = strCode[iEnd];
			strWord[iEnd-iBeg+1] = '\0';

			// Update the valid indices array (IndArray)

			count = 0;
			for(i=0;i<sIndArray;i++)
			{
				// If the index points to the same letter as strCode[iEnd] it is still
				// a valid index, otherwise it is invalid
				if ((IndArray[i] >= CodeLength) || (strCode[IndArray[i]] != strCode[iEnd]))
					IndArray[i] = -1;		// invalidate index
				else
				{
					count++;				// increase count of valid indices
					IndArray[i]++;			// increase index to the next letter
				}
			}

			// Store analyzed word in the cTab
			cTab[count]++;
			cBeg[count] = iBeg;		// remember also the begining and the end of that
			cEnd[count] = iEnd;		// word so it can be reconstructed

			// Pack the IndArray into the IndArray2 - remove invalid indices
			iAct=0;
			for(i=0;i<sIndArray;i++)
				if (IndArray[i] != -1)
				{
					IndArray2[iAct] = IndArray[i];
					iAct++;
				}

			if (iAct != count)
				printf("Error: internal(1)\n\n");

			// Exchange IndArray and IndArray2 pointers
			p = IndArray;
			IndArray = IndArray2;
			IndArray2 = p;

			sIndArray = count;
		}
	}

	free(IndArray);
	free(IndArray2);

	/*
	CODE WITH NO OPTIMALIZATIONS
	for(iBeg=0;iBeg<CodeLength;iBeg++)
	{

		printf("Progress: %i%%        \r",iBeg*100/CodeLength);

		int bSingle = 0;

		for(iEnd=iBeg;iEnd<CodeLength;iEnd++)
		{
			memcpy(strWord,&strCode[iBeg],(iEnd-iBeg+1)*sizeof(char));
			strWord[iEnd-iBeg+1] = '\0';

			int count;

			if (!bSingle)
			{
				char *pAct = strCode;
				for(count=0;pAct = strstr(pAct,strWord);count++,pAct++);
			}
			else
			{
				count = 1;
			}

			cTab[count]++;
			cBeg[count] = iBeg;
			cEnd[count] = iEnd;

			// HERE OPTIMALIZED - remove this two lines to have realy no
			// optimalizations
			if (count == 1)
				bSingle = 1;

		}
	}
*/	

	// end creating cTab

	// cTab[0] should be 0
	fprintf(fout,"cTab[0]: %i\n",cTab[0]);

	// Count number of words with unique repetitions number
	UniCount = 0;

	for(i=1;i<CodeLength;i++)
	{
		if (cTab[i] == i)
			UniCount++;
	};

	fprintf(fout,"\n%i words have unique repetition number.\n\n",UniCount);

	// REPORT: the table of words with unique repetition number
	fprintf(fout,"Unicate repetitions table: nr : number repetitions (x) 'word'\n\n");
	num = 0;
	for(i=1;i<CodeLength;i++)
	{
		if (cTab[i] != i)
			continue;

		fprintf(fout,"%i : %i (x)",num,i);
		num++;

		if (cTab[i])
		{
			memcpy(strWord,&strCode[cBeg[i]],(cEnd[i]-cBeg[i]+1)*sizeof(char));
			strWord[cEnd[i]-cBeg[i]+1] = '\0';

			fprintf(fout,"  '%s'",strWord);
		}

		fprintf(fout,"\n");
	}

	fprintf(fout,"\n\n");

/*
	// REPORT: table of all repetitions
	fprintf(fout,"All repetitions table: number repetitions : number words (some number) 'word'\n\n");
	for(i=1;i<CodeLength;i++)
	{
		fprintf(fout,"%i : %i (%i)",i,cTab[i]/i,cTab[i]);

		if (cTab[i])
		{
			memcpy(strWord,&strCode[cBeg[i]],(cEnd[i]-cBeg[i]+1)*sizeof(char));
			strWord[cEnd[i]-cBeg[i]+1] = '\0';

			fprintf(fout,"  '%s'",strWord);
		}

		fprintf(fout,"\n");
	}
*/

	fclose(fout);
}

/////////////////////////////////////////////////////////////////////////////
// Input/Output

// Load the forest from file to global strCode
int LoadFromFile( char *strFilename )
{
	FILE *fin;
	int ActPos;
	char strTemp[sLINE+20];
	int TempLength;

	// Open input file
	if (NULL == (fin = fopen(strFilename,"rt")))
	{
		printf("ERROR: Failed to open file as input '%s'\n\n",strFilename);
		return(0);
	}

	ActPos = 0;

	while(1)
	{
		// Read one line
		if (NULL == fgets(strTemp,sLINE+10,fin))
			break;

		// Test the string
		TempLength = strlen(strTemp);

		if (TempLength == 0)
		{
			printf("WARNING: Zero length string should not appear.\n\n");
			break;
		}

		if (strTemp[TempLength-1] == '\n')
		{
			strTemp[TempLength-1] = '\0';
			TempLength--;
		}

		if (TempLength == 0)
		{
			printf("WARNING: String with only a newline character should not appear.\n\n");
			break;
		}

		// Append the string to the code
		if (TempLength+ActPos+1 >= sCODE)
		{
			printf("ERROR: The file does not fit into the defined global array (input truncated).\n\n");
			break;
		}

		strcpy(&strCode[ActPos],strTemp);

		ActPos += TempLength;
	}

	// Now the strCode contains the imput read from input file
	CodeLength = ActPos;

	strCode[CodeLength] = '\0';

	fclose(fin);

	return(1);
}

// Store forest from global strCode to file
int OutputToFile( char *strFilename)
{
	FILE *fout;
	int ActPos = 0;
	int bEnd = 0;
	char TempChar;


	// Open output file
	if (NULL == (fout = fopen(strFilename,"wt")))
	{
		printf("ERROR: Failed to open file as output '%s'\n\n",strFilename);
		return(0);
	}

	while(1)
	{

		if (ActPos + sLINE >= CodeLength)
			bEnd = 1;
		else
		{
			TempChar = strCode[ActPos+sLINE];
			strCode[ActPos+sLINE] = '\0';
		}

		fputs(&strCode[ActPos],fout);

		if (bEnd)
			break;

		fputs("\n",fout);
		strCode[ActPos+sLINE] = TempChar;

		ActPos += sLINE;
	}

	fclose(fout);

	return(1);
}

/////////////////////////////////////////////////////////////////////////////
// Support procedures

// Replace the extenstion of file strFilename with strExt
void ChangeExtension( char *strFilename, char *strExt )
{
	int s,i;

	if (strExt[0] != '.')
		printf("Error: wrong extension\n\n");

	s = strlen(strFilename);

	for(i=s-1;i>=0;i--)
	{
		if (strFilename[i] == '.')
			break;
		if (strFilename[i] == '\\')
		{
			i = s;
			break;
		}
		if (strFilename[i] == '/')
		{
			i = s;
			break;
		}
	}

	if (i == -1)
		i = s;

	strcpy(&strFilename[i],strExt);
}

void PrintHelp( void )
{
	printf("Execute:\n\n");
	printf("trolls g<number> <filename.txt>\n");
	printf("   - generate input of length <number> into <filename.txt>\n");
	printf("\n");
	printf("trolls r <filename.txt>\n");
	printf("   - generates report from file <filename.txt> into file <filename.rep>\n");
	printf("\n");
	printf("trolls j <filename.txt>\n");
	printf("   - judge answer on stdin, the forest definition is in file <filename.txt>\n");
	printf("     the correct answer is stored in <filename.ans> in the format:\n");
	printf("             <troll> <number_of_repetitions>\n");
	printf("     For example the file should contain only one line: wolf 6\n");
	printf("\n");
	printf("trolls c<number> <filename.txt>\n");
	printf("   - like 'trolls g' and 'trolls c' executed consequently\n");

	printf("\n");
}