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
aka Kris Kringle,
aka Chris Kindle,
aka amigo secreto,
Names are drawn, and you give a gift to that person.
Can you improve on random?
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)
define the range of valid values,
and define constraints.
I've defined it, now what?
pass the definition to a
Archetypal Constraint Satisfaction Problems (CSPs)
- 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
Constraint number n+1 - Couples don't buy for couples
- Can be hard to model
- Can be hard to verify and debug
- May not find a solution in reasonble time
- May quickly give no solution
- Easy to make changes
One last hack...
Presents must be either-
Second hand, or
Find out more
Links and stuff on my blog - http://pat.macpherson.id.au/