Solving Puzzles in C#: Poker Hands

I particularly like the solution to this puzzle as it can be easily adapted to any problem involving a deck of cards & the probability of being dealt a particular hand.

In this post I’ll be linking each code snippet to “LINQPad instant share” so you can literally execute the code as we go!

The Question

(courtesy of Mitch Wheat)

“How many five-card hands from a standard (52 card) deck of cards contain at least one card in each suit?”

LINQPad Solution

So as you might have guessed, we’re going to use a brute force approach. Before we can tackle the specific problem, we need to come up with a way of generating all possible hands. I figured the simplest (and reasonably efficient) way to represent a deck of cards is with a sequence of integers, each representing a card in the deck.

Enumerable.Range(0,52)

What’s nice about this, is we can quickly assign each integer a suit & the respective card values using the following query.

Generating Cards (http://share.linqpad.net/rkqnan.linq)

from i in Enumerable.Range(0,52)
let suit = i / 13
let card = (i % 13)
select new { card, suit }

This step is not necessary, but you might want to assign each card & suit an enum value. I didn’t actually do this, but if you don’t understand what’s going on here, it might help!

Generating Gold Plated Cards (http://share.linqpad.net/5usvcx.linq)

enum Suit { Hearts, Clubs, Diamonds, Spades }

enum Card { Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Jack, Queen, King, Ace }

void Main()
{
    var query = 
        from i in Enumerable.Range(0,52)
        let suit = (Suit)(i / 13)
        let card = (Card)(i % 13)    
        select new { card, suit };
    
    query.Dump();
}

OK, now that we have a deck of cards, let’s see how we can generate all possible 5 card hands. This is probably the crux of the puzzle & it is a little bit tricky: ordering is not important with a hand of cards & in addition to this, we’re “sampling with out replacement”; a card can only appear in a hand once.

First step is to decide on a method name, I’m going with GetAllHands.

Next we should nail down the interface (I’ve opted for a recursive solution). Remember our deck of cards will be represented as a sequence of integers, so our method will need to accept an IEnumerable<int>. Likewise, each hand can also be represented in this manner (as a sequence of integers) except this method will generate all possible (many) hands, so we can return an IEnumerable<IEnumerable<int>>.

Method Signature

IEnumerable<IEnumerable<int>> GetAllHands(IEnumerable<int> deck)

The only thing I’d like to add here, is a parameter that tells our function the size of the hand. This is important as my recursive approach will need this and we might want to generate all possible 2 card hands later (Texas hold’em).

IEnumerable<IEnumerable<int>> GetAllHands(IEnumerable<int> deck, int handSize)

With these types of problems, I generally find it easiest to work on the non-recursive (first level of depth) solution first. Imagine we just need to return all possible 1 card hands.

Generate All One Card Hands (http://share.linqpad.net/ebh299.linq)

void Main()
{
    var deck = Enumerable.Range(0,52);
    GetAllHands(deck,1).Dump();
}

IEnumerable<IEnumerable<int>> GetAllHands(IEnumerable<int> deck, int handSize)
{
    foreach(var card in deck)
    {
        if(handSize == 1) yield return new[]{card};
    }
}

Easy right? OK, it’s now time to add a sprinkling of recursion! For two card hands, we just need to call our function again, and concatenate the hands together.

Adding Recursion (http://share.linqpad.net/fii9wv.linq)

IEnumerable<IEnumerable<int>> GetAllHands(IEnumerable<int> deck, int handSize)
{
    foreach(var card in deck)
    {
        if(handSize == 1) yield return new[]{card};
        else foreach(var hand in GetAllHands(deck, handSize-1))
            yield return new[]{card}.Concat(hand);
    }
}

Looking at our output, there are two problems.

1. We are producing the same hand in different orders: {1,0} & {0,1}
2. We are sampling with replacement, we can’t have the same card in the hand twice: {0, 0}

To solve this problem, we just need to remove a card from the deck once we’ve generated all the hands it’s involved in.

Killing Two Birds With One Stone (http://share.linqpad.net/futqdc.linq)

IEnumerable<IEnumerable<int>> GetAllHands(IEnumerable<int> deck, int handSize)
{
    var count = 0;
    foreach(var card in deck)
    {
        if(handSize == 1) yield return new[]{card};
        else foreach(var hand in GetAllHands(deck.Skip(++count), handSize-1))
            yield return new[]{card}.Concat(hand);
    }
}

OK, so now this is where this solution really comes into its own. Not only can we compute how many 5 card hands there are, we have a sequence of all 2598960 hands meaning we can query it with LINQ!

If we think back to the puzzle that started all this, we’re interested in finding all the hands that contain at least one card from each suit. We can filter out any hand that doesn’t meet this criteria with a simple where clause!

The Solution (http://share.linqpad.net/u9q7aq.linq)

from hand in GetAllHands(deck, 5)
let suits = hand.Select(x => (Suit)(x / 13))
where suits.Contains(Suit.Hearts)
where suits.Contains(Suit.Clubs)
where suits.Contains(Suit.Diamonds)
where suits.Contains(Suit.Spades)
select hand

What’s interesting is how easy it is to adapt this to other poker hands. Here are some examples:

All Flushes (http://share.linqpad.net/349fer.linq)

from hand in GetAllHands(deck, 5)
let suits = hand.Select(x => (Suit)(x / 13))
where suits.All(x => x == Suit.Hearts)
    || suits.All(x => x == Suit.Clubs)
    || suits.All(x => x == Suit.Diamonds)
    || suits.All(x => x == Suit.Spades)
select hand

PS. When verifying this answer I found some poker websites incorrectly compute this one! They should have used LINQPad.

Three Fours (http://share.linqpad.net/n63fsf.linq)

from hand in GetAllHands(deck, 5)
let cards = hand.Select(x => (Card)(x % 13))
where cards.Count(x => x == Card.Four) == 3
select hand

Pretty cool huh?! I think that just about wraps it up: Another puzzle solved in C#!

Stay tuned for an interesting alternative solution.