Programming Corner from Icon Newsletter 23


February 3, 1987; Icon Version 6

A Program to Deal and Display Bridge Hands

The choice of data representations often is one of the most important aspects in the design of programs that perform nonnumerical computations. Not only do data representations affect program speed and space requirements, but they also may play a central role in the difficulty or ease of writing the program.

Icon offers an unusually wide variety of data types. While it provides more flexibility than is found in some other programming languages, it also presents the programmer with more choices. Sometimes the best choice is not the obvious one.

The following program, which is an adaptation of one from the Icon program library, illustrates a compact data representation that often is useful in programs that manipulate a small number of objects. This data representation also gives computational efficiency, since it allows the use of built-in operations that otherwise might have to be provided as procedures.

The problem is to produce and display hands in the game of bridge. The basic operations are shuffling the deck, dealing the cards to the players, and displaying the results. Not surprisingly, displaying the results is the most difficult part of the program.

In the game of bridge, the deck consists of 52 cards with 13 denominations in four suits. The suits are clubs, diamonds, hearts, and spades, and the denominations are 2 through 10, jack, queen, king, and ace.

There are lots of possible ways of representing the cards. Since a card has two attributes -- its suit and its denomination -- a record type with these fields is a possibility. This representation presents the problem (among others) of how to represent the deck -- that is, how to keep track of the cards. A list of the records is a possibility. A simpler, if less elegant, choice of data representation is simply a list of 52 elements in which the position encodes the attributes of the individual card. In this case, the real representation of the card is its index in the list. In other words, 52 integers are all that are necessary, and the list is used to keep them together. Other representations are possible. For example, the string "8C" might represent the eight of clubs, and so on.

There is clearly some advantage in having a simple object to represent a card. The method used in the following program is to associate a unique character with each card. This allows groups of cards to be represented by strings, and cset operations can be used to operate on groups of cards.

Since there are 52 cards, 52 different characters are needed. For the program that follows, any 52 characters will do, but a convenient choice (purely by coincidence) is
deckimage := &lcase || &ucase
This choice has the additional advantage of facilitating debugging.

The next question is which character corresponds to which card. This decision can be made in many ways. The one chosen here is to consider the deck to be a concatenation of the suits in order, with the first 13 characters corresponding to the clubs, the next 13 to the diamonds, and so on. Thus, the characters abc ... m are clubs, the characters nop ... z are diamonds, the characters ABC ... M are hearts, and the characters NOP ... Z are spades. Except for possible debugging, however, these explicit correspondences never come up. The specific order of denominations is rather arbitrary, but it turns out to be convenient for display purposes to rank the cards according to the order of characters in the following string:
rank := "AKQJT98765432"
Thus, the character a is the ace of clubs, the character z is the two of diamonds, and so on. Again, this never comes up explicitly in the program.

It might appear that encoding the card deck as a string of characters would introduce all sorts of problems, especially in figuring out which card is which and producing output that gives an understandable representation. Actually, most of the operations in the program do not require such determinations. For example, shuffling is insensitive to the suits or denominations of cards -- it simply is the rearrangement of a number of objects that are as anonymous as the backs of real cards are supposed to be.

Shuffling is a good place to start:
procedure shuffle(deck)
   local i

   every i := *deck to 2 by -1 do deck[?i] :=: deck[i]
   return deck
