Poker: a programming problem
By Laurent Le Brun on Sunday, October 5 2008, 18:59 - [EN] F# articles - Permalink
A programming problem: how to evaluate Texas Hold 'Em hands (7 cards), find the winner and print the results?
Today, Brian wrote a blog post about a programming problem: the goal is to evaluate Texas Hold 'Em hands (7 cards), find the winner and print the results. This problem actually comes from the Ruby Quiz #24.
As it was raining, I wanted to solve this problem, and compare my F# code with Ruby solutions. I didn't do much test, but it seems to work quite well, and it seems to be shorter than Ruby programs I've seen. I'm a bit lazy and I won't explain everything. Here the full code (about 100 lines):
[fsharp] #light let face_value = function | 'A' -> 14 | 'K' -> 13 | 'Q' -> 12 | 'J' -> 11 | 'T' -> 10 | c -> int c - int '0' type Card = Card of int * char with static member Create (str: string) = Card (face_value str.[0], str.[1]) interface System.IComparable with member x.CompareTo(y) = match x, (y :?> Card) with | Card (v1,_), Card (v2,_) -> compare v1 v2 let value (Card (v,_)) = v let suit (Card (_,s)) = s type Ranking = | High of int list | Pair of int * int list | TwoPair of int * int * int | Three of int * int list | Straight of int list | Flush of int list | FullHouse of int * int | Four of int * int | StraightFlush of int list | RoyalFlush with override x.ToString() = match x with | RoyalFlush _ -> "Royal Flush" | StraightFlush _ -> "Straight Flush" | Four _ -> "Four of a Kind" | FullHouse _ -> "Full House" | Flush _ -> "Flush" | Straight _ -> "Straight" | Three _ -> "Three of a Kind" | TwoPair _ -> "Two Pair" | Pair _ -> "Pair" | High _ -> "High Card" let group_values h = [for v, l in Seq.group_by value h -> v, Seq.length l] |> List.sort_by (fun (v, l) -> l, v) |> List.rev let test_same h = match group_values h with | (n, 4) :: l -> Four (n, fst l.[0]) | (n, 3) :: (n2, 2) :: _ -> FullHouse (n, n2) | (n, 3) :: l -> Three (n, [fst l.[0]; fst l.[1]]) | (n, 2) :: (n2, 2) :: l -> TwoPair (n, n2, fst l.[0]) | (n, 2) :: l -> Pair (n, l |> Seq.take 3 |> Seq.to_list |> List.map fst) | l -> High (l |> Seq.take 5 |> Seq.to_list |> List.map fst) let test_sequence = Seq.map value >> Seq.distinct >> Seq.sort_by (~-) >> Seq.windowed 5 >> Seq.tryfind (fun s -> s = [|s.[0] .. -1 .. s.[0]-4|]) let get_highest n = Seq.map value >> Seq.sort_by (~-) >> Seq.take 5 >> Seq.to_list let test_various h = Seq.group_by suit h |> Seq.filter (fun (_,l) -> Seq.length l >= 5) |> Seq.to_list |> function | [_, cards] -> match test_sequence cards with | Some l when l.[0] = 14 -> RoyalFlush | Some l -> StraightFlush (Seq.to_list l) | None -> Flush (cards |> get_highest 5) | _ -> match test_sequence h with | Some l -> Straight (Seq.to_list l) | _ -> High [] let rank_hand h = if List.length h < 7 then High [] else max (test_various h) (test_same h) let play input = let convert (line: string) = [for i in line.Split([|' '|]) -> Card.Create i] let ranks = List.map (convert >> rank_hand) input let best = List.max ranks for line, r in List.zip input ranks do printf "%s" line if r <> High [] then printf " %O" r if r = best then printf " (winner)" printfn ""
To test in interactive mode, just call the play function:
[fsharp] play ["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" "7s Ts Ks Kd 9d"]
One thing I loved is the automatic implementation of comparators: to compare two Ranking types, F# uses the declaration order. That is, a RoyalFlush is greater than a Flush, a Flush with an ace is greater than a Flush with a king, and so on. I didn't write any line of code for this, this is quite magical (it's a difference with OCaml)!
My solution doesn't have any side-effect, everything is functional. I was very happy with the Seq.windowed and Seq.group_by functions; I don't use them often, but they are quite nice. If there's something you don't understand, feel free to ask, I can explain. Just one thing: Seq.sort (~-) is used to sort in reverse order.
Comments
Nice! You are pre-empting and besting some of my own ideas, so I may have to steal from you in future blog entries. :)
Very nicely done! One case you didn't handle is an Ace-low straight, which might be handled as follows:
let test_sequence =
let append_ace h =
match Seq.tryfind (fun s -> s = 14) h with
| Some _ -> Seq.append h [|1|]
| None -> h
Seq.map value
>> Seq.distinct
>> append_ace
>> Seq.sort_by (~-)
>> Seq.windowed 5
>> Seq.tryfind (fun s -> s = [|s.[0] .. -1 .. s.[0]-4|])
And a test hand:
play ["Ah 2h 4h 5d 6c 3h 5h"]
There's probably a more elegant way to handle it, but that's what came to mind.
Cheers ~
Keith
Also found a border case on the off chance the player has two sets of three:
| (n, 3) :: (n2, 2) :: _ -> FullHouse (n, n2)
Should be something like:
| (n, 3) :: (n2, c) :: _ when c >= 2 -> FullHouse (n, n2)
Thanks! You're right. :)