I have been experimenting with F# for a couple of years now, occasionally solving problems from Project Euler but have never got around to posting a blog entry on this subject. Recently I have been lucky enough to spend some time with Don Syme and the people of the excellent F#unctional Londoners user group, a number of whom complained that I don’t have an F# blog, so I thought I had better put my money where my mouth is and put a post together.
F# is a functional programming language based on OCaml which combines the best of both worlds in terms of the pure functional aspects of ML and pragmatic use of imperative / object oriented language features. F# is now a first class member of the .NET languages and is part of Visual Studio 2010.
If you are new to F#, my recommended training list is as follows:
- Firstly, get a taster by following Don’s excellent introductory series on Channel 9.
- After that, learn what functional programming is all about in Real World Functional Programming by Tomas Petricek and Jon Skeet.
- Finally, read Expert F# 2.0 by Don Syme himself, Adam Granicz and Antonio Cisternino which does what it says on the cover.
There are also a number of (proper) blogs on F#, such as Don’s (linked above), Tomas Petricek, Robert Pickering, Luca Bolognese and Phillip Trelford.
What’s it all About?
I have already worked through over 50 of the puzzles in Project Euler, most of which I solved using F#. This is a fantastic way to improve both your F# and your maths skills (by the way several people have told me they don’t do Project Euler because their F#/maths skills aren’t good enough – if you think this, you have got it backwards, you will improve both as you work your way through).
Regarding Project Euler – if you have come to this post simply to find the solution, then I feel sorry for you, you have missed the point. I would really recommend that you have a good stab at the solution yourself before reading any further. The sense of achievement as you increment that score one by one is strangely addictive, and if you just copy the work of others, you miss out on all of that.
That said, this post will take you through my solution for Euler 54, which (somewhat unusually) isn’t a particularly mathematical problem, but turns out to be a great way to demonstrate some of the features of the F# language. The basic principle of this problem is to compare two hands of cards in the game of poker, and to determine which is the winning hand.
Representing the Cards
The first step is to come up with a representation for the playing cards themselves, as well as some functions for parsing from a plain text description (which is what the Euler problem provides) and for evaluating individual cards. The representation here uses discriminated unions, and is similar to that shown in chapter 3 of Programming F# by Chris Smith.
type Suit =<br> | Hearts<br> | Diamonds<br> | Clubs<br> | Spades<br><br>type Card =<br> | Ace of Suit<br> | King of Suit<br> | Queen of Suit<br> | Jack of Suit<br> | Value of int * Suit<br>
These two discriminated unions allow us to represent any of the cards found in a deck of playing cards, eg Ace(Spades) or Value(2,Hearts). Next we need a function to take the string representation of a card (such as “AS”, “2H”, “TC”) and return a value of the relevant discriminated union.
let parseCard (s:string) =<br> let parseSuit (c:char) =<br> match c with<br> | 'H' -> Hearts<br> | 'D' -> Diamonds<br> | 'C' -> Clubs<br> | 'S' -> Spades<br> | _ -> failwith "Unknown suit"<br> let charVal (c:char) = int(c)-48<br> if s.Length <> 2 then failwith "Card should be 2 characters in length"<br> let suit = parseSuit s.<br> match s. with<br> | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' -> Value(charVal(s.),suit)<br> | 'T' -> Value(10,suit)<br> | 'J' -> Jack(suit)<br> | 'Q' -> Queen(suit)<br> | 'K' -> King(suit)<br> | 'A' -> Ace(suit)<br> | _ -> failwith "Unknown rank"<br>
Talking through this routine, you can see we have a helper function (which is local in scope to the function itself) called parseSuit which takes a single character and attempts to parse this into a suit by using a pattern matching expression. Within the main body of the routine we ensure that the string is 2 characters, no more, no less, get the suit, and then finally pattern match the rank of the card. For the numeric characters we use the tried and tested technique of subtracting the ASCII value of ’0′ in order to convert the char into a numeric value.
Playing with these functions in the enormously useful F# Interactive REPL window, we can check they work as expected:
> parseCard "KS";;<br>val it : Card = King Spades<br>> parseCard "3D";;<br>val it : Card = Value (3,Diamonds)<br>> parseCard "ZD";;<br>System.Exception: Unknown rank<br>at FSI_0008.parseCard(String s) in C:\Svn\roundthecampfire\trunk\ProjectEuler\EulerHost\Euler54.fs:line 46<br>at <StartupCode$FSI_0011>.$FSI_0011.main@()<br>Stopped due to error
And to conclude this section, lets create a function to load the two hands (as a tuple) from a single line of 10 cards as per the supplied poker.txt file, and then try that function on a couple of lines from the file.
let parseHands (sl:string) =<br> let parts = sl.Split(' ')<br> if parts.Length <> 10 then failwith "Hands must be 10 cards"<br> else<br> let comb = parts |> Array.map parseCard<br> (Array.sub comb 0 5 |> List.ofArray),(Array.sub comb 5 5 |> List.ofArray)<br>
This is our first use of some of the really cool F# higher order functions, such as Array.map and List.ofArray, as well as the forward pipe |> operator. Essentially this function gets an array of the individual 2 char strings, and projects these using Array.map and parseCard into a set of 10 cards. These cards are then split into two hands of 5 cards using Array.sub.
> parseHands "8C TS KC 9H 4S 7D 2S 5D 3S AC";;<br>val it : Card list * Card list =<br>([Value (8,Clubs); Value (10,Spades); King Clubs; Value (9,Hearts);<br> Value (4,Spades)],<br>[Value (7,Diamonds); Value (2,Spades); Value (5,Diamonds); Value (3,Spades);<br> Ace Clubs])<br>> parseHands "5C AD 5D AC 9C 7C 5H 8D TD KS";;<br>val it : Card list * Card list =<br>([Value (5,Clubs); Ace Diamonds; Value (5,Diamonds); Ace Clubs;<br> Value (9,Clubs)],<br>[Value (7,Clubs); Value (5,Hearts); Value (8,Diamonds); Value (10,Diamonds);<br> King Spades])
Functions to Determine the Rank of a Hand
Now that we have our hands of cards, we need a way to determine the highest rank to which a hand belongs, and giving us enough data to be able to compare two hands of the same rank, by checking the highest card which is part of the rank (e.g. a two pairs of Ace,Ace and 9,9 is higher than two pairs of King,Kind and 10,10) or highest cards which aren’t part of the rank (e.g. pair of Kings with Ace high is better than pair of Kings with Jack high).
Before we do this, we need a function to return the relative value of cards as per 2,3,4,5,6,7,8,9,T,J,Q,K,A and a function which returns just the suit for a given card (so we can check for flushes).
let valueOf (c:Card) =<br> match c with<br> | Ace(_) -> 12<br> | King(_) -> 11<br> | Queen(_) -> 10<br> | Jack(_) -> 9<br> | Value(n,_) -> n - 2<br><br>let suitOf (c:Card) =<br> match c with<br> | Ace(s) | King(s) | Queen(s) | Jack(s) | Value(_,s) -> s<br>
As you can see, valueOf means nothing in terms of any card game, but allows us to easily see that valueOf(Value(9,Spades)) < valueOf(King(Clubs)) for example.
Now it gets tricky, bear with me through this, hopefully this para and following examples will clarify. I decided to come up with a standard type for each rank matching function. Each function needs to take a list of cards as its input, returning firstly true or false to indicate whether the hand matches that rank, but also returning two arrays of card values each in descending order – the first array is the values which are part of the rank (eg for two pairs, 9s and Aces, the array would be [| 12; 7 |]); and the second array is any cards which remain that are not in the rank (eg for a hand 9H 9C AS TD 2C this matches a pair of 9s with remaining array of [| 12; 8; 0 |]).
So the type of these functions is Card list -> bool * int  * int  – we can use this to build a list of the ranking functions from highest (a royal flush) to the lowest (single card high), allowing us to try each in turn until one or both hands matches, and thus compare the hands. First I will define a few more helper functions that we will use in the ranking functions:
let desc n = -n<br><br>let allSameSuit (hand:Card list) =<br> (hand |> Seq.map suitOf |> Seq.distinct |> Seq.length) = 1<br>
The desc function is used for Seq.sortBy to reverse the order of an integer based sequence simply by negating the input, and allSameSuit is a predicate to determine when all the cards in a given hand belong to just one suit.
The lowest rank is X-High, meaning that the hand only contains single cards, and when comparing two hands of this rank, we compare card by card, until one hand has the higher card. Therefore any hand (which doesn’t match a higher rank) will match this rank, and all cards in the hand are included in the rank, so appear in the first array, the second array being empty (as there are no remaining cards after those which belong to the rank are removed).
let matchHighCard (hand:Card list) : (bool*int *int ) =<br> true, (hand |> Seq.map valueOf |> Seq.sortBy desc |> Array.ofSeq), [||]<br>
So the implementation is pretty simple, true, followed by the card values in descending order.
The next example is for two pairs. Here we have two sets of two cards which are in the rank, and a single remaining card.
let matchTwoPairs (hand:Card list) : (bool*int *int ) =<br> let matches =<br> hand |> Seq.map valueOf |> Seq.groupBy (fun n -> n)<br> |> Seq.map (fun (n,s) -> n,(Seq.length s))<br> |> Seq.sortBy (fun (_,l) -> -l) |> Array.ofSeq<br> if (Seq.length matches) <> 3 || (matches. |> snd) <> 2 || (matches. |> snd) <> 2 then false,[||],[||]<br> else true,([| fst(matches.); fst(matches.) |] |> Array.sortBy desc),[| fst(matches.) |]<br>
This is one of the more complex implementations. We firstly get the card values and group by those values. Seq.groupBy gives us a sequence of tuples, the first value being the card value itself, the second is itself a sequence of each matching value (which is a bit nugatory in this case, as these are just sequences of the same value, hence in the following Seq.map we collapse these into just the number of occurrences). At this point we sort by the sequence length descending (using a custom lambda here as we are dealing with tuple values) and convert to an array for ease of indexing.
You probably need to see an example now. If the original hand was something like “9S JC 2D 2H JS”, we get a value sequence of seq [ 7; 9; 0; 0; 9 ]. Following all our mappings we are left with an array of tuples [| (9,2); (0,2); (7,1) |].
Now we can check this array to see if it represents two pairs. It must have three elements, and the first two elements must represent pairs (the snd function gets the second value from the tuple, which is the number of occurrences of the given value). If these do not match, this isn’t a rank of Two Pairs, so we return false and empty arrays.
If this is a match, we return true, with an array of two values (the highest of the pairs, then the lowest of the pairs), and finally the single remaining card value.
This is the last of my examples. A straight flush means the cards are all consecutive values, starting at any value, and they are all of the same suit.
let matchStraightFlush (hand:Card list) : (bool*int *int ) =<br> let values = hand |> List.map valueOf |> List.sort |> Seq.distinct |> Array.ofSeq<br> if (Array.length values) <> 5 || (values. - values.) <> 4 || not (allSameSuit hand) then false,[||],[||]<br> else true, [|values.|], [||]<br>
First we get the values, sort and remove duplicates (if there are dups, it can’t be a straight – we check for this next). So now, if we don’t have 5 cards, this isn’t a match, or if the highest value – lowest value is not 4, then they are not consecutive, so not a match, or if they are not all the same suit, it isn’t a match.
Where we have a match, the value of the highest card in the straight is returned.
Comparing the Hands
Lets define a utility function first. This takes two arrays, comparing item by item until a difference is found, returning negative to indicate the first array is greater, positive if the second array is greater, 0 if they are equal. We will use this to compare cards when two hands are of the same rank.
let compArrays (a:int , b:int ) =<br> if Array.length(a) <> Array.length(b) then failwith "Array lengths differ"<br> let rec innerCompArrays (a:int , b:int ,n) =<br> if n = Array.length(a) then 0<br> else<br> if a.[n] <> b.[n] then b.[n] - a.[n]<br> else innerCompArrays(a,b,(n+1))<br> innerCompArrays(a,b,0)<br>
Note the array lengths must be equal, and we assume they are both in the same order. We use a simple recursive function to step through item by item until the end of the array is reached, or a difference is found.
Now we can define our ordered list of match functions (note there are more than shown above, other implementations left as an exercise for the reader):
let matchFuncs =<br> [ matchRoyalFlush<br> matchStraightFlush<br> matchFourOfAKind<br> matchFullHouse<br> matchFlush<br> matchStraight<br> matchThreeOfAKind<br> matchTwoPairs<br> matchAPair<br> matchHighCard<br> ]<br>
We finally have everything we need to do the comparison of two poker hands. We can bring this all together in a single function which itself iterates over the above list of functions until a match is found for one or both hands, then, if needed, comparing the cards in the hand and then remaining cards to find a winner:
type matchFunc = (Card list) -> (bool * int  * int )<br><br>let compareHands (hands:string) =<br> let rec innerCompareHands (handA:Card list, handB:Card list, funcs:matchFunc list) =<br> match funcs with<br> |  -> failwith "No Winning Hand!"<br> | f::tail -><br> let mtchA,incA,remainA = f(handA)<br> let mtchB,incB,remainB = f(handB)<br> match mtchA,mtchB with<br> | true,false -> 1<br> | false,true -> -1<br> | true,true -><br> let c = compare incA incB<br> if c <> 0 then c<br> else compare remainA remainB<br> | false,false -><br> innerCompareHands (handA,handB,tail)<br> let handA, handB = parseHands(hands)<br> if innerCompareHands (handA, handB, matchFuncs) > 0 then 1 else 2<br>
UPDATE: Realised that the compArrays function was redundant, as the F# compare function works as well with lists and arrays as it does with simpler values. Updated the above accordingly.
Here we parse the string containing the two hands into the separate hands, then iterate over this using the inner recursive function. We work through each function in the list, testing both hands, then the inner pattern match checks the two match results side by side to find an outright winner (false,true or true,false) a draw (true,true) in which case we compare first the cards in the matching rank, then the remaining cards if still a draw. If there are no matches for this function, we move to the next rank and test for that. Note that the check for no remaining functions isn’t ever going to be exercised as matchHighCard will always match. The final result indicates a win for player 1 or player 2
> compareHands "JH 2D 3S JC AS 7D 3C AH 7C 7S";;<br>val it : int = 2<br>> compareHands "TS JS QS KS AS 7D 3C AH 7C 7S";;<br>val it : int = 1
We can see this works fine – in the first example the second hand (three 7s) beats the first (pair of Jacks), and in the second example, the first hand wins as it is a Royal Flush.
We can see that F# code really lends itself to breaking down a problem like this. We use discriminated unions to represent our model very succinctly. We use pattern matching for parsing and checking card values, we use higher order functions on sequences and arrays to concisely compose our rank matching functions, and we use an array of these functions just as easily as any other data type to build our final comparison routine.
With some work, I could probably make this even more succinct, maybe by using active patterns to replace the recursion over the array of functions with a pattern matching expression instead, but hopefully the above demonstrates that a “good enough” solution has been achieved. In case you are interested, the final result is calculated in 188ms, including reading the file.