Work the Shell

The last few months, we've been building a complex shell script to play elements of the game of Cribbage, demonstrating a variety of concepts and techniques as we proceed. That's all good, and last month, the script expanded to include a “shuffle” capability and the ability to deal out six cards, a typical two-player starting hand.

Cribbage tip: in a three-player game, each player gets five cards, and the extra is dealt directly into the “crib”—the extra hand counted after play by the dealer.

The challenge we're going to tackle this month is figuring out the best four cards to keep of those initial six, based on potential point values of the different hands. Ultimately, a fifth, “cut card”, is turned up that everyone shares (somewhat akin to the shared cards in Texas Hold 'em), but smart Cribbage players seek to maximize the four they hold and celebrate when the fifth adds to the point value of the hand, rather than count on that cut card to make the hand.

So what's valuable in a Cribbage hand? Sequential runs of three or more cards, pairs or better of the same rank, having all the cards in your hand match suit (and possibly the cut card), combinations of card ranks that add up to 15, and having the jack of the same suit as is on the cut card.

Cards of the same rank—pairs or better—are tricky to count because the game works on combinations. So 5H, 5D is worth two points “for the pair”, but 5H, 5D, 5S is worth six points, because it combines to three pairs: 5H+5D, 5H+5S and 5D+5S. Four of a kind? A sweet 12 points and a very rare combination indeed.

Critical to know: aces always are worth 1 when counting up fifteens, and all face cards are worth 10 points. So A+4+K is a fifteen, just as 9+6 is, though for pairs, it's the same rank, not just pairs of face cards. In other words, J+K is not a pair.

Where counting gets tricky is those combinations of fifteens. A great hand, for example, is 6S, 7H, 8D, 8S, which offers two points for 7H+8D, two points for 7H+8S, three points for 6S+7H+8D, another three points for 6S+7H+8S and a final two points for the pair 8D+8S—very nice. If the cut card is another 7 or, even better, another 8, you can see where there are a lot of points in that potential hand!

The challenge, of course, is doing all of this programmatically. When we left off the program last month, it could deal six cards to us and sort them in increasing rank order, which is helpful, particularly in recognizing runs.

The first problem we have is actually earlier than anything to do with card values. It's to calculate all possible four-card combinations out of a six-card hand. It's combinatorics—something I really enjoyed back when I took that class in college for my CS degree.

What we're looking at is actually factorial math. So “six choose four” is really 6! minus 2!, which is generally written as shown in Figure 1, where n is the total number of cards, and m is the subset we want to choose. In this case, it's 6! / 4!(6! - 4!).

Figure 1. Equation for “Six Choose Four”

A factorial number is calculated as the multiple of all decreasing numbers, so 4! = 4 x 3 x 2 x 1, and 6! = 6 x 5 x 4 x 3 x 2 x 1. Of course, the “x 1” part is pointless, so we can skip it. 4! = 24 and 6! = 720, which means that we have 15 card combinations to check for points. (If we had only five cards dealt because it was a three- or four-person Cribbage game, we'd have only five combinations to evaluate instead.)

The question is, how do we figure out all 15 of those combinations easily? I mean, I could hard-code all 15 of them—it's only four digits per subset, after all—but that seems less interesting than trying to solve the more-general mathematical equation. And yes, I can see myself getting sidetracked as I proceed, but that's part of the fun of programming when you're not on a deadline, right?

Um, never mind. Let's just take as a given that for six-choose-four, there are these specific combinations and no more: {1,2,3,4}, {1,2,3,5}, {1,2,3,6}, {1,2,4,5}, {1,2,4,6}, {1,2,5,6}, {1,3,4,5}, {1,3,4,6}, {1,3,5,6}, {1,4,5,6}, {2,3,4,5}, {2,3,4,6}, {2,3,5,6}, {2,4,5,6} and {3,4,5,6}.

If we're working with five-choose-four, the combinations are {a,b,c,d}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e} and {b,c,d,e}.

The easy way to code this is as an array of arrays. Let's do it this way:

# six choose four
sixfour[0]="0 1 2 3";  sixfour[1]="0 1 2 4"
sixfour[2]="0 1 2 5";  sixfour[3]="0 1 3 4"
sixfour[4]="0 1 3 5";  sixfour[5]="0 1 4 5"
sixfour[6]="0 2 3 4";  sixfour[7]="0 2 3 5"
sixfour[8]="0 2 4 5";  sixfour[9]="0 3 4 5"
sixfour[10]="1 2 3 4"; sixfour[11]="1 2 3 5"
sixfour[12]="1 2 4 5"; sixfour[13]="1 3 4 5"
sixfour[14]="2 3 4 5"

If you're paying close attention to the script we've been creating, you know that our hand is indexed starting at 0, so the card values are 0–5 instead. That's easily fixed by shifting every value down one in the predefined arrays.

Now it's just a matter of interpreting the different sixfour array values as a set of four cards to select, and here's how I do it:

for subhand in {0..14}
do
  /bin/echo -n "Subhand ${subhand}:"
  for thecard in ${sixfour[$subhand]}
  do
    showcard ${hand[$thecard]}
    /bin/echo -n "  $showcardvalue"
  done
  echo ""
done

The echo statements (remember -n prevents a carriage return being appended to the output) aren't important to the final code, but for this interim solution, you'll see how it works by me just tucking it into the end of the program, just after the code that deals, sorts and shows the full six-card hand:

Hand: AS, 5C, 7H, 8H, 9D, JS.
Subhand 0:  AS  5C  7H  8H
Subhand 1:  AS  5C  7H  9D
Subhand 2:  AS  5C  7H  JS
Subhand 3:  AS  5C  8H  9D
Subhand 4:  AS  5C  8H  JS
Subhand 5:  AS  5C  9D  JS
Subhand 6:  AS  7H  8H  9D
Subhand 7:  AS  7H  8H  JS
Subhand 8:  AS  7H  9D  JS
Subhand 9:  AS  8H  9D  JS
Subhand 10:  5C  7H  8H  9D
Subhand 11:  5C  7H  8H  JS
Subhand 12:  5C  7H  9D  JS
Subhand 13:  5C  8H  9D  JS
Subhand 14:  7H  8H  9D  JS

That's a lot of four-card hands, but at least we've got them. Next month, we'll actually start writing the code to evaluate hand values. Stay tuned!