Inside F#

Brian's thoughts on F# and .NET

Archive for October, 2008

An oldie but a goodie…

Posted by Brian on October 17, 2008

What does the following F# program do?  Why not run it and find out?

open System
let nl = new String([|char 13;char 10|])
let quote = char 34
let Quote (s:String) = s.Replace(new String([|quote|]), new String([|char 92; quote|]))
let Quine s =
    String.Format("let s = {0}{1}{2}{3}printf {4}%s%s{5} s (Quine s){6}"
        [| box quote; box (Quote s); box quote; box nl; box quote; box quote; box nl|])
let s = "open System
let nl = new String([|char 13;char 10|])
let quote = char 34
let Quote (s:String) = s.Replace(new String([|quote|]), new String([|char 92; quote|]))
let Quine s =
    String.Format(\"let s = {0}{1}{2}{3}printf {4}%s%s{5} s (Quine s){6}\", 
        [| box quote; box (Quote s); box quote; box nl; box quote; box quote; box nl|])
printf "%s%s" s (Quine s)

Posted in Uncategorized | 2 Comments »

A programming problem, part four (bet the river!)

Posted by Brian on October 16, 2008

Last time I finished the "software engineer" solution and briefly discussed some aspects of that strategy.  In this blog entry, I’ll show the "hacker" solution, and draw comparisons between the two strategies.  This final installment of the series is by far the most interesting!

A "hacker" solution

To start things off, I’ll use the implicit representations suggested here:

//type Card = int * char  // rank (ace=14), suit
//type Hand = Card list

That is, an int-char tuple will be used to represent Cards, and a list of those will represent Hands.  I could define these as type aliases in F#, but due to type inference I never actually need type annotations for these, so I don’t bother defining them.

I define a HandValuation type similar to previous solution.  The automatic lexicographical ordering is something a "hacker" wants to leverage.  The difference is that this time, I use lists of ranks rather than fixed numbers of them for each case:

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

The advantage of e.g. "int list" over "int * int * int" is brevity, both at the definition point and some points of use.  The disadvantage is that it’s possible to accidentally create a list with an unintended number of entries.

I wrote the Evaluate function using the same logic, so it’s extremely similar to the other solution.  I could have gone a different way, but doing so would not have illustrated any new points I wanted to discuss in this blog series, so I kept things similar for simplicity.  (If you want to see a different strategy for Evaluate, check out Laurent’s solution.)  Note that since ranks are now just "int"s, the code for "isStraight" got a bit simpler, since there’s no more converting to/from enums.

let Evaluate cards =
    // ranks in ascending sorted order, so r1 is lowest and r5 is highest
    let [ r1; r2; r3; r4; r5 ] as sorted = cards |> fst |> 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 = cards |> snd |> AllSame
    let theWheel = [ 2; 3; 4; 5; 14 ]
    let isStraight = 
        sorted = theWheel // since Ace is valued 14, this is a special case
        || (sorted |> (fun x -> x – r1)) = [ 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]
        Nothing [r5;r4;r3;r2;r1]

The code for ChooseN is exactly the same as the previous solution, so I don’t reproduce it here.  The same is true of ValToString.

BestHand is quite simplified in this version:

let BestHand sevenCards = ChooseN sevenCards 5 |> List.maxBy Evaluate

I’ll talk about BestHand a great deal more in the discussion section below, as this one function highlights a number of differences between the two coding strategies.

Thanks to a lack of error-handling and no enums to provoke extra type conversions, the code for MakeCard can be short:

let MakeCard (s:string)
    (match s.[0] with
     | ‘T’ -> 10 | ‘J’ -> 11 | ‘Q’ -> 12 | ‘K’ -> 13 | ‘A’ -> 14
     | digit -> int digit – int ‘0’), s.[1]

Finally, the main algorithm:

