A very constrained Christmas

Over-optimising a secret santa draw by using a constraint satisfaction solver.

By Pat Macpherson

Who am I?

Born in Lithgow in 1980, I am...

a developer at ansarada, fine purveyor of virtual datarooms.

(is your passive income startup being acqui-hired by angel venture capitalists?)

(we're hiring - interested in microservices, BDD, Spotify development model?)

This has been a message from Val Morgan.

The main feature will now begin.

A talk about Christmas... in July? WTF?

insert joke about the recent weather

Secret Santa

aka Kris Kringle, aka Chris Kindle, aka Christkindl, aka Monito-Monita, aka Wichteln, aka amigo secreto,

Names are drawn, and you give a gift to that person.

Can you improve on random?

MICROSOFT EXCEL!

Montage of =A$1...

...pressing CTRL-R to re-seed random values...

...in order to brute force a solution

Constraint Programming or
Constraint Satisfaction Problems (CSPs)

What?

Define variables, define the range of valid values, and define constraints.

I've defined it, now what?

pass the definition to a
constraint solver

Archetypal Constraint Satisfaction Problems (CSPs)

Sudoku
N Queens problem
Resource allocation
Scheduling (e.g. sports)

Is Secret Santa a good fit for CSP?

First obvious constraint - one person, one present.

Second obvious constraint - can't buy for yourself.

Some sample families

A super Christmas crossover show

TO THE CODE MACHINE!

Double the trouble

I'm already buying a present for this person!

Constraint number whatever - Can't buy for people in your family group.

More constraints = more fun

Said no teenager ever.

Can't buy for who you bought for last year

Can't buy for who your partner bought for last year

Can't buy for the partner of who you bought for last year.

ONCE MORE INTO THE CODE BREACH, MY FRIEND.

Make it a circle

Constraint number ∞ - A single circuit


solver.Add(solver.MakeCircuit(santas));

What's next?

Constraint number n+1 - Couples don't buy for couples

Downsides?

Can be hard to model
Can be hard to verify and debug
May not find a solution in reasonble time

Benefits?

May quickly give no solution
Easy to make changes
POWERFUL!

One last hack...

Presents must be either-

Second hand, or

personally handmade.

Find out more

Links and stuff on my blog - http://pat.macpherson.id.au/