Inside F#

Brian's thoughts on F# and .NET

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 |> List.map 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 |> List.map snd |> AllSame
    let theWheel = [ 2; 3; 4; 5; 14 ]
    let isStraight = 
        sorted = theWheel // since Ace is valued 14, this is a special case
        || (sorted |> List.map (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]
    else
        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 |> Array.map (fun s ->
    let cards = s.Split([|‘ ‘|], System.StringSplitOptions.RemoveEmptyEntries)
                |> Array.map MakeCard |> List.ofArray 
    if cards.Length < 7 then Nothing [] else Evaluate (BestHand cards)
)
let bestVal = vals |> Array.max 
Array.zip 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 |> List.map (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".

Advertisements

One Response to “A programming problem, part four (bet the river!)”

  1. Michael said

    Hey, just wanted to mention that I loved this series. Was a great exercise, and seeing how someone smart did it was quite useful. Thanks!

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: