Skip to content

Project Euler Problem 54

December 2, 2011

Solving Project Euler Problem 54 really made me to sweat. And, as usual, solution is as good as chosen data presentation is adequate. The latter would be easier to illustrate (zoom in):
P54 data presentation
Each playcard carries a value and a suit. We map each hand of 5 cards as 1s to the matrix Hand of 0s using Hand.[suit, value-1] as mapping function.
Sums of columns of Hand placed into array Suits represent occurences of each suit on hand. As hands are not ranked by suit in poker we only care if the hand is of a same suit, i.e. when Suits.[x] = 5 the hand contains a Flush (ordinary, Straight, or Royal).
Sums of rows of Hand placed into array Values represent occurences of each card value on hand. These can vary from Values.[x]=0 (no cards of value x+1 on hand) to Values.[x]=4 (Four of a Kind of value x+1 on hand). If our hand is initially represented by a sorted by card value array cards.[0]..cards.[4] then Straight would be recognized by cards.[4].Value – cards.[0].Value = 4 and Array.max Values = 1.
Finally, the heart of the solution is an effective ranking that would allow comparing hands in one shot. After long consideration I decided to describe ranks as numbers in positional notation with base 14. Rank Calculator on the left of illustration shows how different hand ranks are represented as parts of a number base 14; overall hand rank is calculated very efficiently by folding Rank Calculator array over subsequent powers of 14. That said, here is the code:

// Poker DOES NOT RANK suits (http://en.wikipedia.org/wiki/High_card_by_suit_(poker)A)
// Tie breaking rules: http://www.pokerhands.com/poker_hand_tie_rules.html 
open System
open System.IO

type Ranks = HighCard = 0 | Pair = 5 | ThreeOfAKind = 7 | Straight = 8
                | Flush = 9 | FourOfAKind = 14 | StraightFlush = 15

type Suit = Spades = 0 | Diamonds = 1 | Clubs  = 2| Hearts = 3

type PlayingCard =
    | Ace of int*Suit | King of int*Suit | Queen of int*Suit | Jack of int*Suit | ValueCard of int*Suit

    static member Parse (code: string) =
        let suit = function
            | 'H' -> Suit.Hearts
            | 'D' -> Suit.Diamonds
            | 'S' -> Suit.Spades
            | 'C' -> Suit.Clubs
            | _ as c -> failwith "Invalid suit code: %s" c
             
        let split = code.ToCharArray()
        if split.Length <> 2 then
            failwith ("Invalid card code: " + code)

        match split.[0] with
        | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' as v -> ValueCard((int)v - (int)'1', suit(split.[1]))
        | 'T' -> ValueCard(9, suit(split.[1]))
        | 'J' -> Jack(10, suit(split.[1]))
        | 'Q' -> Queen(11, suit(split.[1]))
        | 'K' -> King(12, suit(split.[1]))
        | 'A' -> Ace(13, suit(split.[1]))
        | _ -> failwith ("Invalid card code: " + code)

    member __.Value =
        match __ with
        | ValueCard(x,y) | Queen(x,y) | Jack(x,y) | King(x,y) | Ace(x,y) -> x

    member __.Suit =
        match __ with
        | ValueCard(x,y) | Queen(x,y) | Jack(x,y) | King(x,y) | Ace(x,y) -> y

let rank hand =
    let cards = hand |> Array.map PlayingCard.Parse |> Array.sortBy (fun x -> x.Value)
    let handMap: int [,] = Array2D.zeroCreate 4 13
    let suits, values, ranks = (Array.zeroCreate 4), (Array.zeroCreate 13), (Array.zeroCreate 16)

    for card in cards do handMap.[int card.Suit, card.Value - 1] <- 1

    for i in [0..3] do
        for j in [0..12] do
            suits.[i] <- suits.[i] + handMap.[i,j]
            values.[j] <- values.[j] + handMap.[i,j]
    
    if Array.max suits = 5 then // all are the same suit
        if cards.[4].Value - cards.[0].Value = 4 then // ... and consecutive value
            ranks.[int Ranks.StraightFlush] <- cards.[0].Value
        else
            for i in [0..4] do ranks.[int Ranks.Flush + i] <- cards.[i].Value
    elif Array.max values = 1 && cards.[4].Value - cards.[0].Value = 4 then
        ranks.[int Ranks.Straight] <- cards.[0].Value
    else
        let singleIdx = ref (int Ranks.HighCard)
        let pairIdx = ref (int Ranks.Pair)
        for i in [0..12] do
            match values.[i] with
            | 4 -> ranks.[int Ranks.FourOfAKind] <- i + 1
            | 3 -> ranks.[int Ranks.ThreeOfAKind] <- i + 1
            | 2 -> ranks.[!pairIdx] <- i + 1; incr pairIdx
            | 1 -> ranks.[!singleIdx] <- i + 1; incr singleIdx
            | _ -> ()
    
    ranks |> Array.fold (fun (sum, power) x -> (sum + (bigint x)*power, power*14I)) (0I, 1I) |> fst

let readHands (path: string)  =
    seq {
        use reader = new StreamReader(path)
        let (hand1: string[]), (hand2: string[]) = (Array.zeroCreate 5), (Array.zeroCreate 5)
        while not reader.EndOfStream do
            let hands = reader.ReadLine().Split(' ')
            Array.blit hands 0 hand1 0 5; Array.blit hands 5 hand2 0 5
            yield if rank hand1 > rank hand2 then 1 else 0
    }
    
readHands @".\Problem054.data" |> Seq.sum

Once and again I enjoyed the multiparadigm nature of F# allowing to freely mix and match functional, object-oriented, and imperative programming styles. And just another case when a F# solution of a Project Euler problem is right at the first run!.
Although I fully recognize that the solution above it mostly imperative and would definitely revisit this problem to come up with truly functional solution, which I’m positive is possible.

Advertisements

From → Project Euler

Leave a Comment

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: