The Decision Management Community posted a fun challenge: Santa’s elves are supposed to order nine reindeer according to a set of rules. The rules are:
- Comet behind Rudolph, Prancer, and Cupid.
- Blitzen behind Cupid.
- Blitzen in front of Donder, Vixen, and Dancer.
- Cupid in front of Comet, Blitzen, and Vixen.
- Donder behind Vixen, Dasher, and Prancer.
- Rudolph behind Prancer.
- Rudolph in front of Donder, Dancer, and Dasher.
- Vixen in front of Dancer and Comet.
- Dancer behind Donder, Rudolph, and Blitzen.
- Prancer in front of Cupid, Donder, and Blitzen.
- Dasher behind Prancer.
- Dasher in front of Vixen, Dancer, and Blitzen.
- Donder behind Comet and Cupid.
- Cupid in front of Rudolph and Dancer.
- Vixen behind Rudolph, Prancer, and Dasher.
The challenge is to create a decision model, but this looks like a simple exercise in constraint programming. As presented in Send More Money and Eight Queens posts, SQL is a good fit for these.
Reasoning
There are nine reindeer, each of which can be in a position (1..9); hence the number of all possible permutations is
9*8*7*6*5*4*3*2*1 = 9! = 362880
A quick memory requirement estimate — 362880 rows of nine integers each — for this data set would be
362880 * (9*4 + 24) = ~ 22 MB
This should easily fit into memory of an average laptop.
The process is simple:
- Generate all possible permutations of reindeer ordering;
- Apply the rules to the set of all possible orderings;
- Keep all results that satisfy the rules.
Solution
Take a look at the code, a simple query — tested on PostgreSQL and MS SQL Server — is easy to follow; runs within 2 seconds.
There is only one solution that satisfies all the rules:
- Prancer
- Cupid
- Rudolph
- Dasher
- Blitzen
- Vixen
- Comet
- Donder
- Dancer