Skip to content

Revenge of the Secret Santa Code Kata – F#

17 February 2012

Here’s another solution to the Secret Santa code kata, this time a scouting mission into functional programming with F#.

To recap:

  • My first solution, written in PowerShell, relied on selecting random pairs of people and using a “hill-climbing” algorithm to avoid getting stuck.
  • My second solution I constrained to be deterministic — no randomness.

This one was more about trying to write something meaningful in F# using a problem I’m by now familiar with. Take a look at the code:

open System
open System.IO

// TODO: what's the accepted way to configure an F# program at runtime, App.config?
let lines = File.ReadAllLines(@"names_santa.txt") |> List.ofArray

let surname (x : string) = (x.Split ' ').[1]

// TODO: how do I make this generic enough to use in both cases below?
let lastItem (a : string[]) = a.[a.Length - 1]

let randomizer = new Random(DateTime.Now.Millisecond)

let swap (a: _[]) x y =
    let tmp = a.[x]
    a.[x] <- a.[y]
    a.[y] <- tmp

// shuffle an array (in-place), borrowed from a code snippet site
let shuffle a = 
    let len = Array.length a
    Array.iteri (fun i _ -> swap a i (randomizer.Next(i, len))) a

let linesArray = Array.ofList lines

// TODO: this "do-while" loop, I should be able to rewrite it as a recursive function, but how?
shuffle linesArray 
while surname linesArray.[0] = surname linesArray.[(Array.length linesArray) - 1] do shuffle linesArray

let rec pairings = linesArray
                    |> Seq.windowed 2
                    |> Seq.choose (fun (x:string[]) -> 
                                        match x with
                                        | x when surname x.[0] <> surname x.[1] -> Some(x)
                                        | _ -> None
                                   ) 

let pairingsList = List.ofSeq pairings

List.append pairingsList [[|pairingsList.[pairingsList.Length - 1].[1]; pairingsList.[0].[0]|]] |> 
    Seq.iter (fun (x:string[]) -> printfn "%s gives a gift to %s" x.[0] x.[1])

Console.WriteLine "Done, press Enter to exit"
Console.ReadLine() |> ignore

As you can see, I left myself a few to-do items. I boxed the effort at three hours, which is why I went ahead and borrowed the shuffle logic from the internet.

The first hour was learning to speak F# again, especially the method signatures. I played with F# when it was in beta, so I didn’t go into the kata stone cold. However, it took me a while to troubleshoot why my methods didn’t have the signature I expected.

I spent the most time writing the pairings function. Once I had the insight of using the match operator, the algorithm came together very quickly. I decided that I wasn’t happy with it being deterministic. I found that if I provided a file that was already in an appropriate order, pairings regurgitated the list. Dissatisfied, I went about trying to shuffle the array. Not being familiar with unit testing in F#, I used the F# Interactive console. I got frustrated with trying to implement the shuffle algorithm, so I decided to study a working copy.

The hard part came in integrating it with my code. I resorted to using a while loop, which I know from reading about functional programs means that I’m not thinking of the problem through. I believe I couldn’t convert this into a recursive function because shuffle returns a unit (that is, it does the work inline). If it returned an array, I bet I’ve have more luck. I’ll have to experiment further.

My attempts to rewrite the loop badly broke the program. I used comments as poor man’s source control, and I got lucky. I really should have check in the first working version into my local Subversion repository.

Some time passed. I managed to look at the do-while problem again, and after about 90 minutes, I solved both it and another issue that bugged me.

Here’s the second revision:

open System
open System.IO

let randomizer = new Random(DateTime.Now.Millisecond)

let surname (x : string) = (x.Split ' ').[1]
let lastItem (a : 'a list) = a.[a.Length - 1]

let shuffle items =
    let upperBound = (List.length items) * 100
    let randomlyWeightedItems = List.map (fun item -> item, randomizer.Next(0, upperBound)) items
    let sortedByWeight = List.sortWith (fun (_, leftWeight) (_, rightWeight) -> leftWeight - rightWeight) randomlyWeightedItems
    List.map (fun (item, _) -> item) sortedByWeight

let shuffleUntilEndsDiffer theList =    
    let rec loop a =        
        let shuffled = shuffle a        
        if surname shuffled.Head = surname (lastItem shuffled) then             
            loop shuffled    
    loop theList

// Main part of the program, need to find out how to separate code into files

let lines = List.ofArray (File.ReadAllLines(@"names_santa.txt"))

shuffleUntilEndsDiffer lines

let rec pairings = lines
                    |> Seq.windowed 2
                    |> Seq.choose (fun (x:string[]) -> 
                                        match x with
                                        | x when surname x.[0] <> surname x.[1] -> Some(x)
                                        | _ -> None
                                    )
                    |> List.ofSeq 

let veryFirstPerson = pairings.Head.[0]
let veryLastPerson = (lastItem pairings).[1] 

List.append pairings [[|veryLastPerson; veryFirstPerson|]] 
    |> Seq.iter (fun (x:string[]) -> printfn "%s gives to %s" x.[0] x.[1])

Console.ReadLine() 
    |> ignore

The do-while loop was solved by making the shuffling function return the shuffled contents instead of unit (void in C# parlance).

The second change was to get away from arrays. Arrays in F# are mutable, and I wanted to only use immutable data structures as much as possible.

The shuffler was the main barrier. Once I hit upon the idea to associate each person with external data, in this case a random weighting, the rest fell into place. You may also notice some language usage improvements, such as using a.Head instead of a.[0]

Questions? Comments?

Advertisements
No comments yet

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: