My Constraint Programming Blog

Here is a fun little problem related to the holiday. Merry Christmas, everyone! (For the Swedish readers: Sorry for the one day off greeting.)

This problem is from the Ruby Quiz#2 Secret Santas

Honoring a long standing tradition started by my wife's dad, my friends all play a Secret Santa game around Christmas time. We draw names and spend a week sneaking that person gifts and clues to our identity. On the last night of the game, we get together, have dinner, share stories, and, most importantly, try to guess who our Secret Santa was. It's a crazily fun way to enjoy each other's company during the holidays.

To choose Santas, we use to draw names out of a hat. This system was tedious, prone to many "Wait, I got myself..." problems. This year, we made a change to the rules that further complicated picking and we knew the hat draw would not stand up to the challenge. Naturally, to solve this problem, I scripted the process. Since that turned out to be more interesting than I had expected, I decided to share.

This weeks Ruby Quiz is to implement a Secret Santa selection script.

Your script will be fed a list of names on STDIN.

...

Your script should then choose a Secret Santa for every name in the list. Obviously, a person cannot be their own Secret Santa. In addition, my friends no longer allow people in the same family to be Santas for each other and your script should take this into account.

The MiniZinc model secret_santa.mzn skips the parts of input and mailing. Instead, we assume that the friends are identified with a unique number from 1..n, and the families are identified with a number 1..num_families.

We use two arrays:

• the array x represents whom a person should be a Santa of. x[1] = 10 means that person 1 is a Secret Santa of person 10, etc.
• the family array consists of the family identifier of each person.

Now, the three constraints can easily be stated in a constraint programming system like MiniZinc:

• "everyone gives and received a Secret Santa gift": this is handled with a permutation of the values 1..n using all_different(x).
• "one cannot be one own's Secret Santa". This is captured in the no_fix_point predicate, stating that there can be no i for which x[i] = i (i.e. no "fix point").
• "no Secret Santa to a person in the same family". Here we use the family array and checks that for each person (i), the family of i (family[i]) must not be the same as the family of the person that receives the gift (family[x[i]]).

Here is the complete MiniZinc model (in a slightly compact form):

include "globals.mzn"; 
int: n = 12;
int: num_families = 4;
array[1..n] of 1..num_families: family = [1,1,1,1, 2, 3,3,3,3,3, 4,4];
array[1..n] of var 1..n: x :: is_output;

% Ensure that there are no fix points in the array.
predicate no_fix_points(array[int] of var int: x) = 
      forall(i in index_set(x)) ( x[i] != i  );

solve satisfy;

constraint
  % Everyone gives and receives a Secret Santa
  all_different(x) /\      

  % Can't be one own's Secret Santa
  no_fix_points(x) /\   

  % No Secret Santa to a person in the same family
  forall(i in index_set(x)) (   family[i] != family[x[i]]  )
; 

% output (just for the minizinc solver)
output [
   "Person " ++ show(i) ++ 
   " (family: " ++ show(family[i]) ++ ") is a Secret Santa of " ++ 
    show(x[i]) ++ 
   " (family: " ++ show(family[x[i]]) ++ ")\n"
   | i in 1..n
] ++ 
["\n"];

Solution

Here is the first solution (of many):

[10, 9, 8, 5, 12, 4, 3, 2, 1, 11, 7, 6]

This means that person 1 should be a Secret Santa of person 10, etc.

The minizinc solver gives the following, using the output code (slightly edited):

Person  1 (family: 1) is a Secret Santa of 10 (family: 3)
Person  2 (family: 1) is a Secret Santa of  9 (family: 3)
Person  3 (family: 1) is a Secret Santa of  8 (family: 3)
Person  4 (family: 1) is a Secret Santa of  5 (family: 2)
Person  5 (family: 2) is a Secret Santa of 12 (family: 4)
Person  6 (family: 3) is a Secret Santa of  4 (family: 1)
Person  7 (family: 3) is a Secret Santa of  3 (family: 1)
Person  8 (family: 3) is a Secret Santa of  2 (family: 1)
Person  9 (family: 3) is a Secret Santa of  1 (family: 1)
Person 10 (family: 3) is a Secret Santa of 11 (family: 4)
Person 11 (family: 4) is a Secret Santa of  7 (family: 3)
Person 12 (family: 4) is a Secret Santa of  6 (family: 3)

Bales of Hay

As an extra, here is another MiniZinc model: bales_of_hay.mzn which solves the following problem (from The Math Less Traveled the other day):

You have five bales of hay.

For some reason, instead of being weighed individually, they were weighed in all possible combinations of two. The weights of each of these combinations were written down and arranged in numerical order, without keeping track of which weight matched which pair of bales. The weights, in kilograms, were 80, 82, 83, 84, 85, 86, 87, 88, 90, and 91.

How much does each bale weigh? Is there a solution? Are there multiple possible solutions?

The answer? There is a unique solution (when bales are ordered on weight): 39, 41, 43, 44, 47.