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!