Inside F#

Brian's thoughts on F# and .NET

A programming problem, part two (see the flop!)

Posted by Brian on October 11, 2008

Last time I introduced a programming problem.  In this blog entry I’ll talk about two different strategies for solving it, and discuss the first half of the first solution.

Two strategies for solving the problem

The two strategies I will demonstrate in this blog series are what I shall call the "hacker" strategy and the "software engineer" strategy.  These are my own rough characterizations of two different modes of programming that you are probably already familiar with.  The programming problem at hand will provide a venue for demonstrating the differences between these strategies.  Here is my brief synopsis of the two strategies.

  • Hacker.  This strategy emphasizes brevity, finding the shortest distance to coding a solution.  This strategy leverages implicit data formats and pays little attention to exception-handling when it’s not relevant to the problem specification.  This strategy is excellent in timed programming contests, when playing code golf, and when developing scripts that could be rewritten from scratch in an afternoon or less.
  • Software engineer.  This strategy emphasizes readability and maintainability.  This strategy uses explicit data formats, is robust to exceptional cases, and structures code so that it can be easily changed to accommodate specification changes or reused in other contexts.  This strategy is excellent for developing larger bits of code for projects with long maintenance lifetimes and multiple developers.

I’ll take these strategies to a little bit of an extreme to highlight the differences, but in fact there is a continuum between these two.  (Actually, it’s not just a linear continuum; another interesting point in the "strategy space" is one I might label the "functional hacker", which emphasizes succinctness and codes mostly using functional composition in a points-free style.  This strategy shares some strengths and some weakness with each of "hacker" and "software engineer".  Laurent’s solution is in this vicinity.)

I’ll solve the poker problem both ways, so let’s start with…

A "software engineer" solution, part one

After reading the problem specification, it is clear that I need to model the essential entities for representing poker hands and comparing their relative strengths (what-beats-what).  Without paying too much attention to the details of the problem specification, I see the obvious nouns in the domain (card, suit, rank, hand), as well as one less-obvious one (hand valuation, e.g. "two pair, kings and nines, with queen kicker").  So let’s start there.

I can use enums to represent suits and ranks:

type Suit = 
    | Club = 1
    | Diamond = 2
    | Heart = 3
    | Spade = 4
        
type Rank =
    | Two = 2
    | Three = 3
    | Four = 4
    | Five = 5
    | Six = 6
    | Seven = 7
    | Eight = 8
    | Nine = 9
    | Ten = 10
    | Jack = 11
    | Queen = 12
    | King = 13
    | Ace = 14

