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 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:
| 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.
// 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
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
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
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:
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:
(match s. with
| ‘T’ -> 10 | ‘J’ -> 11 | ‘Q’ -> 12 | ‘K’ -> 13 | ‘A’ -> 14
| digit -> int digit – int ‘0’), s.
Finally, the main algorithm:
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.)
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:
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:
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.
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.
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".