// puzzles.nigelcoldwell.co.uk/fourteen.htm

#include <iostream>
#include <string>
#include <time.h>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main ()
{


  short int q=0; // quit value
  bool deck[54]; // deck array
  short int a=0; // ath card in the deck or run 
  short int b=0; // bth card for randomizer
  short int c=0; // cth card for randomizer
  short int w=0; // win in a specific game
  long int totalwin=0; //win over all games
  float iter=0; //iterations total
  //long int totaliter=1000000; //total iterations set here
const long int totalit=1000000;
int tim=time(NULL); // part of the random number seed

  string outpt;
string mystr;
string outline;

cout << "v2.008\n";
/*
2.008 improved randomize
2.007 changed total iterations to constant
2.006 if q==0 return 0
2.005 randomize deck using while
2.001 change screen out put to 10,000th line
2.000 rewite from qbasic to C++
*/
cout << "This program is designed to help in the solving of riddle number 14 from\n";
cout << "my website http://puzzles.nigelcoldwell.co.uk\n";
cout << " \n";
cout << "#14:\n";
cout << "You have 52 playing cards (26 red, 26 black). You draw cards one by one.\n";
cout << "A red card pays you a dollar. A black one fines you a dollar. You can\n";
cout << "stop any time you want. Cards are not returned to the deck after being\n";
cout << "drawn. What is the optimal stopping rule in terms of maximizing expected\n";
cout << "payoff? Also, what is the expected payoff following this optimal rule?\n";
cout << " \n";
cout << "This program runs the simulation 'I will quit if i get x amount of Dollars\n";
cout << "ahead' " << totalit << " times.\n";
while (1) //loop for program
{

cout << "Enter quit level, eg. 1, 2, 3 Dollars etc. (0 to quit)"; 

  getline (cin,mystr);
  stringstream(mystr) >> q;
  	  /* initialize random seed: */
  srand ( time(NULL) + tim );
  
if (q==0)
  {
	  return 0;
  } 

totalwin=0;
for (iter=1;iter<=totalit;iter++) //main loop for iterations
{
//set deck to zero
for (a=1; a<=52; a++)
{
	deck[a] = false;
}

//randomize deck
a = 0;
while (a < 26) {
    b = rand() % 52 + 1;
    if (!deck[b]) {
        deck[b] = true;
        a++;
    }
}  

//rundeck and test
w=0;
outpt="";
for (a=1; a<=52; a++){
	if (deck[a]==false) {
		
		outpt.append("W");
		w++;
	}
	else{

	outpt.append("L");
	w--;
	}

	if (w==q) break;
}
if (a==53) a=52;
outpt.append((55-a),' ');
totalwin=totalwin+w;

if (int(iter) % 10000 == 0) // output every 10,000th line to screen, for speed
{
	cout << "After " << iter << " itterations...\n";
	cout << outpt << w << " average " << (totalwin/iter) << "\n";
}

}
cout << "With " << (iter-1) << " iterations completed expected return is " << (totalwin/(iter-1)) << " using a \nquit value of " << q << "\n";
}
    return 0;
}