Inside F#

Brian's thoughts on F# and .NET

Play Ball in F#

Posted by Brian on March 5, 2008

I had recently been checking out the 2008 Winter Scripting Games, and today I read a couple blogs with solutions to the Play Ball problem (go read the problem description – it’s short).  This looked like it should be straightforward in F#, so I coded up my own solution:

open System

let rng = new Random() let shuffle (array : 'a array) = // ' let n = array.Length for x in 1..n do let i = n-x let j = rng.Next(i+1) let tmp = array.[i] array.[i] <- array.[j] array.[j] <- tmp array let teams = [| 'A' .. 'F' |] let n = teams.Length let ans = seq { for i in 0..n-1 do for j in i+1..n-1 do yield (teams.[i],teams.[j]) } |> Array.ofSeq |> shuffle for x in ans do printfn "%A" x

(Sorry about the syntax highlighting – my code-snippet widget just knows C#, so "let"s are not highlighted as keywords and it thinks the generic type variable ‘a starts a character literal.)

The solution has just two main parts.  First, the solution demands the results in random order, so I wrote a quick function to shuffle an array.  This is based on the algorithm I recently read in Programming Pearls.  You walk down the array from index n-1 down to 0, and at each element, you swap it with some random element from 0..current.  This generates a random permutation.

Now we just need the list of pairings.  Each team needs to be paired with every other team exactly once, and this is easily expressed as "nested loops" in a sequence comprehension.  We yield a tuple of values for each matchup, and so the sequence comprehension results in:

('A', 'B')
('A', 'C')
('A', 'D')
('A', 'E')
('A', 'F')
('B', 'C')
('B', 'D')
('B', 'E')
('B', 'F')
('C', 'D')
('C', 'E')
('C', 'F')
('D', 'E')
('D', 'F')
('E', 'F')

We then pipeline that sequence through a couple more functions: first "Array.ofSeq", which converts the sequence to an array; then our "shuffle" function, which shuffles the array (mutating the array in place and returning a reference to the original array object).  Finally we print out the results, and get an answer like

('B', 'F')
('C', 'D')
('B', 'E')
('D', 'F')
('A', 'F')
('D', 'E')
('A', 'D')
('C', 'F')
('B', 'C')
('A', 'C')
('C', 'E')
('A', 'E')
('B', 'D')
('E', 'F')
('A', 'B')

which is what we desire.

Advertisements

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: