//========================================================================= #define PROGRAMMER "SOLUTIONS, NoFrills" #define PROG_CODE "soln" #define COURSE "ECE-1021" #define YEAR (2003) #define TERM "Fall" #define SECTION (0) #define ASSIGNMENT "HW #3B" #define REVISION (0) #define TITLE "The Monty Hall Problem" #define SUBTITLE "Problem 5.20" #define EMAIL "wbahn@eas.uccs.edu" #define FILENAME "03b0soln.c" //========================================================================= //==================================================================== // PROBLEM: //==================================================================== // // Write a program that simulates the Monty Hall game to answer the // question of the best strategy for playing the game. // //==================================================================== // SOLUTION: //==================================================================== // // The main part is to write a function that plays the game according to // the rules of the the game. So the first step is to clearly detail the // rules of the game. // // The Rules of the Game: // // Step 1: Randomly place a car behind one of three doors. // Step 2: The player picks a door. // Step 3: One of the non-picked, non-winning doors is opened. // Step 4: The player has the choice to switch doors. // Step 5: The player's final selection is revealed. // // Per the statement of the problem, the program is to play the game // according to one of three user-selected strategies. // // Strategy 1: Always stay with the door initially picked. // Strategy 2: Randomly choose whether to stay or switch. // Strategy 3: Always switch to the unpicked, unopened door. // // Our game playing function can take that as an argument and return // a logical value indicating whether the game was won or lost. Also, // per the additional material given in the homework assignment, the // function needs to know the "verbosity level" and print out information // accordingly. // // PSEUDOCODE: (Fleshed out from that contained in 03b0soln.txt) // // REM: After fleshing out the final results output task, tha // following quantities are needed to generate the output. // // TotalGamesPlayed GamesSwitched GamesStayed // TotalGamesWon Switched&Won Stayed&Won // TotalGamesLost Switched&Lost Stayed&Lost // // It would be perfectly acceptable to use nine variables to // track all of this data, but if we know some minimal amount // of it we can compute the rest. // // Looking at the relationships, we see that it is sufficient // to track the following: // // Switched&Won Stayed&Won // Switched&Lost Stayed&Lost // // Since every game played falls into exactly one of the above // categories, we can exploit the nature of arrays and logical // values to track the necessary data using a single statement. // // WillSwitch = 0 if the player stays // = 1 if the player switched // Won = 0 if the player lost // = 1 if the player won // // So the statement data[WillSwitch][Won]++ will update the // correct variable where: // // data[1][1] = Switched&Won data[0][1] = Stayed&Won // data[1][0] = Switched&Lost data[0][0] = Stayed&Lost // //==================================================================== // PSEUDOCODE FOR main() //==================================================================== // // Constants // // STAY (0) logical label plus index to data array // SWITCH (1) logical label plus index to data array // LOST (0) logical label plus index to data array // WON (1) logical label plus index to data array // STRATEGY (0) index to parameter array // GAMES (1) index to parameter array // VERBOSITY (2) index to parameter array // SEED (3) index to parameter array // ST_STAY (1) strategy code // ST_RANDOM (2) strategy code // ST_SWITCH (3) strategy code // GOAT (0) losing prize // CAR (1) winning prize // // Variables: // d[2][2] (data array) - long int (to allow for large number of games) // data[0][0]: Stayed&Lost // data[0][1]: Stayed&Won // data[1][0]: Switched&Lost // data[1][1]: Switched&Won // p[3] (parameters array) - long int (for games and seed) // parameter[0]: strategy // parameter[1]: games to play // parameter[2]: verbosity level // parameter[3]: random number seed // // 1) TASK: Get information from user // 1.1) CALL: GetUserData(p) // 2) TASK: Simulate the games // 2.1) CALL: PlayGames(d, p) // 3) TASK: Output final results. // 3.1) CALL: FinalResults(p[STRATEGY], d) //== MACRO DEFINITIONS ==================================================== #define STAY (0) #define SWITCH (1) #define LOST (0) #define WON (1) #define STRATEGY (0) #define GAMES (1) #define VERBOSITY (2) #define SEED (3) #define ST_STAY (1) #define ST_RANDOM (2) #define ST_SWITCH (3) #define GOAT (0) #define CAR (1) //== INCLUDE FILES ======================================================== #include // printf(), scanf() #include // RAND_MAX, srand(), rand() //== FUNCTION PROTOTYPES (functions called in main() ) ==================== void PrintHeader(void); void PlayGames(long int p[], long int d[][2]); void GetUserData(long int p[]); void FinalResults(int strategy, long int d[][2]); //== MAIN FUNCTION ======================================================== int main(void) { long int p[4]; long int d[2][2]; PrintHeader(); printf("\n"); // Print a blank line // 1) TASK: Get information from user GetUserData(p); // 2) TASK: Simulate the games PlayGames(p, d); // 3) TASK: Output final results. FinalResults( (int) p[STRATEGY], d); return(0); } //== SUPPORT FUNCTION PROTOTYPES (functions not called in main() ) ======== void Verbosity(long int p[], long int d[][2], int won, int switched); int PlayMonty(int WillSwitch); int RemainingDoor(int CarDoor, int PlayerDoor); int RandInt(int min, int max); int Switch(int Strategy); int PickOne(int a, int b); void Stats(long int won, long int lost); void DescribeStrategy(int strategy); void PrintPercentage(long int fraction, long int total); long int BoundsLimit(long int n, long int min, long int max); //== SUPPORT FUNCTIONS ==================================================== void PrintHeader(void) { printf("========================================" "=======================================\n"); printf("Course....... %s-%i (%s %i)\n", COURSE, SECTION, TERM, YEAR); printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE); printf("Assignment... %s (Rev %i) (Source Code in %s)\n", ASSIGNMENT, REVISION, FILENAME); printf("Description.. %s\n", TITLE); printf(" %s\n", SUBTITLE); printf("========================================" "=======================================\n"); return; } //==================================================================== // PSEUDOCODE FOR SUPPORT FUNCTIONS //==================================================================== // ----------------------------------------------------------- // void PlayGames(long int p[], long int d[][2]) // ----------------------------------------------------------- // // 1) TASK: Initialize necessary variables. // 1.1) SET: data[?][?] = 0 (all elements to 0) // 2) TASK: Seed the random number generator // 2.1) CALL: srand(p[SEED]) // 3) TASK: Play the Games // 3.2) WHILE: (p[GAMES] > 0) // 3.2.1) TASK: Play the game based on strategy and verbosity. // 3.2.1.1) SET: WillSwitch = Switch(strategy) // 3.2.1.2) SET: won = PlayMonty(Willswitch) // 3.2.2) TASK: Update variables based on game outcome. // 3.2.2.1) SET: data[WillSwitch][Won]++ // 3.2.3) TASK: Generate output based on verbosity. // 3.2.3.1) CALL: Verbosity(p, d, won, willswitch) // 3.2.4) SET: p[GAMES]-- // 4) RETURN: void PlayGames(long int p[], long int d[][2]) { int WillSwitch, Won; // 1) TASK: Initialize necessary variables. d[STAY][WON] = 0; d[STAY][LOST] = 0; d[SWITCH][WON] = 0; d[SWITCH][LOST] = 0; // 2) TASK: Seed the random number generator srand( (unsigned) p[SEED]); // 3) TASK: Play the Games while(p[GAMES]) { WillSwitch = Switch( (int) p[STRATEGY]); Won = PlayMonty(WillSwitch); d[WillSwitch][Won]++; Verbosity(p, d, Won, WillSwitch); p[GAMES]--; } return; } // ----------------------------------------------------------- // void Verbosity(long int p[], long int d[][2], int won, int switched) // ----------------------------------------------------------- // // This function prints out information after each game based // on the verbosity level requested. // // 1) TASK: Handle Verbosity Level 0 // 1.1) REM: Do nothing // 2) TASK: Handle Verbosity Level 1 // 2.1) IF: (p[VERBOSITY] > 0) // 2.1.1) OUT: "Results for this game: Player " // 2.1.2) IF: (won) // 2.1.2.1) OUT: "WON " // 2.1.3) ELSE: // 2.1.3.1) OUT: "LOST" // 3) TASK: Handle Verbosity Level 2 // 3.1) IF: (p[VERBOSITY] > 1) // 3.1.1) OUT: "Player chose to " // 3.1.2) IF: (switched) // 3.1.2.1) OUT: "SWITCH" // 3.1.3) ELSE: // 2.1.3.1) OUT: "STAY " // 4) TASK: Handle Verbosity Level 3 // 4.1) IF: (p[VERBOSITY] > 2) // 4.1.1) TASK: Generate Totals // 4.1.1.1) GamesWon = d[STAY][WON] + d[SWITCH][WON] // 4.1.1.2) GamesLost = d[STAY][LOST] + d[SWITCH][LOST] // 4.1.1.3) GamesStayed = d[STAY][WON] + d[STAY][LOST] // 4.1.1.4) GamesSwitched = d[SWITCH][WON] + d[SWITCH][LOST] // 4.1.1.5) GamesTotal = GamesWon + GamesLost // 4.1.2) TASK: Output Cumulative Totals // 4.1.2.1) OUT: "Cumulative Stats:" // 4.1.2.2) OUT: "Total Games Played: .............. " GamesTotal // 4.1.2.3) OUT: "Total Games Won: ................. " GamesWon // 4.1.2.4) OUT: "Total Games Lost: ................ " GamesLost // 4.1.2.5) OUT: "Total Games Stayed: .............. " GamesStayed // 4.1.2.6) OUT: "Total Games Stayed and Won:....... " d[STAY][WON] // 4.1.2.7) OUT: "Total Games Stayed and Lost:...... " d[STAY][LOST] // 4.1.2.8) OUT: "Total Games Switched: ............ " GamesStayed // 4.1.2.9) OUT: "Total Games Switched and Won: .... " d[SWITCH][WON] // 4.1.2.10) OUT: "Total Games Switched and Lost: ... " d[SWITCH][LOST] // 5) TASK: Handle Verbosity Level 4 // 5.1) IF: (p[VERBOSITY] > 3) // 5.1.1) OUT: "Win Percentages:" // 5.1.2) OUT: "Overall: " PrintPercentage(GamesWon, GamesTotal) // 5.1.3) OUT: "Stayed:" PrintPercentage(d[STAY][WON], GamesStayed) // 5.1.4) OUT: "Switched: " PrintPercentage(d[SWITCH][WON], GamesSwitched) // 6) RETURN: void Verbosity(long int p[], long int d[][2], int won, int switched) { long int GamesWon; long int GamesLost; long int GamesStayed; long int GamesSwitched; long int GamesTotal; // 1) TASK: Handle Verbosity Level 0 // 1.1) REM: Do nothing // 2) TASK: Handle Verbosity Level 1 if(p[VERBOSITY] > 0) { printf("Results for this game: Player "); if(won) printf("WON " ); else printf("LOST" ); } else return; // 3) TASK: Handle Verbosity Level 2 if(p[VERBOSITY] > 1) { printf("Player chose to "); if(switched) printf("SWITCH \n" ); else printf("STAY \n" ); } else { printf("\n"); return; } // 4) TASK: Handle Verbosity Level 3 if(p[VERBOSITY] > 2) { // 4.1) IF: (p[VERBOSITY] > 2) // 4.1.1) TASK: Generate Totals GamesWon = d[STAY][WON] + d[SWITCH][WON]; GamesLost = d[STAY][LOST] + d[SWITCH][LOST]; GamesStayed = d[STAY][WON] + d[STAY][LOST]; GamesSwitched = d[SWITCH][WON] + d[SWITCH][LOST]; GamesTotal = GamesWon + GamesLost; // 4.1.2) TASK: Output Cumulative Totals printf("Cumulative Stats:\n"); printf("Total Games Played: .............. %li\n", GamesTotal); printf("Total Games Won: ................. %li\n", GamesWon); printf("Total Games Lost: ................ %li\n", GamesLost); printf("Total Games Stayed: .............. %li\n", GamesStayed); printf("Total Games Stayed and Won:....... %li\n", d[STAY][WON]); printf("Total Games Stayed and Lost:...... %li\n", d[STAY][LOST]); printf("Total Games Switched: ............ %li\n", GamesStayed); printf("Total Games Switched and Won: .... %li\n", d[SWITCH][WON]); printf("Total Games Switched and Lost: ... %li\n", d[SWITCH][LOST]); } else { return; } // 5) TASK: Handle Verbosity Level 4 if(p[VERBOSITY] > 3) { printf("Win Percentages:\n);"); printf("Overall: "); PrintPercentage(GamesWon, GamesTotal); printf("\n"); printf("Stayed: "); PrintPercentage(d[STAY][WON], GamesStayed); printf("\n"); printf("Switched: "); PrintPercentage(d[SWITCH][WON], GamesSwitched); printf("\n"); } return; } // ----------------------------------------------------------- // int PlayMonty(int WillSwitch) // ----------------------------------------------------------- // // This function plays a single game according to the Rules of the Game. // // The Rules of the Game: // // 1) TASK: Randomly place a car behind one of three doors. // 1.1) SET: CarDoor = RandInt(0,2) // // 2) TASK: The player picks a door. // 2.1) SET: PlayerDoor = RandInt(0,2) // // 3) TASK: One of the non-picked, non-winning doors is opened. // 3.1) SET: RemainingDoor = RemainingDoor(CarDoor, PlayerDoor) // // 4) TASK: The player has the choice to switch doors. // 4.1) IF: (WillSwitch) // 4.1.1) SET: PlayerDoor = RemainingDoor // // 5) TASK: The player's final selection is revealed. // 5.1) IF: (PlayerDoor = CarDoor) // 5.1.1) RETURN: WON // 5.2) ELSE: // 5.2.1) RETURN: LOST int PlayMonty(int WillSwitch) { int CarDoor, PlayerDoor, OtherDoor; // 1) TASK: Randomly place a car behind one of three doors. CarDoor = RandInt(1,3); // 2) TASK: The player picks a door. PlayerDoor = RandInt(1,3); // 3) TASK: One of the non-picked, non-winning doors is opened. OtherDoor = RemainingDoor(CarDoor, PlayerDoor); // 4) TASK: The player has the choice to switch doors. if(WillSwitch) PlayerDoor = OtherDoor; // 5) TASK: The player's final selection is revealed. if(PlayerDoor == CarDoor) return(WON); else return(LOST); } // ----------------------------------------------------------- // int RemainingDoor(int CarDoor, int PlayerDoor) // ----------------------------------------------------------- // // This function returns the door number that the player has // the option to switch to. The basic constraint is that the // door cannot be the player's original door and it must be // consistent with the fact that Monty will open a door that // is neither the player's door nor the winning door. // // 1) IF: (PlayerD = 1) // 1.1) IF: (CarDoor = 1) // 1.1.1) RETURN: PickOne(2,3) // 1.2) IF: (CarDoor = 2) // 1.2.1) RETURN: 2 // 1.3) IF: (CarDoor = 3) // 1.3.1) RETURN: 3 // // 2) IF: (PlayerDoor = 2) // 2.1) IF: (CarDoor = 1) // 2.1.1) RETURN: 1 // 2.2) IF: (CarDoor = 2) // 2.2.1) RETURN: PickOne(1,3) // 2.3) IF: (CarDoor = 3) // 2.3.1) RETURN: 3 // // 3) IF: (PlayerDoor = 3) // 3.1) IF: (CarDoor = 1) // 3.1.1) RETURN: 1 // 3.2) IF: (CarDoor = 2) // 3.2.1) RETURN: 2 // 3.3) IF: (CarDoor = 3) // 3.3.1) RETURN: PickOne(2,3) int RemainingDoor(int CarDoor, int PlayerDoor) { switch(PlayerDoor) { case 1: switch(CarDoor) { case 1: return(PickOne(2,3)); // Monty could open Door 2 or 3 case 2: return(2); // Monty had to open Door 3 case 3: return(3); // Monty had to open Door 2 } break; case 2: switch(CarDoor) { case 1: return(1); // Monty had to open Door 3 case 2: return(PickOne(1,3)); // Monty could open Door 1 or 3 case 3: return(3); // Monty had to open Door 1 } break; case 3: switch(CarDoor) { case 1: return(1); // Monty had to open Door 2 case 2: return(2); // Monty had to open Door 1 case 3: return(PickOne(1,2)); // Monty could open Door 1 or 2 } break; } return(-1); // Should never get here } // ----------------------------------------------------------- // int RandInt(int min, int max) // ----------------------------------------------------------- // // This function randomly returns a random integer such that // a <= return valueeither <= b // 1) RETURN: min + rand()%(min-max+1) int RandInt(int min, int max) { return(min + rand()%(max-min+1)); } // ----------------------------------------------------------- // int Switch(int Strategy) // ----------------------------------------------------------- // // This function takes a strategy number {0,1,2} and returns whether // the player will elect to switch in the next game played. // // 1) IF: (Strategy = ST_STAY) // 1.1) RETURN: STAY // 2) IF: (Strategy = ST_RANDOM) // 2.1) RETURN: PickOne(STAY, SWITCH) // 3) IF: (Strategy = ST_SWITCH) // 3.1) RETURN: SWITCH int Switch(int Strategy) { if(ST_STAY == Strategy) return(STAY); if(ST_RANDOM == Strategy) return(PickOne(STAY, SWITCH)); if(ST_SWITCH == Strategy) return(SWITCH); return(-1); // Should never get here } // ----------------------------------------------------------- // int PickOne(int a, int b) // ----------------------------------------------------------- // // This function randomly returns either a or b // // 1) IF: (rand()%2) // 1.2) RETURN: a // 2) ELSE: // 2.1) RETURN: b int PickOne(int a, int b) { if(rand()%2) return(a); return(b); } // ----------------------------------------------------------- // void Stats(long int won, long int lost) // ----------------------------------------------------------- // // This function prints out the statistics based on games won and lost // // 1) OUT: BLANK LINE // 2) OUT: "Games Played:.... " (won + lost) // 3) OUT: "Games Won:....... " (won) // 4) OUT: "Games Lost:...... " (lost) // 5) OUT: "Win Percentage:.. " PrintPercentage(won, won+lost) // 8) OUT: BlANK LINE // 9) RETURN: void Stats(long int won, long int lost) { printf("\n"); printf("Games Played:.... %li\n", (won + lost)); printf("Games Won:....... %li\n", won); printf("Games Lost:...... %li\n", lost); printf("Win Percentage:.. "); PrintPercentage(won, won+lost); printf("\n"); printf("\n"); return; } // ----------------------------------------------------------- // void PrintPercentage(long int fraction, long int total) // ----------------------------------------------------------- // // This function prints a percentage of "N/A" if total = 0 // // 1) IF: (total) = 0 // 6.1) OUT: "N/A" // 7) ELSE: // 7.1) SET: Percentage = 100 * fraction/total // 7.2) OUT: Percentage "%" // void PrintPercentage(long int fraction, long int total) { if(0 == total) printf("N/A"); else printf("%6.2f%%", 100.0*((double)fraction/(double)total) ); return; } // ----------------------------------------------------------- // void FinalResults(int strategy, long int d[][2]) // ----------------------------------------------------------- // // This function prints out the final results of the simulation // // 1) TASK: Output Strategy Discription // 1.1) CALL: DescribeStrategy(strategy) // 2) TASK: Output Statistics for overall games played // 2.1) OUT: "For All Games played:" // 2.2) SET: won = d[STAY][WON] + d[SWITCH][WON] // 2.3) SET: lost = d[STAY][LOST] + d[SWITCH][LOST] // 2.4) CALL: Stats(won, lost) // 3) TASK: Output Statistics for games Stayed // 3.1) OUT: "For Games in which the Player Stayed:" // 3.2) SET: won = d[STAY][WON] // 3.3) SET: lost = d[STAY][LOST] // 3.4) CALL: Stats(won, lost) // 4) TASK: Output Statistics for games Switched // 4.1) OUT: "For Games in which the Player Switched:" // 4.2) SET: won = d[SWITCH][WON] // 4.3) SET: lost = d[SWITCH][LOST] // 4.4) CALL: Stats(won, lost) // 5) RETURN: void FinalResults(int strategy, long int d[][2]) { // 1) TASK: Output Strategy Discription DescribeStrategy(strategy); // 2) TASK: Output Statistics for overall games played printf("For All Games played:\n"); Stats(d[STAY][WON]+d[SWITCH][WON], d[STAY][LOST]+d[SWITCH][LOST]); // 3) TASK: Output Statistics for games Stayed printf("For Games in which the Player Stayed:\n"); Stats(d[STAY][WON], d[STAY][LOST]); // 4) TASK: Output Statistics for games Switched printf("For Games in which the Player Switched:\n"); Stats(d[SWITCH][WON], d[SWITCH][LOST]); return; } // ----------------------------------------------------------- // void DescribeStrategy(int Strategy) // ----------------------------------------------------------- // // This function prints a description of the chosen strategy // // 1) OUT: "The chosen strategy was to " // 2) IF: (Strategy = 1) // 2.1) OUT: "always stay with the initial door." // 2) IF: (Strategy = 2) // 2.1) OUT: "randomly pick whether to stay or switch." // 2) IF: (Strategy = 3) // 2.1) OUT: "always switch to the remaining door." // 3) RETURN: void DescribeStrategy(int Strategy) { printf("The chosen strategy was to "); if(ST_STAY == Strategy) printf("always stay with the initial door.\n"); if(ST_RANDOM == Strategy) printf("randomly pick whether to stay or switch.\n"); if(ST_SWITCH == Strategy) printf("always switch to the remaining door.\n"); return; } // ----------------------------------------------------------- // void GetUserData(long int p[]) // ----------------------------------------------------------- // This function stores the user supplied information in an array. // The user is given the allowed values or ranges for their input. // If there response is invalid, default values are chosen. // // 1) TASK: Get Number of games to play. // 1.1) OUT: "How many games do you want to play? (1-1000000000)" // 1.2) GET: p[GAMES] // 1.3) SET: p[GAMES] = BoundsLimit(p[GAMES], 1, 1000000000) // // 2) GET: Strategy to use. // 2.1) OUT: "Available Strategies: " // 2.2) OUT: " 1) Always stay with the initial choice" // 2.3) OUT: " 2) Randomly stay or switch after a door is revealed" // 2.4) OUT: " 3) Always switch to the remaining door" // 2.5) OUT: "Which Stategy do you wish to follow? (1-3): " // 2.6) GET: parameters[STRATEGY] // 2.7) SET: p[STRATEGY] = BoundsLimit(p[STRATEGY], 1, 3) // // 3) GET: Verbosity level. // 3.1) OUT: "What Verbosity Level do you desire? (0-4): " // 3.2) GET: parameters[VERBOSITY] // 3.3) SET: p[VERBOSITY] = BoundsLimit(p[VERBOSITY], 0, 4) // // 4) GET: Random number seed // 4.1) OUT: "Enter random number seed: (1-1000000000)" // 4.2) GET: parameters[SEED] // 4.3) SET: p[SEED] = BoundsLimit(p[SEED], 1, 1000000000) // // 5) RETURN: void GetUserData(long int p[]) { // 1) TASK: Get Number of games to play. printf("How many games do you want to play? (1-1000000000)"); scanf("%li", &p[GAMES]); p[GAMES] = BoundsLimit(p[GAMES], 1, 1000000000L); // 2) GET: Strategy to use. printf("Available Strategies: \n"); printf(" 1) Always stay with the initial choice.\n"); printf(" 2) Randomly stay or switch after a door is revealed.\n"); printf(" 3) Always switch to the remaining door.\n"); printf("Which Stategy do you wish to follow? (1-3): "); scanf("%li", &p[STRATEGY]); p[STRATEGY] = BoundsLimit(p[STRATEGY], 1, 3); // 3) GET: Verbosity level. printf("What Verbosity Level do you desire? (0-4): "); scanf("%li", &p[VERBOSITY]); p[VERBOSITY] = BoundsLimit(p[VERBOSITY], 0, 4); // 4) GET: Random number seed printf("Enter random number seed: (1-1000000000) "); scanf("%li", &p[SEED]); p[SEED] = BoundsLimit(p[SEED], 1, 1000000000L); return; } // ----------------------------------------------------------- // long int BoundsLimit(long int n, long int min, long int max) // ----------------------------------------------------------- // // This function limits n to a min and max value // // 1) IF: ( n < min ) // 1,1) OUT: "Invalid Entry - value set to " min // 1.2) RETURN: min // 2) IF: ( n > max ) // 2,1) OUT: "Invalid Entry - value set to " max // 2.2) RETURN: max // 3) RETURN: n long int BoundsLimit(long int n, long int min, long int max) { if(n < min) { printf("Invalid Entry - value set to %li\n", min); return(min); } if(n > max) { printf("Invalid Entry - value set to %li\n", max); return(max); } return(n); }