(In F#, the syntax for enumerated types looks a lot like the syntax for discriminated unions; the "=<intValue>" is the key difference.)  Note that I chose to value an ace as 14 rather than 1, since most poker hands treat aces as high cards.

A card is just a combination of a suit and a rank:

type Card = Card of Suit * Rank

And a hand is just a set of five cards:

type Hand = Hand of Card * Card * Card * Card * Card

There are a number of ways we could choose to represent hand valuations, but in F#, this is one of the best choices:

type HandValuation = 
    | Nothing of Rank * Rank * Rank * Rank * Rank  // descending order
    | Pair of Rank * Rank * Rank * Rank  // pair, then kickers in descending order
    | TwoPair of Rank * Rank * Rank // high pair, low pair, kicker
    | ThreeOfAKind of Rank * Rank * Rank // trips, kickers in descending order
    | Straight of Rank // high card
    | Flush of Rank * Rank * Rank * Rank * Rank // descending order
    | FullHouse of Rank * Rank // three then two
    | FourOfAKind of Rank * Rank // quad, kicker
    | StraightFlush of Rank // high card

Like some other functional languages, F# automatically implements a comparison function for algebraic data types (e.g. lists, tuples, discriminated unions) using a lexicographical ordering.  In other words, you get operators like "<" and "=" for free, with the right semantics.  Witness these example:

assert (TwoPair(Rank.King, Rank.Nine, Rank.Queen) < ThreeOfAKind(Rank.Two, Rank.Four, Rank.Three))
assert (TwoPair(Rank.King, Rank.Nine, Rank.Queen) < TwoPair(Rank.Ace, Rank.Three, Rank.Eight))
assert (TwoPair(Rank.King, Rank.Nine, Rank.Queen) < TwoPair(Rank.King, Rank.Nine, Rank.Ace))

In the first line, TwoPair is less than ThreeOfAKind (TwoPair was listed first in the type declaration), so the ‘<‘ operator can stop evaluating right there.  In the second line, both HandValuations have the same union case (TwoPair), so we start comparing the carried data one piece at a time; King is less than Ace, so we’re done.  In the last line, the cases are the same (TwoPair), and the first two piece of data are the same (King and Nine), so the final datum (Queen versus Ace) is the tiebreaker.  In other words, it’s completely analogous to "dictionary order" for strings, where the union case is the first "letter" of the string and the carried data are the subsequent "letters" in the string.

Thus my HandValuation type is a nice choice because it clearly represents the information both for classifying an individual hand as well as for comparing two hands (what beats what).

With these data types under my belt, I am ready to write the first piece of "real" code for the problem; the hand evaluation logic.  I need a function that takes a Hand as input and computes its HandValuation as a result.  There are a variety of ways to implement this logic; I chose one that is rather plodding, but is straightforward to read and understand.

let Evaluate (Hand(Card(s1,r1),
                   Card(s2,r2),
                   Card(s3,r3),
                   Card(s4,r4),
                   Card(s5,r5))) =
    // redo ranks in ascending sorted order, so r1 is lowest and r5 is highest
    let [r1; r2; r3; r4; r5] as sorted = [r1; r2; r3; r4; r5] |> List.sort
    // handy helper function
    let rec AllSame l = 
        match l with
        | [] | [_] -> true
        | h::(i::_ as t) -> h = i && AllSame t
    // decide up front if hand contains a flush and/or a straight
    let isFlush = AllSame [s1; s2; s3; s4; s5]  
    let theWheel = [Rank.Two; Rank.Three; Rank.Four; Rank.Five; Rank.Ace]
    let isStraight = 
        sorted = theWheel // since Ace is valued 14, this is a special case
        || (sorted |> List.map (fun x -> (int x)(int sorted.Head))) = [0;1;2;3;4]
    // all the tedious logic for classifying the hand
    if isStraight && isFlush then
        StraightFlush r5
    elif AllSame [r1;r2;r3;r4] then
        FourOfAKind(r1,r5)
    elif AllSame [r2;r3;r4;r5] then
        FourOfAKind(r2,r1)
    elif AllSame [r1;r2;r3] && AllSame[r4;r5] then
        FullHouse(r1,r4)
    elif AllSame [r1;r2] && AllSame[r3;r4;r5] then
        FullHouse(r3,r1)        
    elif isFlush then
        Flush(r5,r4,r3,r2,r1)
    elif isStraight then
        Straight r5
    elif AllSame[r1;r2;r3] then
        ThreeOfAKind(r1,r5,r4)
    elif AllSame[r2;r3;r4] then
        ThreeOfAKind(r2,r5,r1)
    elif AllSame[r3;r4;r5] then
        ThreeOfAKind(r3,r2,r1)
    elif r1=r2 && r3=r4 then
        TwoPair(r3,r1,r5)
    elif r1=r2 && r4=r5 then
        TwoPair(r4,r1,r3)
    elif r2=r3 && r4=r5 then
        TwoPair(r4,r2,r1)
    elif r1=r2 then
        Pair(r1,r5,r4,r3)
    elif r2=r3 then
        Pair(r2,r5,r4,r1)
    elif r3=r4 then
        Pair(r3,r5,r2,r1)
    elif r4=r5 then
        Pair(r4,r3,r2,r1)
    else
        Nothing(r5,r4,r3,r2,r1)

Blah.  No matter how you choose to implement the logic, there are a lot of cases and it feels error-prone.  Being a good developer, I wrote some unit tests.  I chose to specify a whole lot of tests mostly declaratively.  First, for convenience, I named all 52 cards in the deck:

let CA = Card(Suit.Club,Rank.Ace)
let CK = Card(Suit.Club,Rank.King)
let CQ = Card(Suit.Club,Rank.Queen)
...

Then I made a big list of hands, starting with the best and evidencing each step of "slightly worse" along the way:

// list of hands in intended order (best to worst)
// each element is itself another list of hands that ‘tie’ with each other
// these will serve as good test cases of ranking logic
let handsInOrder = [
    // straight flush
    [Hand(SA,SK,SQ,SJ,ST); Hand(HA,HK,HQ,HJ,HT)]
    [Hand(S9,S8,S7,S6,S5)] // worse high
    // four of a kind
    [Hand(SA,HA,DA,CA,SQ); Hand(SA,HA,DA,CA,CQ)]
    [Hand(SA,HA,DA,CA,S4)] // worse kicker
    [Hand(SK,HK,DK,CK,SA)] // worse quads
    // full house
    [Hand(SA,HA,DA,S3,H3); Hand(SA,DA,CA,H3,C3)]
    [Hand(SA,HA,CA,D2,H2)] // worse low
    [Hand(SK,HK,CK,DQ,HQ)] // worse high
    // flush
    [Hand(SA,S9,S8,S4,S3); Hand(DA,D9,D8,D4,D3)]
    [Hand(SA,S9,S8,S4,S2)] // worse 5th
    [Hand(SA,S9,S8,S3,S2)] // worse 4th
    [Hand(SA,S9,S6,S5,S2)] // worse 3rd
    [Hand(SA,S8,S7,S6,S5)] // worse 2nd
    [Hand(SK,SQ,SJ,ST,S8)] // worse 1st
    // straight
    [Hand(SA,SK,SQ,SJ,HT); Hand(DA,DK,DQ,DJ,ST)]
    [Hand(DK,HQ,SJ,CT,S9)] // worse high-card
    // three of a kind
    [Hand(SA,HA,DA,DK,SQ); Hand(CA,DA,HA,SK,SQ)]
    [Hand(SA,HA,DA,DK,ST)] // worse 2nd kicker
    [Hand(SA,HA,DA,DQ,DJ)] // worse kicker
    [Hand(S3,H3,D3,SA,DK)] // worse trips
    // two-pair
    [Hand(SA,HA,S3,D3,S9); Hand(CA,HA,C3,S3,H9)]
    [Hand(SA,HA,S3,D3,S7)] // worse kicker
    [Hand(SK,HK,SQ,HQ,S9)] // worse high-pair
    [Hand(SK,HK,SJ,HJ,SA)] // worse low-pair
    // pair
    [Hand(SA,CA,SK,SQ,SJ); Hand(HA,CA,HK,CQ,DJ)]
    [Hand(SA,CA,SK,SQ,S2)] // worse 3rd kicker
    [Hand(SA,CA,SK,SJ,S5)] // worse 2nd kicker
    [Hand(SA,CA,SQ,SJ,ST)] // worse 1st kicker
    [Hand(SK,HK,SA,HJ,C6)] // worse pair
    // nothing
    [Hand(HA,S9,S8,S4,S3); Hand(CA,D9,D8,D4,D3)]
    [Hand(HA,S9,S8,S4,S2)] // worse 5th
    [Hand(HA,S9,S8,S3,S2)] // worse 4th
    [Hand(HA,S9,S6,S5,S2)] // worse 3rd
    [Hand(HA,S8,S7,S6,S5)] // worse 2nd
    [Hand(HK,SQ,SJ,ST,S8)] // worse 1st
    ]

With this data structure, it’s easy to write code that walks the structure and ensures that

  • every hand on the same row ties with the other hands on that row
  • every row beats all the hands below it
  • these are true regardless of the order of the 5 cards in a hand

To implement the last bullet, I want to be able to generate all possible permutations of a hand.  So I’ll start with a function that generates every permutation of an array.  There are lots of ways to write such a function; here is one way that does it with the fewest number of array element swaps:

let AllPermutations s =
    let a = Array.ofSeq s
    let Swap i j =
        let tmp = a.[i]
        a.[i] <- a.[j]
        a.[j] <- tmp
    let p = Array.init (a.Length + 1) (fun x -> x)
    seq {
        yield Array.copy a
        let i = ref 1
        while !i < a.Length do
            p.[!i] <- p.[!i]1
            let j = if !i % 2 = 1 then p.[!i] else 0
            Swap !i j
            yield Array.copy a
            i := 1
            while p.[!i] = 0 do
                p.[!i] <- !i
                i := !i + 1
    }

Now it’s trivial to take a given hand of 5 cards and generate an array of all the hands containing those 5 cards in any order:

let AllHands (Hand(c1,c2,c3,c4,c5)) =
    let a = [| c1; c2; c3; c4; c5 |]
    [| for [| c1; c2; c3; c4; c5 |] in AllPermutations a -> Hand(c1,c2,c3,c4,c5) |]

And now I can test all the bits I want to ensure:

let rec Test handsInOrder =
    match handsInOrder with
    | [] -> ()
    | h::t -> let firstValuation = Evaluate (List.head h)
              for hand in h do
                  for perm in AllHands hand do
                      assert( (Evaluate perm) = firstValuation )
              for lesserHand in List.concat t do
                  assert( firstValuation > (Evaluate lesserHand) )
              Test t
Test handsInOrder

Each recursive call to "Test" tests one row – we ensure that all permutations of all hands on this row tie, and that the valuation of the hands on this row beat all of the lesser hands further down the list.  With these tests, I did in fact find a typo in my original version of "Evaluate"; thanks to the tests, I am confident that "Evaluate" works properly.

Next time…

That’s enough for this blog entry.  Next time I’ll finish off the "software engineer" strategy by adding logic to choose the best hand of 5 cards from 7 cards, parsing the input, and writing the output.  After that, I’ll show the "hacker" strategy, and draw comparisons between the two.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: