Every year in the run up to Christmas we always seem to get asked for help with IT-related problems right before the silly season really kicks off. But this is the first time we’ve been asked for help by the big guy from the North Pole himself, Santa.
So what did he have in mind? ‘Automation!’, he told us. ‘My Head Elf is down with the spicy cough and he usually decides which kid gets what. Hey, I just deliver the toys. I don’t tick off the naughty or nice list’.
Luckily the other elves had already consolidated the global present wishlist so they had a good idea of what each kid wanted (and didn’t want). They cross checked this against the ‘Naughty v Nice’ master spreadsheet (no pressies for the ‘naughties’ of course) and worked out how many gifts each kid could expect based on the size of their fam.
With the boss Elf on sick leave and Santa self-medicating with shots of butterscotch schnapps, the rest of the elf crew began frantically making random toys. With no one there to guide them, stock levels were all over the shop! However, they did manage to categorise and approximate the value of every gift they rolled out – High, Medium or Low. This way they made sure the kids got a variety of pressies of varying value.
So what do we know about Santa’s problem? And, how do we begin to solve it?
Let’s define some business rules from what we know so far. Thanks to the elves we know what the little rug rats don’t want. Let’s call these Exclusion Rules. I mean we don’t want one of our little princes/princesses to get something they told us they don’t want right? Can you imagine?
But they’ve also let us know what they do want. We’ll do our best, but there’s no guarantees, so they might not get exactly what they asked for. There might not be enough stock to go around for instance. So let’s call these Weighted Rules.
We can use these rules to allocate a score to every child/present combo. Think of this as a suitability score. This is what we call a cartesian join (all presents and all children). We use BigQuery to handle this huge volume of data.
Let’s give an Exclusion Rule a large negative score and a Weighted Rule a small positive score. In this way, we can ensure that an Exclusion Score will always trump a Weighted Score, and these negative scores can be used to make sure a child won’t receive a present in a category they’ve told us they don’t like.
The more of the Weighted Scores a child/present combination receives, the more likely the child is to receive that present.
We now have a score for every child and present combination. All of this can be calculated using vanilla SQL – more on this shortly. Now we have these scores, we can use them for present allocation. We do this by:
Using this cartesian data, we can now apply a Dislike Score for each combination of child/ present. We do this by looking at all the categories of present the child doesn’t like, against the categories of present for a given child/present row. We count how many matches of dislikes we have for present categories – and multiply this by a large negative score. The data looks as follows:
For the first row, we have 9 presents of High Value out of a total of 20 presents overall. Therefore our diversity score for any presents allocated to child #1 that are of High Value is 4.5 (9/20*10)
To ensure that High Value presents are treated as being more desirable, we can simply add a score for each present value, so Low = 1, Medium = 2 and High = 3. This means that Higher Value presents will be placed further up the desirability list of presents for the child – as the score for those presents will be higher.
Finally, we want to collect all of these scores – for both Exclusion and Weighted Rules – and sum them altogether to get a final grand total score for a given child/present combination.
Note: the dislike & like categories for the children and categories for the present are also available, but have been omitted here for clarity.
We sort by the score in descending order, so the best matches are listed first. For a limited number of categories and business rules – as per this example – a lot of the values will be the same – in which case additional sort fields (i.e. the child ID and present ID here) will be required in order to make the process deterministic and repeatable. You can randomise the sort – but it can make tracking down errors hard – as it can be difficult to repeat the process that caused the error in the first place.
Now we progress to the allocation process using all these scores – something we’re going to do in code. Let’s start by demonstrating the process using ‘pseudo code’. We already touched on how we’d go about this earlier, but the detailed process will look like this:
# For every child/present score (sorted by score in descending order): # Get the child, present and score # If there is a negative score (or the child has been naughty), don't allocate, # otherwise continue # Check to see if we've give out all of these type of presents (continue if not) # Check to see if the child has their quota of presents (continue if not) # If we're allocating the present, then # Decrement the stock level for this present # Decrement the number of presents the child is now entitled to # Keep a reference to the allocation (including non-allocations, so we can # check why) # Go back to the beginning of the loop and repeat.
We can use this information (along with additional data that has been omitted here for clarity – such as all the business rule scores) to help us understand why a child was allocated a given present.
However, the list that Santa wants on Christmas Eve is as follows:
This example is intentionally trivial to demonstrate how straightforward logic can be used to solve an allocation problem. There are many other considerations as the problem scales in terms of volumes of data and complexity, such as:
The complete set of accompanying code to demonstrate this allocation process can be found at:
Santa is relieved (Mrs Clause is happy Santa is no longer stressed and/or drunk on schnapps), and the Mondo Ventures Team are all going to bed as it’s way past their bedtime.
Merry Christmas everyone, and if you have a Christmas nightmare you’d like help with, then give Mondo a shout. We’d love to hear from you.
Drop us a note and we’ll be in touch as soon as we can be.