Programming Challenge

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.php

Is 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, []).

2 Comments

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

Random Photo