// calcprob.cpp
// This program models choosing lettered tiles from an urn in 
// order to calculate an empirical probability

#include <iostream>
#include <stdlib.h>	// needed for the rand function
#include <time.h>	// needed to get current time to seed rand function
using namespace std;

long GetRandomNumber(int nMin, int nMax);

int main()
{
	const int nDiscardTilesOnceChosen = 1;
	const int nLetteredTiles = 9;
	const int nTargetTiles = 4;
	const int nMatchesNeededForSuccess = 1;
	const int nTrialsPerIteration = 4;
	const long lIterations = 1000000;

	int nTrial = 0;
	int nMatches = 0;
	int nIndex = 0;
	int nLooper = 0;
	int nFoundOne = 0;
	long lIteration = 0;
	long lSuccessfulIterations = 0;
	char cLetter = ' ';
	char cUrn[nLetteredTiles][3];


	// Before doing anything else, intialize the random number generator
	// using the system clock
	srand((unsigned)time(NULL));

	// Initialize array (fill the urn with lettered tiles)
	// The columns of the multidimensional array breakdown as follows:
	// [1] = LETTER: a unique symbol on a tile that gets placed into the urn.
	// 		 As the program currently stands, this value is not used.
	// [2] = CHOSEN: has this letter/tile already been chosen from the urn?
	//		 If so, it may have been disarded and so not available 
	//		 any more, or it may have been replaced and available to 
	//		 be selected again.  Which occurs for an already selected
	//		 tile depends upon the value of the const variable
	//		 nDiscardTilesOnceChosen.
	// [3] = TARGET: is this letter/tile one of the targets?
	for (nIndex = 0; nIndex < nLetteredTiles; nIndex++)
	{
		cLetter = 64 + nIndex;
		cUrn[nIndex][1] = cLetter;
		cUrn[nIndex][2] = 'F';
		cUrn[nIndex][3] = 'F';
	}
	
	// Choose x number of tiles from the Urn to serve as targets
	for (nLooper = 1; nLooper <= nTargetTiles; nLooper++)
	{
		nFoundOne = 0;
		while (nFoundOne == 0)
		{
			nIndex = (int) GetRandomNumber(0, nLetteredTiles - 1);
			if (cUrn[nIndex][3] == 'F')
			{
				cUrn[nIndex][3] = 'T';
				nFoundOne = 1;	
			}
		}
	}



	// Begin selecting tiles from the Urn.
	for (lIteration = 1; lIteration <= lIterations; lIteration++)
	{
		// New iteration: need to clear all CHOSEN flags
		for (nIndex = 0; nIndex < nLetteredTiles; nIndex++)
		{
			cUrn[nIndex][2] = 'F';	
		}
		nMatches = 0;
		
	
		// Give the user some output throughout the process 
		cout << "Iteration " << lIteration << " of " << lIterations << endl;

		for (nTrial = 1; nTrial <= nTrialsPerIteration; nTrial++)
		{

			// Pull a single tile out of the urn
			nFoundOne = 0;
			while (nFoundOne == 0)
			{
				nIndex = (int) GetRandomNumber(0, nLetteredTiles - 1);
				if (nDiscardTilesOnceChosen == 0)
				{
					// Doesn't matter if the tile has been 
					// chosen previously because selected
					// tiles are placed back into the urn.
					nFoundOne = 1;
				}
				else if (cUrn[nIndex][2] == 'T')
				{
					// This tile has already been chosen and
					// discarded: it can't be selected again.
					nFoundOne = 0;
				}
				else if (cUrn[nIndex][2] == 'F')
				{
					// This tile has not been chosen previously.
					nFoundOne = 1;
				}
			}
			// A tile has been chosen: flag it as such
			cUrn[nIndex][2] = 'T';

			// Does the chosen tile match one of the targets?
			if (cUrn[nIndex][3] == 'T')
			{
				nMatches += 1;
			}

			// No need to continue pulling tiles for this iteration
			// if we've obtained enough matches for success
			if (nMatches >= nMatchesNeededForSuccess)
			{
				nTrial = nTrialsPerIteration + 1;
			}
		}

		// Did we get enough matches for this iteration?
		if (nMatches >= nMatchesNeededForSuccess)
		{
			lSuccessfulIterations += 1;
		}
	}
	

	cout << "Tiles discarded after being chosen? ";
	cout << (nDiscardTilesOnceChosen == 1?"Yes":"No") << endl;
	cout << "Number of lettered tiles in Urn: ";
	cout << nLetteredTiles << endl;
	cout << "Number of target tiles: ";
	cout << nTargetTiles << endl;
	cout << "Number of matches needed: ";
	cout << nMatchesNeededForSuccess << endl;
	cout << "Trials per iteration: ";
	cout << nTrialsPerIteration << endl;
	cout << "Total iterations: ";
	cout << lIterations << endl;
	cout << "Successful iterations: ";
	cout << lSuccessfulIterations << endl;
	cout << "Empirical probability: ";
	cout << ((float)lSuccessfulIterations / lIterations) * 100 << "%" << endl;

	return (0);
}


long GetRandomNumber(int nMin, int nMax)
{
	long lRandomNumber;

	lRandomNumber = rand();
	while (lRandomNumber < nMin || lRandomNumber > nMax)
	{
		lRandomNumber = rand();
	}
	return lRandomNumber;
}