Probably a little naive, I first though writing a blog post about secret Santa would be fun and original. Turns out it might be fun but definitely not original, and many wrote about the topic before me (here, here or there).

Luckily for me, I found fewer resources based on Java and constraint solvers. In addition, I have my own set of functional constraints. That gave me the motivation to write this post. So first thing first, let me define the rules of my secret Santa.

  • RULE 1: Everybody must give and receive a gift.
  • RULE 2: No member of the same family should share gifts with each other. That also implies that nobody is gifting himself.
  • RULE 3: Participants can be present on the 24th or 25th, and gift should be shared between people present on the same day.
  • RULE 4: The distribution of gifts should not form sub-sets of people, in other word the chain of gifts must be unique.

Problem specification

The first step of problem solving is to be able to express the problem and the solution easily. To do so, I defined three classes, two to express the problem (Person and Family), and one for the solution (GiftSolution). A person has a name and a mail, might be present on the 24th or 25th and has a family. A family has a (last) name and also has a notion of presence on the 24th or the 25th. For a person, the notion of presence of the family is taken into account only of its own presence is undefined (null). I also defined a bidirectional relation between families and people to preserve the model consistency with ad hoc mechanisms.

public class Person {
    private String name;
    private Family family;
    private Boolean on24;
    private Boolean on25;
    private String mail;

    public Person(String name, Family family, String mail) {
        this(name, family, null, null, mail);
    }

    public Person(String name, Family family, Boolean on24,
      Boolean on25, String mail) {
        this.name = name;
        this.family = family;
        this.family.getPeople().add(this);
        this.on24 = on24;
        this.on25 = on25;
        this.mail = mail;
    }

    // generic accessors...

    public boolean isOn24() {
        if (on24 != null) return on24;
        else return this.family.isOn24();
    }

    public boolean isOn25() {
        if (on25 != null) return on25;
        else return this.family.isOn25();
    }
}

public class Family {
    private String name;
    private List<Person> people = new ArrayList<>();
    private boolean on24;
    private boolean on25;

    public Family(String name, boolean on24, boolean on25) {
        this.name = name;
        this.on24 = on24;
        this.on25 = on25;
    }

    // generic accessors...

    public void setPeople(List<Person> people) {
        people.forEach(personne -> personne.setFamily(this));
        this.people = people;
    }
}

public class Pair<T, T1> {
    private T key;
    private T1 value;

    public Pair(T a, T1 b) {
        this.key = a;
        this.value = b;
    }

    public T getKey() { return key; }
    public T1 getValue() { return value; }
}

public class GiftSolution {
    private List<Pair<Person, Person>> attributions = new ArrayList<>();

    public void addPair(Person from, Person to) {
        this.attributions.add(new Pair<>(from, to));
    }

    public List<Pair<Person, Person>> getAttributions() {
        return attributions;
    }
}

Defining a specific instance of the problem is then quite straightforward.

Family fA = new Family("a", true, true);
Person pA1 = new Person("pA1", fA, "p1@a.com");
Person pA2 = new Person("pA2", fA, "p2@a.com");
Family fB = new Family("a", true, true);
Person pB1 = new Person("pB1", fB, "p1@b.com");
Person pB2 = new Person("pB2", fB, true, false, "tp2@b.com");

This piece of code defines four people, dispatched in two families of two. The last person isn’t present on the 25th.

That done, the challenge is now to link the problem and the solution!

Problem solving with constraint solving

I will not go into the details of constraint solvers as the documentation of choco is much clearer than anything I could write. But to give you a broad view of constraint solving, the idea is to translate a problem into a set of variables and their potential values and a set of constraints in between these variables. Then the constraint solver automatically find if a solution exist, and the sets of values that satisfy the constraints. In the code below, we define three sets of constraints, each encoding one of the rules we defined earlier, at the exception of the fourth. But we’ll come back to that one later.

public class Problem {

    private List<Person> people = new ArrayList<>();
    private Set<Family> familySet = new HashSet<>();

    public Problem(Person... people) {
        // precompute the list of people and families.
        this.people.addAll(Arrays.asList(people));
        this.people.forEach(p -> familySet.add(p.getFamily()));
    }

    private Model createModel() {
        Model model = new Model("Gift Problem");

        // encoding the people into model's variables.
        int size = people.size();
        IntVar[] persIntVar = new IntVar[size];
        for (int i = 0; i < size; i++) {
            String firstName = people.get(i).getName();
            IntVar intVar = model.intVar("var_" + firstName + "_" + i, +0, size - 1);
            persIntVar[i] = intVar;
        }

        // RULE 1: Everybody must give and receive a gift.
        model.allDifferent(persIntVar).post();

        // RULE 2: no gift in a familly
        for (Family f : familySet) {
            for (Person p : f.getPeople()) {
                for (Person p2 : f.getPeople()) {
                    int pidx = people.indexOf(p);
                    int p2idx = people.indexOf(p2);
                    model.arithm(persIntVar[pidx], "!=", p2idx).post();
                }
            }
        }

        // RULE 3: gifts can only be shared between people present the same day.
        for (Person p : people) {
            for (Person p2 : people) {
                boolean presentOnTheSameDay = p.isOn24() && p2.isOn24()
                        || p.isOn25() && p2.isOn25();
                if (!presentOnTheSameDay) {
                    int pidx = people.indexOf(p);
                    int p2idx = people.indexOf(p2);
                    model.arithm(persIntVar[pidx], "!=", p2idx).post();
                }
            }
        }

        return model;
    }
}

So far we have a solution that can yield valid solutions taking into account the three first rules.

But, the figure below depict a solution that conforms to the first four rules, but not the fourth, since we have two sub-sets of people gifting each other.

I must admit that I am not an expert of constraint solvers, so I might have missed something, but I did not find a way to encode the fourth rule into the model.

Instead, I simply integrated it as a precondition, and I loop over the potential solutions yield by the Choco model until a solution that conforms to the fourth rule matches. The validation of the fourth rule is based on the isSingleLoop method presented below.

public static boolean isSingleLoop(GiftSolution solution) {
    List<Pair<Person, Person>> attributions = solution.getAttributions();
    int size = attributions.size();

    final List<Person> lst = new ArrayList<>();
    Pair<Person, Person> current = attributions.get(0);
    while (!lst.contains(current.getKey())) {
        lst.add(current.getKey());
        final Pair<Person, Person> currentF = current;
        current = attributions.stream()
                .filter(p -> Objects.equals(p.getKey(), currentF.getValue()))
                .findFirst()
                .get();
    }

    return lst.size() == size;
}

Without extensive experimentation, even with eighteen people and five families, finding a solution is instantaneous.

Adding randomness

I observed that, using Choco, the returned solution is deterministic for a given problem. In other words, executing twice the same program yield the same solution. But it is funnier if the secret gift givers can’t be predicted. To do so, a simple shuffle of the list of participants before the generation of the Choco model is enough to randomize the yield solutions.

// [...]
Model model = new Model("Gift Problem");

Collections.shuffle(people);
// [...]

Conclusion

Using only a few lines of code we managed to find interesting solutions to a non-trivial but fun problem. I simply integrated the code presented in this post with a mail sending library to notify every member of my family to whom they are to give a gift.

A full version of this project can be found on github. I’m currently working on its integration into a web service using Quarkus for the backend and Vue.js for the frontend. Those are really fun and productive frameworks and I hope to write something about that soon.