# Project Euler Problem 54

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):

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.