The Secret Santa Problem
by Yan Cui
As I walked down Oxford Street the other day, it’s hard to miss all the Christmas decorations everywhere. Many of the shops are already running Christmas sales, and HR departments up and down the country are busy booking venues for Christmas parties. With the imminent arrival of Christmas, another time honoured office tradition will soon come to pass – Secret Santa. Which means now is the perfect time to solve the Secret Santa problem, in F# of course 🙂
The Rules
Each person must give and receive a present
People can only give present to someone who is not in their family (i.e. same surname)
The names are: Toby Blair, Ian Smith, Martin Kelly, Kate Kelly, John Smith, Bruno Tavares, Vicky Chen, Sarah Kelly, Mark Kelly and Ajay Singh.
Approach
Sort the names by surname, with the most frequent surnames first.
Iterate through the sorted names and…
Add to the queue if the name is of the same family as the head of the queue.
Otherwise, pair with the head of the queue and send each other presents.
For example:
Implementation
First let’s add some function names. We mentioned earlier that most frequent surnames should appear first, this is an important detail. Otherwise, the following might happen and lead to a nonsolution:
let surname (name : string) = name.Split().Last() let sortedBySurname names = names |> Seq.groupBy surname |> Seq.sortByDescending (Seq.length << snd) |> Seq.collect snd
Now that’s outta the way, we just need to go through the sorted list of names and match people up (via a Queue) and..
let secretSanta names = let queue = new Queue<string>() for name in (sortedBySurname names) do if queue.Count = 0 || (surname <| queue.Peek()) = (surname name) then queue.Enqueue name else let giftee = queue.Dequeue() printfn "%s -> %s" name giftee printfn "%s -> %s" giftee name
MISSION ACCOMPLISHED!