let lines = fileContents.Split([|"\r\n"|], System.StringSplitOptions.RemoveEmptyEntries)
let vals = lines |> (fun s ->
    let cards = s.Split([|‘ ‘|], System.StringSplitOptions.RemoveEmptyEntries)
                |> MakeCard |> List.ofArray 
    if cards.Length < 7 then Nothing [] else Evaluate (BestHand cards)
let bestVal = vals |> Array.max lines vals |> Array.iter (fun (s,v) ->
    match v with
    | Nothing [] -> printfn "%s" s
    | _ -> printfn "%s %s %s" s (ValToString v) (if v = bestVal then "(winner)" else "")

What was previously separate "ParseFile" and "MakePlayer" functions has now just been written inline at the call-sites.  Whereas previously a separate data type ("Folded") represented folded hands and an option ("None") represented the valuation of folded hands, now folded hands are just a list of cards whose length is less than 7, and their valuation is represented with the otherwise meaningless HandValuation "Nothing []".  (The more flexible valuation representation lets us store uninteresting values using a representation within the domain of the type, whereas in the previous solution we needed a separate type (the None option) to deal with the valuation of folded hands.)

That’s it!

Comparison of the "hacker" solution with "software engineer"

True to form, the "hacker" solution is shorter than "software engineer".  This one comes in at about 110 lines, compared to about 180 for the other solution (ignoring unit tests).

What are the main trade-offs between the two solutions?  A deep look at the "BestHand" function is terrifically interesting, as it hosts most of the differences in microcosm.  Here once again is the "software engineer" solution:

// BestHand: Card -> Card -> Card -> Card -> Card -> Card -> Card -> Hand
let BestHand c1 c2 c3 c4 c5 c6 c7 =
    let allSetsOf5Cards = ChooseN [c1; c2; c3; c4; c5; c6; c7] 5
    let allHands = allSetsOf5Cards |> (fun [c1;c2;c3;c4;c5] -> Hand(c1,c2,c3,c4,c5))
    allHands |> List.maxBy Evaluate

and here again is the "hacker" solution:

// BestHand: (int * ‘a) list -> (int * ‘a) list
let BestHand sevenCards = ChooseN sevenCards 5 |> List.maxBy Evaluate

I’ve added the inferred type signatures in comments.  The type signature of the first version enforces a variety of constraints: there are seven cards coming in, five cards going out (recall, a "Hand" was exactly five Cards), and each Card is a Rank and a Suit.  Now consider the second version.  Here there are no constraints to the number of elements in or out, and the data is a tuple of an int (intended to represent the rank) and any other type (the suit).  The reason the "suit" became generic is that the only thing that could impose a constraint on the second part of the tuple was Evaluate, and all it does for suits is check if they are all the same value (the poker "flush" check), which works for any data type.  So the "hacker" solution admits a host of potential run-time errors (such as passing in a zero-element list) ruled out by the "software engineer" solution, but also implements a "wider" solution than is necessary to meet the problem spec, but is potentially useful (the "hacker" code can compute the best hand from eight cards, or nine cards, etc.).  So the "software engineer" solution leverages the type system to rule out some incorrect or meaningless programs; whereas the "hacker" solution picks up some potentially useful extra behavior.

Another advantage to the "software engineer" solution is that the type is self-documenting.  Read the signature and it’s pretty clear what will happen; with the "hacker" signature, you need more context about the representation to grok what it does.

Another advantage to the "hacker" solution is that it is shorter.  (By a factor of three!)  And the reason is that there is no conversion to and from data structures to mediate the impedance mismatches among various function signatures.  "ChooseN" is a very general function, so of course it takes in a list and returns a list.  In the "software engineer" solution, I’d represented the cards individually, so I had to put the seven cards in a list to call "ChooseN".  And then the result was a list, which meant I had to pick apart that list to get the five cards back out so that I could re-wrap them in my domain-specific type "Hand".  The price I paid for the advantages of the extra static type checks was longer code that will be less performant at run-time due to extra data structure conversions. 

In a sense, this tiny function captures the essence of the ongoing debate between static and dynamic typing.  The programmer can create domain-specific static types to structure the program, convey intent, and rule out a class of errors and behaviors at compile-time, at the price of having to author that structure and mediate structural mismatches at module boundaries.  Or the programmer can choose to compute most everything with just scalars and lists, in which case data flows easily everywhere, resulting in short code, but with the loss of compile-time checks and conveyance of intent.

Both programs yield the correct behavior on well-formed inputs.  What about bad input?  The "hacker" solution has the spirit of "garbage in, garbage out", whereas the "software engineer" solution imposes stricter expectations and yields error diagnostics when those expectations are violated.  Here are a few examples, with commentary.

When passed this illegal hand

Jx Kh Ks Kd Jx 3c 6d

the "software engineer" solution yields a helpful diagnostic

System.Exception: Not a legal card suit: ‘x’

whereas "hacker" accepts this and decides

Jx Kh Ks Kd Jx 3c 6d Full house (winner)

The former solution constrained the set of legal suits when parsing the input, and tries to preserve those constraints by representing suits via enums.  The latter made no check while parsing and represented suits as just ‘char’s, so these "suit" values flow freely through the program logic, sometimes with unexpected results.

This hand

J Kh Ks Kd J 3c 6d

has similar diagnostic results for "software engineer", but for "hacker" yields the more opaque exception

System.IndexOutOfRangeException: Index was outside the bounds of the array.

as it tries to access the second character of the string "J".

Finally this hand (with ‘extra’ cards tacked on the end)

Jh Kh Ks Kd Jd 3c 6d Qd Td Ad

fed to "software engineer" yields this diagnostic

System.Exception: Bad input line ‘Jh Kh Ks Kd Jd 3c 6d Qd Td Ad’

whereas "hacker" says

Jh Kh Ks Kd Jd 3c 6d Qd Td Ad Straight flush (winner)

The hacker behavior is outside the problem specification, but might be useful if we ever need a variation where players have more than just two hole cards in addition to the five community cards.

Notice how all of these behaviors are related to the representational choices (discussed earlier) made by each of the two solutions.

Summing up

I really enjoyed this blog series for a number of reasons:

  • I got to code a solution to a fun problem
  • I got to show off more features of F#
  • I demonstrated how F# can be used as a language for "software engineer" solutions, leveraging the strengths of the type system
  • I demonstrated how F# can be used as a language for "hacker"/scripting solutions, leveraging the succinctness of the language/syntax
  • I discusses the trade-offs in these two different "strategies" for programming

I hope you learned half as much as I did along the way!  Comments welcome!

The source code

The source code for both solutions is available here.  The project named "Poker" is the "software engineer", and "Poker2" is "hacker".

Posted in Uncategorized | 1 Comment »

A programming problem, part three (make the turn!)

Posted by Brian on October 12, 2008

Last time I sketched out two different strategies for solving the poker problem ("software engineer" and "hacker"), and started coding the "software engineer" solution.  In this blog entry, I’ll finish that solution and discuss some characteristics of the strategy.

A "software engineer" solution, part two

Picking up where I left off, the next thing to do is select the best 5 cards from a set of 7 (a player’s two hole cards plus the five common cards on the board).  An algorithm for this is straightforward; I can just enumerate all possible 5-card subsets and then pick the one with the maximum valuation.  Here’s a generic function for choosing "n" elements from a given list:

let rec ChooseN l n =
    if n < 0 then invalidArg "n" "n must be >= 0"
    if n = 0 then
        [ [] ]  // one solution (empty list)
        match l with
        | [] -> [] // no solution (n > list length)
        | h :: t ->
            let doPickH = ChooseN t (n-1) |> (fun res -> h :: res)
            let dontPickH = ChooseN t n
            doPickH @ dontPickH

The logic is straightforward; recurse down the list, and at each step of of the way compute both the solutions that do pick the current list element and those that do not pick the current element.  (This is not a particularly efficient implementation; it allocates a lot of extra lists along the way.)

With the "ChooseN" function in hand, making the best hand from 7 cards is a snap:

let BestHand c1 c2 c3 c4 c5 c6 c7 =
    let allSetsOf5Cards = ChooseN [c1; c2; c3; c4; c5; c6; c7] 5
    let allHands = allSetsOf5Cards |> (fun [c1;c2;c3;c4;c5] -> Hand(c1,c2,c3,c4,c5))
    allHands |> List.maxBy Evaluate

The "max_by" library function selects the list element with the maximum value under a given projection; here it chooses the Hand that has the greatest HandValuation as determined by applying Evaluate to each Hand in the list.

That nearly completes all of the implementation logic for the program.  Most of the remainder is parsing the input and writing the output.  So next up, I need a function to convert strings (like "Kc") into Card objects (like Card(Suit.Club,Rank.King)).

let MakeCard (s:string)
    if s.Length <> 2 then failwith <| sprintf "Not a legal card: ‘%s’" s
    let suits = dict [| ‘c’, Suit.Club; ‘d’, Suit.Diamond; ‘h’, Suit.Heart; ‘s’, Suit.Spade |]
    let ranks = dict [|
         ‘A’, Rank.Ace
         ‘2’, Rank.Two
         ‘3’, Rank.Three
         ‘4’, Rank.Four
         ‘5’, Rank.Five
         ‘6’, Rank.Six
         ‘7’, Rank.Seven
         ‘8’, Rank.Eight
         ‘9’, Rank.Nine
         ‘T’, Rank.Ten
         ‘J’, Rank.Jack
         ‘Q’, Rank.Queen
         ‘K’, Rank.King
    match ranks.TryGetValue s.[0], suits.TryGetValue s.[1] with
    | (false,_),_ -> failwith <| sprintf "Not a legal card rank: ‘%c’" s.[0]
    | _,(false,_) -> failwith <| sprintf "Not a legal card suit: ‘%c’" s.[1]
    | (_,r),(_,s) -> Card(s,r)

The "dict" function in F# takes a sequence of tuples representing key-value pairs as input and returns an IDictionary<_,_>.  This code also takes advantage of the F# feature that turns "out" parameters into result tuples (which Dustin wrote about here).

Looking at the problem spec again, I see I need to read in info on a set of players, and then write it back out with extra information (hand rank and whether the player won) for players that did not fold.  So I chose the following representation for parsing each line of input that represents a player:

type Player =
    | Folded
    | Played of Card * Card * Card * Card * Card * Card * Card
let MakePlayer (s:string) =
    let cards = s.Split([|‘ ‘|], System.StringSplitOptions.RemoveEmptyEntries)
                |> MakeCard
    if cards.Length > 7 then failwith <| sprintf "Bad input line ‘%s’" s
    match cards with
    | [| c1; c2; c3; c4; c5; c6; c7 |] -> s, Played(c1,c2,c3,c4,c5,c6,c7)                
    | _ -> s, Folded

Note that MakePlayer returns a tuple of the input string and the Player; I’m holding on to the input string since I’ll need to write it right back out again in a moment.

Now here’s some sample input as well as code to parse the whole input.

let fileContents = "
Kc 9s Ks Kd 9d 3c 6d
9c Ah Ks Kd 9d 3c 6d
Ac Qc Ks Kd 9d 3c
9h 5s
4d 2d Ks Kd 9d 3c 6d
9h Kh Ks Kd 9d 3c 6d
7s Ts Ks Kd 9d"

let ParseFile (s:string) =
    let lines = s.Split([|"\r\n"|], System.StringSplitOptions.RemoveEmptyEntries)
    lines |> MakePlayer

I need one more function, to print the hand rank in the format suggested by the problem spec:

let ValToString handVal =
    match handVal with
    | Nothing _ -> "Nothing"
    | Pair _ -> "Pair"
    | TwoPair _ -> "Two pair"
    | ThreeOfAKind _ -> "Three of a kind"
    | Straight _ -> "Straight"
    | Flush _ -> "Flush"
    | FullHouse _ -> "Full house"
    | FourOfAKind _ -> "Four of a kind"
    | StraightFlush _ -> "Straight flush"

Finally, my main algorithm, that ties it all together:

let evaledPlayers = ParseFile fileContents |> (fun (s,p) -> 
    s, match p with
       | Played(c1,c2,c3,c4,c5,c6,c7) -> Some(BestHand c1 c2 c3 c4 c5 c6 c7 |> Evaluate)
       | _ -> None
let bestVal = [| for _,v in evaledPlayers do
                     match v with 
                     | None -> ()
                     | Some(x) -> yield x 
              |] |> Array.max 
evaledPlayers |> Array.iter (fun (s,v) ->
    match v with
    | None -> printfn "%s" s
    | Some(v) -> printfn "%s %s %s" s (ValToString v) (if v = bestVal then "(winner)" else "")

First I compute the best hand valuation for each player (as an "option", using "None" for players that folded).  Then I compute the best hand valuation among all the players that did not fold.  Finally I print the output for each player in the desired format.  The whole way through this code the arrays contain tuples whose first element is the input string ("s"), since I need that data as the first part of the output I need to print.

That’s it!

Discussion of the "software engineer" solution

I’ll briefly discuss some aspects of this solution strategy, but save some of the discussion until after posting the "hacker" version of the code for comparison.

The types I created for the domain objects (e.g. Suit, Card, Hand) helps make the code readable as well as reusable.  The structure of the types helps document the intention; for example, the fact that a Hand contains exactly five cards

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

makes clearer some aspects of how the data type will be used (if a Hand instead had held a "Card list", the reader might speculate that it only represents a player’s two hole cards, or all seven cards – hole plus community).  There is little to these types that’s custom-tailored to the problem at hand; I expect I could easily lift these types out of this program and use them advantageously in another poker program as well. 

The data types are explicit; by that I mean choosing to use enums rather than just ints or chars, and creating single-case unions like

type Card = Card of Suit * Rank

rather than just using tuples.  The advantages of these explicit data formats include static type checks enforced by the compiler to prevent misuse as well as making the code and tooling more self-documenting; I’ll demonstrate this in more detail in the next blog entry.  The disadvantages of explicit data formats are that more effort goes into "conversion of data structures" which also impacts succinctness; an example is

let BestHand c1 c2 c3 c4 c5 c6 c7 = 
    let allSetsOf5Cards = ChooseN [c1; c2; c3; c4; c5; c6; c7] 5 
    let allHands = allSetsOf5Cards |> (fun [c1;c2;c3;c4;c5] -> Hand(c1,c2,c3,c4,c5)) 
    allHands |> List.max_by Evaluate

where I needed to pack 7 individual bits of data into a list to hand them off to a function (ChooseN), and then unpack the list back into separate pieces of data to convert it back to one of my data types (Hand).  Once again, I’ll discuss this in more detail after showing the "hacker" style solution for comparison. 

As a matter of course, I did some input checking and validation (though not very much – there’s only a handful of exceptions) to try to make the code more robust to exceptional conditions.  I did so mostly with the intention of providing helpful diagnostics rather than more opaque ones (like IndexOutOfRange or KeyNotFound exceptions), but as I’ll demonstrate next time, this error-checking also provides robustness by helping prevent out-of-spec behavior of the program.

Next time…

In the next blog entry, I’ll show a solution using the "hacker" strategy, and draw more specific comparisons between the two strategies, using code from each solution as concrete examples to illustrate my points.

Posted in Uncategorized | Leave a Comment »

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(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 |> (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
    elif AllSame [r2;r3;r4;r5] then
    elif AllSame [r1;r2;r3] && AllSame[r4;r5] then
    elif AllSame [r1;r2] && AllSame[r3;r4;r5] then
    elif isFlush then
    elif isStraight then
        Straight r5
    elif AllSame[r1;r2;r3] then
    elif AllSame[r2;r3;r4] then
    elif AllSame[r3;r4;r5] then
    elif r1=r2 && r3=r4 then
    elif r1=r2 && r4=r5 then
    elif r2=r3 && r4=r5 then
    elif r1=r2 then
    elif r2=r3 then
    elif r3=r4 then
    elif r4=r5 then

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.

Posted in Uncategorized | Leave a Comment »

A programming problem, part one (place your bets!)

Posted by Brian on October 5, 2008

I was trying to come up with a programming problem to motivate some blog entries, and I found one that I really like.  Ruby Quiz #24 requires you to write a short console application that reads in information about Texas Hold ‘Em poker hands, evaluates the results, and prints out the results.  Follow the link and go check the problem out.

I like this problem because

  • It is simple to read and understand (the spec is a little thin/lax, but the main idea is straightforward and obvious).
  • It is deceptively complex – this is not a program you will knock out in 20 minutes of coding (but please try to prove me wrong!).
  • It can be solved with a few different implementation strategies.
  • It does not require much domain-specific knowledge (just cards and poker – a complete list of what-beats-what is here; unlike the link in the problem, this link includes important tiebreaker information).
  • It is fun!  I used to play No Limit Hold ‘Em a bit, and enjoyed it, but never got good at it (and not for lack of trying).  So for me, there’s a bit of a nostalgia aspect here.

So in the next few blog entries, I will walk through solving this problem.  And here’s the kicker (pun!) – I intend to show you two different ways to do it.  Why?  And what differentiates the two ways?  You’ll find out in due time.  In the meantime, try your own hand (not so much a pun) at the problem, using any language or implementation strategy you like.  That way you’ll have something of your own to compare against the solutions I present.

Get crackin’!

Posted in Uncategorized | Leave a Comment »