I got the following email from Billy today:

Jake,My family switched to a "drawing" system for choosing who to buy gifts for. This year, they did the drawing by hand. For fun, I decided to make a web page for next year.

The rules:

* The drawing should result in each person as a giver once and a receiver once.

* There are no gifts to siblings/spouses.

* Kids are on a separate list from adults so that kids give to kids and adults give to adults.I was amazed at how much more complicated this was than I thought. Not that 50 lines of code is complicated, but I thought it'd be like 5 lines.

http://eyepits.com/xmas

http://eyepits.com/comment.php?entry=/xmas/index.phpIs there a trick to this? Feel free to use any language and reformat the data.

Billy

Making an elegant solution for this problem sounded like an interesting challenge and the more I thought about it, the more I realized that it was such a perfect problem to solve in Prolog. So, I downloaded SWI-Prolog and tried to remember how to write Prolog code. It took quite a bit of effort to brush the 2+ year old cobwebs away, but I got it finished! Below is my solution:

adult(kordell).

adult(annemarie).

adult(doug).

adult(carla).

adult(terry).

adult(jennifer).

adult(billy).

adult(jacqui).

adult(jim).

adult(sue).

husband(kordell, annemarie).

husband(doug, carla).

husband(terry, jennifer).

husband(billy, jacqui).

husband(jim, sue).

spouse(X,Y) :-

husband(X,Y).

spouse(X,Y) :-

husband(Y,X).

child(wyatt).

child(quinn).

child(emma).

child(douglasjr).

child(meghan).

child(mckenzie).

child(mikayla).

child(matthias).

child(grace).

child(kalin).

child(ben).

father(kordell, wyatt).

father(kordell, quinn).

father(doug, emma).

father(doug, douglasjr).

father(terry, meghan).

father(terry, mckenzie).

father(terry, mikayla).

father(billy, matthias).

father(billy, grace).

father(billy, kalin).

father(billy, ben).

sibling(X,Y) :-

child(X),

child(Y),

father(Z, X),

father(Z, Y),

X \= Y.

valid_match(X,Y) :-

adult(X),

adult(Y),

not(spouse(X,Y)),

X \= Y.

valid_match(X,Y) :-

child(X),

child(Y),

not(sibling(X,Y)),

X \= Y.

find_matches([], Used).

find_matches([Person|Rest], Used) :-

valid_match(Person, X),

not(member(X, Used)),

find_matches(Rest, [X | Used]),

write(Person), write(' '), write(X), nl.

do_it :-

findall(X,adult(X);child(X),Z),

find_matches(Z, []).

I just wrote a secret santa code for my family. I wrote it in MATLAB. The solution wasn't as elegant as it could have been, but I was under a time crunch.

We had done this in previous years, so I had the added constraint of people not having who they had the year before (and a soft constraint of the people they had two years before).

I have no idea how prolog work, so I don't really follow your example above.

I would have liked to tie it into a website/msql database, so that people could simply log into the website and find out who they have. But I really didn't have time for that :)

Prolog is a funky language where you type up logical predicates or rules and query the system to evaluate the predicates. So something like child(wyatt) can be read as "wyatt is a child". If I later typed child(X) then Prolog would evaluate the predicates and return all values of X where child(X) is true. father(kordell, wyatt) can be read as "kordell is the father of wyatt" or "father(X,Y) is true when X = kordell and Y = wyatt". Then you can make interesting compound predicates like sibling(X,Y) above, which can be read as "sibling(X,Y) is true if there is an X and Y where X is a child, Y is a child, there is a Z where Z is the father of X and the father of Y, and where the value of X and Y are not equal."

The find_matches predicates are used recursively to process the list of all people and find valid matches for everyone. find_matches([], Used) is the base case, where the passed in list is empty aka [] which does nothing (but evaluates true). The other find_matches takes in list and splits off the first element (Person) to find a match before recursively processing the Rest of the list.

Good stuff! :D