Case Study: Card Shuffling and Dealing Simulation
Case Study Card Shuffling and Dealing Simulation
This section uses random-number generation to develop a card shuffling and dealing simulation program. This program can then be used as a basis for implementing programs that play specific card games. To reveal some subtle performance problems, we have intentionally used suboptimal shuffling and dealing algorithms. In the exercises, we develop more efficient algorithms.
Using the top-down, stepwise-refinement approach, we develop a program that will shuffle a deck of 52 playing cards and then deal each of the 52 cards. The top-down approach is particularly useful in attacking larger, more complex problems than we have seen in the early chapters.
We use a 4-by-13 two-dimensional array deck to represent the deck of playing cards (Fig. 8.23). The rows correspond to the suitsrow 0 corresponds to hearts, row 1 to diamonds, row 2 to clubs and row 3 to spades. The columns correspond to the face values of the cardscolumns 0 through 9 correspond to faces ace through 10, respectively, and columns 10 through 12 correspond to jack, queen and king, respectively. We shall load the string array suit with character strings representing the four suits (as in Fig. 8.22) and the string array face with character strings representing the 13 face values.
Figure 8.23. Two-dimensional array representation of a deck of cards.
This simulated deck of cards may be shuffled as follows. First the array deck is initialized to zeros. Then, a row (03) and a column (012) are each chosen at random. The number 1 is inserted in array element deck[ row ][ column ] to indicate that this card is going to be the first one dealt from the shuffled deck. This process continues with the numbers 2, 3, ..., 52 being randomly inserted in the deck array to indicate which cards are to be placed second, third, ..., and 52nd in the shuffled deck. As the deck array begins to fill with card numbers, it is possible that a card will be selected twice (i.e., deck[ row ][ column ] will be nonzero when it is selected). This selection is simply ignored, and other rows and columns are repeatedly chosen at random until an unselected card is found. Eventually, the numbers 1 through 52 will occupy the 52 slots of the deck array. At this point, the deck of cards is fully shuffled.
This shuffling algorithm could execute for an indefinitely long period if cards that have already been shuffled are repeatedly selected at random. This phenomenon is known as indefinite postponement (also called starvation). In the exercises, we discuss a better shuffling algorithm that eliminates the possibility of indefinite postponement.
Performance Tip 8.3
|
Sometimes algorithms that emerge in a "natural" way can contain subtle performance problems such as indefinite postponement. Seek algorithms that avoid indefinite postponement. |
To deal the first card, we search the array for the element deck[ row ][ column ] that matches 1. This is accomplished with a nested for statement that varies row from 0 to 3 and column from 0 to 12. What card does that slot of the array correspond to? The suit array has been preloaded with the four suits, so to get the suit, we print the character string suit[ row ]. Similarly, to get the face value of the card, we print the character string face[ column ]. We also print the character string " of ". Printing this information in the proper order enables us to print each card in the form "King of Clubs", "Ace of Diamonds" and so on.
Let us proceed with the top-down, stepwise-refinement process. The top is simply
Shuffle and deal 52 cards
Our first refinement yields
Initialize the suit array
Initialize the face array
Initialize the deck array
Shuffle the deck
Deal 52 cards
"Shuffle the deck" may be expanded as follows:
For each of the 52 cards
Place card number in randomly selected unoccupied slot of deck
"Deal 52 cards" may be expanded as follows:
For each of the 52 cards
Find card number in deck array and print face and suit of card
Incorporating these expansions yields our complete second refinement:
Initialize the suit array
Initialize the face array
Initialize the deck array
For each of the 52 cards
Place card number in randomly selected unoccupied slot of deck
For each of the 52 cards
Find card number in deck array and print face and suit of card
"Place card number in randomly selected unoccupied slot of deck" may be expanded as follows:
Choose slot of deck randomly
While chosen slot of deck has been previously chosen
Choose slot of deck randomly
Place card number in chosen slot of deck
"Find card number in deck array and print face and suit of card" may be expanded as follows:
For each slot of the deck array
If slot contains card number
Print the face and suit of the card
Incorporating these expansions yields our third refinement (Fig. 8.24):
|
1 Initialize the suit array 2 Initialize the face array 3 Initialize the deck array 4 5 For each of the 52 cards 6 Choose slot of deck randomly 7 8 While slot of deck has been previously chosen 9 Choose slot of deck randomly 10 11 Place card number in chosen slot of deck 12 13 For each of the 52 cards 14 For each slot of deck array 15 If slot contains desired card number 16 Print the face and suit of the card |
This completes the refinement process. Figures 8.258.27 contain the card shuffling and dealing program and a sample execution. Lines 6167 of function deal (Fig. 8.26) implement lines 12 of Fig. 8.24. The constructor (lines 2235 of Fig. 8.26) implements lines 13 of Fig. 8.24. Function shuffle (lines 3855 of Fig. 8.26) implements lines 511 of Fig. 8.24. Function deal (lines 5888 of Fig. 8.26) implements lines 1316 of Fig. 8.24. Note the output formatting used in function deal (lines 8183 of Fig. 8.26).
Figure 8.25. DeckOfCards header file.
|
1 // Fig. 8.25: DeckOfCards.h 2 // Definition of class DeckOfCards that 3 // represents a deck of playing cards. 4 5 // DeckOfCards class definition 6 class DeckOfCards 7 { 8 public: 9 DeckOfCards(); // constructor initializes deck 10 void shuffle(); // shuffles cards in deck 11 void deal(); // deals cards in deck 12 private: 13 int deck[ 4 ][ 13 ]; // represents deck of cards 14 }; // end class DeckOfCards |
Figure 8.26. Definitions of member functions for shuffling and dealing.
(This item is displayed on pages 435 - 437 in the print version)
|
1 // Fig. 8.26: DeckOfCards.cpp 2 // Member-function definitions for class DeckOfCards that simulates 3 // the shuffling and dealing of a deck of playing cards. 4 #include 5 using std::cout; 6 using std::left; 7 using std::right; 8 9 #include 10 using std::setw; 11 12 #include // prototypes for rand and srand 13 using std::rand; 14 using std::srand; 15 16 #include // prototype for time 17 using std::time; 18 19 #include "DeckOfCards.h" // DeckOfCards class definition 20 21 // DeckOfCards default constructor initializes deck 22 DeckOfCards::DeckOfCards() 23 { 24 // loop through rows of deck 25 for ( int row = 0; row <= 3; row++ ) 26 { 27 // loop through columns of deck for current row 28 for ( int column = 0; column <= 12; column++ ) 29 { 30 deck[ row ][ column ] = 0; // initialize slot of deck to 0 31 } // end inner for 32 } // end outer for 33 34 srand( time( 0 ) ); // seed random number generator 35 } // end DeckOfCards default constructor 36 37 // shuffle cards in deck 38 void DeckOfCards::shuffle() 39 { 40 int row; // represents suit value of card 41 int column; // represents face value of card 42 43 // for each of the 52 cards, choose a slot of the deck randomly 44 for ( int card = 1; card <= 52; card++ ) 45 { 46 do // choose a new random location until unoccupied slot is found 47 { 48 row = rand() % 4; // randomly select the row 49 column = rand() % 13; // randomly select the column 50 } while( deck[ row ][ column ] != 0 ); // end do...while 51 52 // place card number in chosen slot of deck 53 deck[ row ][ column ] = card; 54 } // end for 55 } // end function shuffle 56 57 // deal cards in deck 58 void DeckOfCards::deal() 59 { 60 // initialize suit array 61 static const char *suit[ 4 ] = 62 { "Hearts", "Diamonds", "Clubs", "Spades" }; 63 64 // initialize face array 65 static const char *face[ 13 ] = 66 { "Ace", "Deuce", "Three", "Four", "Five", "Six", "Seven", 67 "Eight", "Nine", "Ten", "Jack", "Queen", "King" }; 68 69 // for each of the 52 cards 70 for ( int card = 1; card <= 52; card++ ) 71 { 72 // loop through rows of deck 73 for ( int row = 0; row <= 3; row++ ) 74 { 75 // loop through columns of deck for current row 76 for ( int column = 0; column <= 12; column++ ) 77 { 78 // if slot contains current card, display card 79 if ( deck[ row ][ column ] == card ) 80 { 81 cout << setw( 5 ) << right << face[ column ] 82 << " of " << setw( 8 ) << left << suit[ row ] 83 << ( card % 2 == 0 ? ' ' : ' ' ); 84 } // end if 85 } // end innermost for 86 } // end inner for 87 } // end outer for 88 } // end function deal |
Figure 8.27. Card shuffling and dealing program.
(This item is displayed on pages 437 - 438 in the print version)
|
1 // Fig. 8.27: fig08_27.cpp 2 // Card shuffling and dealing program. 3 #include "DeckOfCards.h" // DeckOfCards class definition 4 5 int main() 6 { 7 DeckOfCards deckOfCards; // create DeckOfCards object 8 9 deckOfCards.shuffle(); // shuffle the cards in the deck 10 deckOfCards.deal(); // deal the cards in the deck 11 return 0; // indicates successful termination 12 } // end main
|
The output statement outputs the face right justified in a field of five characters and outputs the suit left justified in a field of eight characters (Fig. 8.27). The output is printed in two-column formatif the card being output is in the first column, a tab is output after the card to move to the second column (line 83); otherwise, a newline is output.
There is also a weakness in the dealing algorithm. Once a match is found, even if it is found on the first try, the two inner for statements continue searching the remaining elements of deck for a match. In the exercises, we correct this deficiency.