end
This procedure is an implementation of a method given by Knuth in his book, Seminumerical Algorithms. It operates by starting at the end of the deck, exchanging that card with a randomly chosen one, and then working down toward the beginning, chosing the exchange card from the remainder of the deck. Whether or not this produces a `good' shuffle is somewhat of an open question, but it seems to work well in practice.

Once the deck is shuffled, it is customary to distribute the cards to the four players by dealing them one-by-one to the four players in turn. This method of distribution is more of a convention than a necessity and is motivated partly by social considerations. If the deck really is shuffled properly, it is good enough to give the first 13 cards to the first player, the next 13 to the next player, and so on. It is also a lot easier to program.

The real fun comes in displaying the results of the deal. In bridge, it is customary to separate the cards in each hand into suits and to arrange the cards in each suit from higher to lower denomination. Here is where Icon's cset and mapping operations can be used to advantage. The idea is to extract from a hand of 13 cards all of the cards of a given suit by mapping the cards of the desired suit into themselves and mapping all other cards into a single character that is not in the deck, effectively throwing away the cards that are not in the desired suit. The blank character is useful for this elimination. For example, the mapping string to discard all cards that are not clubs is constructed as follows:
denom := deckimage[1+:13]
blanks := repl(" ",13)
Cmap := denom || repl(blanks,3)
The strings denom and blanks are used here in place of a more direct construction of Cmap, since they are useful in producing maps for the other suits.

Now,
clubs := map(hand,deckimage,Cmap)
assigns to clubs a string in which all the characters correspond-ing to clubs are left unchanged, while all other characters are blanks. This string still is 13 characters long, and probably contains a lot of blanks. The clubs can be obtained by constructing a cset with the blank removed:
clubs --:= ' '
(There's an augmented assignment operation you don't see very often. It does not appear in the actual program, where the result is computed in a single expression.)

At this point, clubs contains all the clubs in the hand, but they are in a cset and unordered. The desired string with the clubs in order and mapped into their denominations is produced by
clubs := map(clubs,denom,rank)
The result comes out correctly, since the automatic conversion of the cset to a string in the first argument to map puts the char-acters in alphabetical order.

That's about all there is to it, except for the mechanics of handling all of the suits in all of the hands and formatting the output in a manner that is customary, with the four hands arranged according to the points of the compass. Here's the complete program, arbitrarily set up to print five sets of hands. Comments have been removed to save space.
global deck, deckimage, handsize
global suitsize, denom, rank, blanks

procedure main()
   deck := deckimage := &lcase || &ucase
   handsize := suitsize := *deck / 4
   rank := "AKQJT98765432"
   blanks := repl(" ",suitsize)
   denom := &lcase[1+:suitsize]
   every 1 to 5 do display()
end

procedure display()
   local layout, i
   static bar, offset

   initial {
      bar := "\n" || repl("-",33)
      offset := repl(" ",10)
      }

   deck := shuffle(deck)
   layout := []
   every push(layout,show(deck[(0 to 3) *
      handsize + 1 +: handsize]))
   write()
   every write(offset,!layout[1])
   write()
   every i := 1 to 4 do
      write(l
   every write(offset,!layout[3])
   write(bar)
end
procedure shuffle(deck)
   local i

   every i := *deck to 2 by -1 do deck[?i] :=: deck[i]
   return deck
end
procedure show(hand)
   static Cmap, Dmap, Hmap, Smap
   initial {
      Cmap := denom || repl(blanks,3)
      Dmap := blanks || denom || repl(blanks,2)
      Hmap := repl(blanks,2) || denom || blanks
      Smap := repl(blanks,3) || denom
      }
return [
   "S: " || arrange(hand,Smap),
   "H: " || arrange(hand,Hmap),
   "D: " || arrange(hand,Dmap),
   "C: " || arrange(hand,Cmap)
   ]
end
procedure arrange(hand,suit)
   return map(map(hand,deckimage,suit) -- ' ', denom,rank) end
An example of the output from this program is:
             S: 3
             H: T7
             D: AKQ762
             C: QJ94

S: KQ987                  S: A652
H: 52                     H: AKQ4
D: T94                    D: 3
C: T82                    C: A653

             S: JT4
             H: J9863
             D: J85
             C: K7
A couple of things are left for you to consider, including the use of denom for all suits and the method used to provide the final layout.

Processing Command-Line Arguments

One final subject for this issue's programming corner concerns the use of command-line arguments and methods for processing them. In the program above, for example, it would be useful to be able to specify how many rounds of hands are to be produced and possibly to be able to set the seed for random number generation to produce different sets of hands. One way to do this is to provide an interactive interface, prompting the user for this information. An alternative method, and one that often is handier, is to allow the user to specify such matters as options on the command line when the program is executed.

For example, if the program above is named deal, it might be executed as
deal -h 10 -s 17
The argument following -h indicates that 10 rounds of hands are to be produced and the argument following -s indicates that the seed for random number generation is to be 17. The syntax shown here is the standard one for UNIX; other operating systems conventionally handle it differently. Such differences are inessential here. However, such command-line arguments, in whatever form, should be optional and defaults should be provided if they are omitted.

In the example above, there are four command-line arguments. These are passed as a list of strings to the main procedure of deal, as if the argument to main were
["-h", "10", "-s", "17"]
Thus, the main procedure of the program above might be rewritten as:
procedure main(a)
   local s, hands

     . . .
   hands := 5
   while s := get(a) do {
      case s of {
         "-h": hands := integer(get(a)) | use()
         "-s": &random := integer(get(a)) | use()
         default: use()
         }
      }
every 1 to hands do display()
  . . .
The procedure use terminates program execution with an error message in case there is an erroneous command-line argument. UNIX favors a terse style for such error messages, and a version of use in this style might be
procedure use()
   stop("usage: deal [-h n] [-s n]")
end
Note that get(a) provides an easy and concise way of obtaining the command-line arguments. Other possibilities are using an explicit index, as in a[i], or iterating over the list, as in !a. Try rephrasing the processing of the command-line arguments above to see why the use of get is better. Of course, get consumes the list. That does not matter in the case here. How could this be reformulated to avoid consuming the list while retaining the advantages that get provides?


Icon home page