It's not widely known, but Santa Claus is a true early adopter. For instance, he long ago understood the critical role of data in operations. There is a reason he checks that list twice and uses XML and NoSQL - his entire operation depends on it!
But Santa also realized that no matter how great his systems were, to really scale out the Christmas spirit he needed to let everyone get in on the gift matching. Once again, Santa was ahead of the curve, developing the very early crowdsourcing program of Secret Santa.
But the old pick names out of the hat routine was starting really show some strain. And the first digital versions just did straight forward matching (something Santa moved well beyond when he adopted semantics).
Prompted by a very determined campaign from 9-year-old girl who wants to be a programmer and an engineer (you know who you are), Santa decided to reboot Secret Santa with the help of his very agile Elf programming teams. They looked at couple of approaches and some of the Old Skool Elves re-assembled Team XML Old Skool and got to work. Another team took on the added problem of transactions for each pick and their Javascript solution is here.
Here is how team Old Skool tackled the problem:
The first step is the list of participants. Key to scaling this out is making so that groups can pick together and ensure they don't get someone from their group. For instance, family groups: You already have to get your brother something so what you really want is your cool cousin or maybe her somewhat OK brother.
Being team XML Old Skool, we made the participant list in XML (and programmed the picking in XQuery - specially MarkLogic's XQuery implementation which you can run in Query Console).
This XML creates a nice data model of the participants and their family groups and, with XQuery, we can set that to a variable and work on it from there:
xquery version "1.0-ml";
let $family-list := <family>
<person><first>Kid1</first><fname>Family1</fname></person>
<person><first>Kid2</first><fname>Family1</fname></person>
<person><first>Parent1</first><fname>Family1</fname></person>
<person><first>Kid3</first><fname>Family2</fname></person>
<person><first>Kid4</first><fname>Family2</fname></person>
<person><first>Parent2</first><fname>Family2</fname></person>
<person><first>Parent3</first><fname>Family2</fname></person>
<person><first>Grandparent1</first><fname>Family3</fname></person>
<person><first>Grandparent2</first><fname>Family3</fname></person>
</family>
The next thing we need is a place to hold the picks. This is a tricky bit - XQuery is a functional programming language. It looks procedural, but in fact you can't modify variable values as you go (known as 'side effects') ... unless you use a map:
let $picked-map := map:map()
To make sure this is truly a good pick, let's also randomize this list by breaking it apart and putting it back together in a new variable:
let $random-family-list := for $person at $pos in $family/person
order by xdmp:random()
return
<family>{$person}</family>
That gives up the data we need to make the match, so let's get picking! Job one is to iterate through the random family list. For those of you that have forgotten, in XQuery you use a FLOWR statement to literate through a list. We just did that above to make the random list. A FLOWR goes through each item in the list and runs the rest of the query based on the data from each item of the list. For us, we'll get a person from the random family list:
for $person at $pos in $random-family-list/person
And we can now start to collect data for a match. First up, we need the current state of the picked map. And yes, that's another FLOWR inside of that if then:
let $already-picked := if (map:count($picked-map) > 0) then
for $key in map:keys($picked-map)
return
map:get($picked-map, $key)
else "nothing"
Then we get the family groups to pick from. We do this with neat XPath to extract a picklist of ALL the names NOT in the picker's family group. This is an especially cool thing about XML and paths: you can use simple path tests to make just the right list for a given condition (and not have complicated if/then loops):
let $testname := $person/fname
let $family-picklist := $family-list/person[./fname != $testname]
But that doesn't work so well to get only names not already picked. I might have this wrong, but picking the items in one sequence (the names) that are not in another sequence (those already picked) means you need to test them individually. Since this is a Santa Blog I won't go into it, but list just say that, in XQuery, '==' != '=' and leave it at that! But doing it this way, we can also randomize the picklist, so all good. And yup, that 'order by xdmp:random() does magic to randomly order your FLOWR. I think the Elves snuck that into MarkLogic 4.1 or so:
let $picklist := for $picked in $family-picklist
where fn:not($picked/first = $already-picked)
order by xdmp:random()
return $picked
And now we have what we need to make the pick:
let $picklength := fn:count($picklist)
let $pick := xdmp:random($picklength -1) + 1
let $choice := $picklist[$pick]
What's going on with the math around the random? xdmp:random takes a max value parameter and returns a result from 0 to that max value. So if we have a list of 6, we want 6 possible random results (0 through 5) and so we -1 the parameter. Then we need to match our sequence of possible picks (1 through 6) so we +1 the pick (which will be 0 through 5). Clear? Look, the extremely agile Elf programming team got this right away ...
With this pick - pulled by using the random number to take the person at that position in the sequence ($picklist[3] = third person in the picklist) - we can then add that picked person to the picked map:
let $value := $choice/first/string()
let $result := map:put($picked-map, $value, $value)
And output the results!
return
fn:string-join(($person/first/string(), "picked", $value), " ")
This gives us a nice list of matches:
Kid3 picked Parent1
Parent1 picked Parent2
Kid2 picked Kid3
Grandparent1 picked Kid1
Kid4 picked Grandparent1
Parent2 picked Grandparent2
Parent3 picked Kid2
Kid1 picked Kid4
Grandparent2 picked Parent3And its all random! Go ahead, hit execute again and the results will change ... until you get that error.
Yup, we're not done. The Secret Santa Between Groups Problem includes the nasty reality of having the picks sometimes not work out. Kid1 might get Parent3 etc but when Parent3 picks, there might not be anyone outside of their family to choose. In the real world, you just pick again. And that's what we'll just add.
Before getting into the main loop, we'll do a quick count of the family group and then set the entire results of the loop to a variable:
...</family>
let $family-count := fn:count($family-list/person)
let $secret-santa :=
let $random-family-list := ...
Then we'll add a test for the random function to give us a '0' result if it turns out we don't have any more picks and stop the error we were sometimes getting:
let $pick := if ($picklength > 0) then xdmp:random($picklength -1) + 1 else 0
And then we'll not return anything for that failed match:
return
if ($pick eq 0) then () else fn:string-join(($person/first/string(), "picked", $value), " ")
Now, I could program another entire process to just run the picking again ... but that would be a whole other blog! For now, we'll keep it Old Skool and when we return the new $secret-santa result, if we are missing something we'll just tell the user to pick again - just like in the real world. This return now goes below the previously last return (and matches the 'let $secret-santa' line we added at the top:
return
if ($family-count eq count($secret-santa)) then
$secret-santa
else "pick again"
Now we're done - a Secret Santa picker that lets groups pick together and not get their siblings, co-workers or any other group we want to bring together and scale out the Santa Claus spirit.
You can try it out yourself - here is the complete code for Secret Santa.
When I last checked, the XML Old Skool team up North was well into the final holiday lock down period. But with this code in the bag, they are looking forward to an even bigger holiday season - one where Santa can truly scale out with crowdsourcing and the team can get to their after Christmas beach (rumored to be a secret part of Hawaii) in better shape than ever!
Blogging the holidays,
Matt