Inside F#

Brian's thoughts on F# and .NET

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)
    else
        match l with
        | [] -> [] // no solution (n > list length)
        | h :: t ->
            let doPickH = ChooseN t (n-1) |> List.map (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 |> List.map (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)
                |> Array.map 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 |> Array.map 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 |> Array.map (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 |> List.map (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.

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: