Skip to content

“Secret Santa” Code Kata in Powershell

25 January 2012

The team at work is doing a Code Kata, the Secret Santa kata from Ruby Quiz. In it, you are given a list of names and emails and need to pair givers with receivers, with the only constraint being that a giver and receiver can’t have the same surname.

I wrote my solution in PowerShell. I wanted to use native PowerShell functionality, so I didn’t import any .NET libraries. I know this post is brief, but I wanted to get my solution posted with a little commentary while it was still fresh in my mind.

When run like this:

PS> .santa.ps1 .names.txt

It gives output like:

Giver                                                Receiver
-----                                               ---------
John Smith <jsmith@example.com>         Jane Doe <jdoe@example.com>
...

Here’s the code:

 param($file)

 function ConvertTo-Array($hashtable) 
 {   
     $result = @()
     $hashtable.GetEnumerator() | % {
         $object = New-Object PSObject   
         Add-Member -inputObject $object -memberType NoteProperty -name Giver -value $_.Name 
         Add-Member -inputObject $object -memberType NoteProperty -name Receiver -value $_.Value 
         $result += $object
     }   
     $result
 }

 $none = "NONE"
 $names = @{}
 gc $file | % { $names.Add($_, $none) }
 $namesToMatch = $names.Keys.Count
 if ($namesToMatch -lt 2) {  throw "Need at least two names to match" }

 while (($names.Keys | ? { $names.$_ -eq $none }).Length -gt 0) 
 {
     $from = $names.Keys | ? { $names.$_ -eq $none } | Get-Random
     $to = $names.Keys | ? { $_ -ne $from -and $names.Values -notcontains $_ } | Get-Random
     #"DEBUG: $from, $to"
     if ($from -ne $null -and $to -ne $null -and $from.split()[1] -ne $to.split()[1]) 
     {
         $names.$from = $to
     }
     else
     {
         $undoMatch = $names.Keys | ? { $names.Values -ne $none `
             -and $from.split()[1] -ne $_.split()[1]} | Get-Random
         #"DEBUG: unset $undoMatch"
         if ($undoMatch -ne $null) 
         {
             $names.$undoMatch = $none
         }
     }
     $percentComplete = 100 * ($names.Values | ? { $names.$_ -ne $none }).Length / $namesToMatch
     Write-Progress -activity "Match in Progress" -status "% Complete:" -percentcomplete $percentComplete
 }
 $results = ConvertTo-Array $names
 $results | ft  

(I apologize in advance for the formatting. I will look into another solution like Pastebin if I do this more often. Please comment if you have recommendations.)

It reads the contents of the file and writes each line to a hashtable, where all the receivers are $none (a special value I created which I used like $null).

As long as there are unmatched people, I go through an algorithm to select a random gift giver who doesn’t have a receiver ($from) and a receiver who doesn’t have a giver ($to). The split(” “)[1] yields a person’s surname.

I used a variant on the “Hill Climbing” algorithm mentioned on the site. If I run into a situation where there are no more matches, I take a random person who could have been a match and throw them back into the pool of candidates. In this way, the algorithm never gets stuck.

At the end, I call my ConvertTo-Array function to beautify the output. Without it, the hashtable columns are labeled “Name” and “Value”, and that didn’t satisfy me. (I couldn’t get Format-Table to help.)

I added a progress bar to see how often this part of the code is invoked, and it gets called once or twice per run on average. However, the script itself has decent performance. It takes a second or so to match 40 names.

Please let me know what you think or ask questions. I’m happy to go into more detail.

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: