Poker: a programming problem

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

1. On Sunday, October 5 2008, 22:11 by Brian

Nice! You are pre-empting and besting some of my own ideas, so I may have to steal from you in future blog entries. :)

2. On Sunday, October 12 2008, 02:13 by Keith Dahlby

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

3. On Sunday, October 12 2008, 02:40 by Keith Dahlby

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)

4. On Sunday, October 12 2008, 12:02 by Laurent Le Brun

Thanks! You're right. :)