[QUIZ] Secret Santas (#2)

[Gavin Kistner]

The way you look at it, each person in your arrangement is the next
person's secret Santa, wrapping around the end of the array as needed,
right? Actually that's like putting people in a circle such that each
person's secret Santa is standing to his/her left (or right).

Correct. (Indeed, I wrote my own circular list class because that's
exactly how I was looking at it

But actually that leaves out the arrangements with multiple smaller
circles, so you
can't generate every solution this way.

Good point...I hadn't considered that!
Is it a good or bad thing that these smaller circles might be two
reciprocating people?
I suppose it adds to the surprise if/when it occurs.

But James' solution does however.

Apparently my RRC (Ruby Reading Comprehension) is not good. I
misunderstood Jame's solution at first. I didn't realize it was a 1<->1
mapping in to lists. (I failed to see that there were both $players and
$santas being compared in his #check_families? method.)

I like the smaller-circles possibility, and if speed were a problem,
you could add people to $santas in a more deterministic fashion
(randomize a copy, and then find the first available slot for the
person) rather easily.


The multiplicity of solutions here is pretty sweet.

 

[Niklas Frykholm]

I didn't participate, but I thought it was a trivial case of sorting the

families by number of members and start giving santas from the most populous
down. I should have tested that theory with code, but I didn't have time on
the weekend . How can it not work?

Assume three families with one member each A, B, C. Since the families
are the same size, sorting by size will not do anything. If we assign
randomly, only checking that the santa is not from the same family for
each assignment, we can get:

A -> B
B -> A

Now we have an impossible situation, for C cannot be his own santa.

// Niklas

 

[Carlos]

Assume three families with one member each A, B, C. Since the families
are the same size, sorting by size will not do anything. If we assign
randomly, only checking that the santa is not from the same family for
each assignment, we can get:

A -> B
B -> A

Now we have an impossible situation, for C cannot be his own santa.

I see! Nothing trivial here.

I'll try to understand your analysis.

Thanks.

 

[James Edward Gray II]

(Sorry for missing much of this exciting discussion. My e-mail server
is having a bad hair day...)

Does this actually work? I mean, for realistic data sets?

Excellent question. I have no idea. It does solve all the little
examples I've thrown at it reasonably fast, but "realistic data sets"
is pretty wide open. This is the first of three solutions I came up
with and not my favorite. All of my ideas have now been represented by
submissions.

What are the goals of a Secret Santa draw? Randomness should be up
there, I think. This does handle that. However, if speed also makes
the list, this falls off the wagon.

Perhaps my math is wrong

The essence of your message is right on, I think. Naturally a random
sort is an awful performer.

your test case small

I've been using real life test cases and yes, they are pretty small.

your computer really fast

Dual 2.0 G5, it's pretty fast.

or your test case not pathological

Again, I'm using real life test data. You're pathological case doesn't
happen to model my friends well, but I don't know that that makes it
less valid.

James Edward Gray II

 

[James Edward Gray II]

Good point...I hadn't considered that!
Is it a good or bad thing that these smaller circles might be two
reciprocating people?
I suppose it adds to the surprise if/when it occurs.

I'm of the opinion that it should be the number one feature for a Santa
draw. However, you don't have to use a random sort to get it.

James Edward Gray II

 

[James Edward Gray II]

I didn't participate, but I thought it was a trivial case of sorting
the
families by number of members and start giving santas from the most
populous
down. I should have tested that theory with code, but I didn't have
time on
the weekend . How can it not work?

To be honest, my first reaction to this problem was that it was
trivial. It wasn't until I was in the middle of coding up a solution
that I began to appreciate it.

One person told me this problem is just "toy code". While a Secret
Santa draw may not appeal to everyone, I assure you there are
interesting issues involved with the solution. It's a fun "toy" to
play with, if nothing else.

James Edward Gray II

 

[Joe Cheng]

I see! Nothing trivial here.

Your solution becomes viable again if you build up a circular list of
santa->recipient (each person in the list gives to the next). That's
what I did for my solution. So the possible outputs (depending on what
sorting tiebreaker is used) of the A-B-C example are:

ABCA
ACBA
BACB
BCAB
CABC
CBAC

I don't know if I would call it "trivial", but there it is.

I have to give Niklas credit for setting maximum randomness as one of
his goals. I just went for speed, simplicity, and correctness, which
was much less challenging.

 

[Joe Cheng]

One person told me this problem is just "toy code". While a Secret

Santa draw may not appeal to everyone, I assure you there are
interesting issues involved with the solution. It's a fun "toy" to play
with, if nothing else.

Sorry for the misunderstanding; I didn't intend "toy code" to mean it
was not fun, interesting, or challenging. I had fun solving it and
looking at other people's solutions. I just meant it's code that's
written for the sake of writing it, as opposed to a program you will
actually use.

Since you, James, are (presumably) actually going to use such a program
this Christmas, it's not a toy to you; but since the rest of us are just
having fun solving the problem, it's "toy code", no matter how hard the
problem is.

 

[James Edward Gray II]

I have to give Niklas credit for setting maximum randomness as one of
his goals. I just went for speed, simplicity, and correctness, which
was much less challenging.

I'm not saying you're wrong, but how you define correct can be
interesting. Your solution produces the same permutation, given the
same set of names, right? You'll have to change friends each year to
keep the surprise factor.

Seriously, I'm just kidding around. A truly random draw was not a part
of the quiz, but it is interesting to me to examine which solutions
went for it and to what degree.

James Edward Gray II

 

[Jim Weirich]

--------------010504010903070701040200
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

One person told me this problem is just "toy code". While a Secret
Santa draw may not appeal to everyone, I assure you there are
interesting issues involved with the solution. It's a fun "toy" to play
with, if nothing else.

Perhaps it does not count as enterprise level computing, but it is
certainly not toy code. At least not in our family. My family has been
using computer generated Christmas gift lists for at least 11 years (and
probably longer ... October 1993 is the earliest date given in the code
comments).

I haven't had time to partake in the Ruby Quiz yet. But just for fun,
I'm attaching my C version that my family has been using for years. It
solves essentially the same problem, although the input format is a bit
different. It also supports additional constraints such as MustByFor
(added the year Aunt Helen said she found the perfect gift for cousin
Josiah and could I "arrange" the list so that she could give his gift)
and MustNotBuyFor (added when Aunt Mary said if she got Uncle John (a
particularly difficult person to buy for) one more year in a row, she
would have my head). Oh, and I swear that the year Uncle Pat got the
exploding gift from me, it wasn't pre-arranged. Honestly!

My version doesn't support email addresses either, for when it was first
written, I was probably the only person in family who knew what email
was. Today, I think even Grandma has an email account. That would be a
great way to distribute the lists.

Oh, and if you actually use a computerized Christmas list, make sure you
archive the results. You see, Uncle Dan can never remember whose name
has been assigned to him.

--
-- Jim Weirich (e-mail address removed) http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

--------------010504010903070701040200
Content-Type: text/x-csrc;
name="xmaslist.c"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="xmaslist.c"

#define VERSION "2.01"
/*
* XMasList -- Create a Christmas List
*
* History:
* 2.00 05/Oct/93 JNWeirich -- Added Must buy list
* 2.01 21/Dec/98 JNWeirich -- Fixed bug where the buysFor lists was
* not reset when a the GenerateBuysFor was rerun.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#define strcmpi strcasecmp


/* module level variables */

#define TRUE 1
#define FALSE 0

FILE * inFile; /* name input file */
int verbose = FALSE; /* TRUE if extra printout desired */
int shorter = FALSE; /* TRUE if short output desired */
int debugging = FALSE; /* TRUE if debugging output desired */

#define MAX_PERSON 50 /* maximum number of people allowed */
int nPeople = 0; /* number of people in data base */
char * person[MAX_PERSON]; /* names of the people */
int family[MAX_PERSON]; /* family index */
int buysFor[MAX_PERSON]; /* index of who you buy for */

unsigned char avoid[MAX_PERSON][MAX_PERSON];
/* matrix of unallowed combinations */
/* i.e. if (avoid[j]) then P cant buy for P[j] */

int nMust = 0; /* number of entries in mustBuy */
unsigned char mustBuy[MAX_PERSON][2];
/* matrix of must buy associations */
/* i.e. mustBuy[0] must buy for mustBuy[1] */


unsigned int randomSeed = 0; /* random seed used to randomize the lists */

/* Usage -- Display Usage */

void Usage (void)
{
printf ("XmasList Version %s\n", VERSION);
printf ("Usage: xmaslist <people >buylist [-h][-s][-v]\n");
}


/* Random -- Return a random number between zero and n */

int Random (int max)
{
int n = (int) (max * (rand() / (float)RAND_MAX));
return n;
}


/* Randomize -- Randomize the random number generator */

void Randomize ()
{
srand (randomSeed);
}

/* StrSave -- Save a String to Dynamic Memory */

char * StrSave (char * str)
{
char *s;

s = malloc (strlen(str)+1);
if (!s) {
fprintf (stderr, "Out of Memory\n");
exit (1);
}
strcpy (s, str);

return s;
}




/*
* GetToken -- Get the Next Token from the Input File
*
* A token is delimited by a comma or end of line, or one of
* the following special characters: ":", "%", and "=".
* A "#" begins a comment that continues to the end of the line.
* The name type is returned: 'A' for names, the special character
* or EOF for end of file.
*/

int GetToken ( /* RETURN Name Type */
char * buf) /* IN buffer to get new name */
{
int ch, i;
int tok;

/* skip white space */

buf[0] = 0;
do {
ch = getc(inFile);
if (ch == '#') {
while (ch != '\n' && ch != EOF)
ch = getc(inFile);
}
} while (isspace(ch));

if (ch == EOF)
return EOF;

switch (ch) {
case ';':
case '=':
case '%':
case ',':
tok = ch;
buf[0] = ch;
buf[1] = 0;
break;

default:
if (isalpha(ch)) {
tok = 'A';
i = 0;
while (isalnum(ch) || isspace(ch) || ch=='.') {
buf[i++] = ch;
ch = getc(inFile);
}
ungetc (ch, inFile);
while (i>0 && isspace(buf[i-1]))
i--;
buf = '\0';
}
else {
tok = '?';
strcpy (buf, "?");
}
break;
}

if (debugging)
fprintf (stderr, "GT: %c [%s]\n", tok, buf);

return tok;
}


/* LookupName -- Find the Index of a Name (-1 if not found) */

int LookupName ( /* OUT index of name (-1 if not found) */
char * name) /* IN name to lookup */
{
int i;

for (i=0; i<nPeople; i++) {
if (strcmpi (name, person) == 0)
return i;
}
return -1;
}


/* ReadPerson -- Read a Person Name (-1 if not a person) */

int ReadPerson (void)
{
int tok;
int p;
static char buf[80];

while ((tok = GetToken (buf))== ',') {
}

if (tok != 'A') {
if (debugging)
fprintf (stderr, "ReadPerson: %c [%s]\n", tok, buf);
return -1;
}
p = LookupName (buf);
if (debugging)
fprintf (stderr, "ReadPerson: %c [%s] %d\n", tok, buf, p);

return p;
}


/* AddBuyer -- Add a buyer to the buysFor list */

void AddBuyer (int iBuyer, int iReceiver, int who[])
{
buysFor[iBuyer] = iReceiver;
who[iReceiver] = -1;
if (debugging) {
printf ("%d buys for %d\n", iBuyer, iReceiver);
}
}

/* GenerateBuyList -- Generate the Buys For List */

int GenerateBuyList (void)
{
int i, j, nLeft, randIndex;
int who[MAX_PERSON];
static int count = 0;

for (i=0; i<MAX_PERSON; i++)
buysFor = -1;

if (debugging) {
printf ("Generating Buy List -- Attempt #%d\n", ++count);
}

/* initialize who array with people left to buy for */

for (i=0; i<nPeople; i++)
who = i;

/* copy the must buy information in to the buysFor array */
/* ... and remove the target from the who array */

if (debugging) {
printf ("#Must Buys = %d\n", nMust);
}
for (i=0; i<nMust; i++) {
AddBuyer (mustBuy[0], mustBuy[1], who);
}

/* compress the who array */

for (i=0, j=0; i<nPeople; i++)
if (who >= 0)
who[j++] = who;
nLeft = j;

/* for each person, pick someone from the who array */
/* that doesn't violate the avoid constraints */

for (i=0; i<nPeople; i++) {
if (buysFor >= 0) /* skip this person if already handled*/
continue;

for (j=0; j<nLeft; j++) /* check for at least one possible */
if (!avoid[who[j]]) /* ... match */
break;

if (j >= nLeft)
return FALSE; /* can not find a match for i */

/* search for a match */

for (j=0; j<100; j++) {
randIndex = Random(nLeft);
if (!avoid[who[randIndex]])
break;
}
if (j >= 100)
return FALSE; /* still cannot find match */

buysFor = who[randIndex];
for (j=randIndex; j<nLeft-1; j++)
who[j] = who[j+1];
nLeft--;
}

return TRUE; /* we did it */
}




/* Main -- Main Program */

int main (int argc, char *argv[])
{
char termCh;
char abuf[81], tbuf[81];
int familyHead, i, j, agent, target;
int p1, p2;
int tok;

randomSeed = (unsigned int)time(NULL);
inFile = stdin;

for (i=1; i<argc; i++) {
if (strcmpi (argv,"-v") == 0) {
verbose = TRUE;
}
else if (strcmpi (argv, "-s") == 0) {
shorter = TRUE;
}
else if (strcmpi (argv, "-x") == 0) {
fprintf (stderr, "DEBUGGING ON\n");
debugging = TRUE;
}
else if (strcmpi (argv, "-h") == 0) {
Usage();
exit (0);
}
else if (strcmpi (argv, "-r") == 0 && i<argc-1) {
i++;
randomSeed = (unsigned int)atol(argv);
}
else {
inFile = fopen (argv, "r");
if (!inFile) {
fprintf (stderr, "Unable to Open File [%s]\n", argv);
exit (1);
}
}
}

/* initialize the avoidance and must buy matricies */

memset (avoid, 0, sizeof (avoid));
memset (mustBuy, 0, sizeof(mustBuy));

/* read the input file */

familyHead = 0;
while ((tok=GetToken(abuf)) != EOF) {
switch (tok) {
case ';': /* end of family */
if (debugging) {
fprintf (stderr, "Finishing Family: ");
for (i=familyHead; i<nPeople; i++ )
fprintf (stderr, "%s, ", person);
fprintf (stderr, "\n");
}
familyHead = nPeople;
break;

case 'A': /* add a member to the list and current family */
if (LookupName (abuf) >= 0) {
fprintf (stderr, "Name [%s] is a Duplicate\n", abuf);
exit (1);
}
if (nPeople >= MAX_PERSON) {
fprintf (stderr, "Too Many People in List\n");
exit (1);
}

person[nPeople] = StrSave (abuf);
for (i=familyHead; i<=nPeople; i++) {
avoid[nPeople] = TRUE;
avoid[nPeople] = TRUE;
}
nPeople++;
break;

case '%': /* add an avoidance */
p1 = ReadPerson ();
p2 = ReadPerson ();
if (p1 < 0 || p2 < 0) {
fprintf (stderr, "Bad Avoid List\n");
exit(1);
}
avoid[p1][p2] = TRUE;
if (debugging) {
fprintf (stderr, "Avoid: %s, %s\n",
person[p1], person[p2]);
}
break;

case '=': /* add a must buy */
p1 = ReadPerson ();
p2 = ReadPerson ();
if (p1 < 0 || p2 < 0) {
fprintf (stderr, "Bad Must Buy List\n");
exit(1);
}
if (nMust >= MAX_PERSON) {
fprintf (stderr, "Too Many Must Buy Lists\n");
exit (1);
}
if (debugging) {
fprintf (stderr, "MustBuy: %s, %s\n",
person[p1], person[p2]);
}
mustBuy[nMust][0] = p1;
mustBuy[nMust][1] = p2;
nMust++;
break;

case ',': /* ignore commas */
break;

default:
fprintf (stderr, "Syntax error in file ");
if (nPeople > 0)
fprintf (stderr, "after: %s\n", person[nPeople-1]);
else
fprintf (stderr, "before any people\n");
break;
}
}

/* print the names and avoid list */

if (verbose) {
for (i=0; i<nPeople; i++)
printf ("[%2d] %s\n", i, person);

printf ("\n\n");
for (i=0; i<nPeople; i++) {
for (j=0; j<nPeople; j++)
printf (" %c", (avoid[j] ? 'X' : '-'));
printf ("\n");
}
printf ("\n\n");
for (i=0; i<nMust; i++)
printf ("[%2d] %-10s Must Buy For [%2d] %s\n",
mustBuy[0], person[mustBuy[0]],
mustBuy[1], person[mustBuy[1]]);
}

/* generate the buys for list */

Randomize ();

for (i=0; i<100; i++)
if (GenerateBuyList())
break;

if (i>= 100) {
fprintf (stderr,
"Unable to Generate Buy List after %d attempts\n", i);
exit (1);
}

/* print the buy list */

printf ("# Seed %u\n\n", randomSeed);
for (i=0; i<nPeople; i++) {
printf ("%-*s Buys For %s\n",
(shorter ? 10 : 50), person, person[buysFor]);
if (!shorter)
printf ("\n\n"
"-------------------------------------------------------\n"
"\n\n");
}

return 0;
}

--------------010504010903070701040200--

 

[James Edward Gray II]

It also supports additional constraints such as MustByFor (added the
year Aunt Helen said she found the perfect gift for cousin Josiah and
could I "arrange" the list so that she could give his gift) and
MustNotBuyFor (added when Aunt Mary said if she got Uncle John (a
particularly difficult person to buy for) one more year in a row, she
would have my head). Oh, and I swear that the year Uncle Pat got the
exploding gift from me, it wasn't pre-arranged. Honestly!

Oh, if we're sharing great Secret Santa stories now, maybe I should
talk about last year when my wife and my best friend gave each other
viruses as their gifts.

Seriously, thanks a lot for the post Jim. It was educational and
laugh-out-loud funny at the same time!

James Edward Gray II

 

[Cedric Foll]

Hi,

these is my solution.
In order to solve the problem I've proceed like that:
-Start to compute all permutations possibles of emails addresses
-Remove all of them where there is a couple of persons in the same family.
-Return, randomly, one of the permutations.

Example:
$ ./santa.rb < friends
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>
<[email protected]> -> <[email protected]>


This is the script:

#!/usr/bin/ruby

class Friends
attr_reader :email, :family, :nb
def initialize
@email = Hash.new
@members=0
@nb = []
end
def add (first_name,family_name,mail)
@email[mail] = family_name
@nb[@members] = mail
@members += 1
end
end
# compute all permutation in a list
def permute(items, perms=[], res=[])
unless items.length > 0
res << perms
else
for i in items
newitems = items.dup
newperms = perms.dup
newperms.unshift(newitems.delete(i))
permute(newitems, newperms,res)
end
end
return res
end

friends = Friends.new
while line = gets
friends.add(*line.split(' '))
end
perms = permute(friends.email.keys)
perms.reject!{|tab|
res = false
for i in 0..tab.length-1
if friends.email[tab] == friends.email[friends.nb]
# same family
res = true
end
end
res
}
res = perms[rand(perms.length)]
for i in 0..res.length-1
puts "#{friends.nb} -> #{res}"
end

 

[Thomas Leitner]

On Mon, 4 Oct 2004 07:19:57 +0900

| On Oct 3, 2004, at 8:04 AM, Thomas Leitner wrote:
|
| > And here is my version of the second quiz. It does not use
| > 'net/smtp' but shows the chosen santas on the console.
| >
| > Thomas
|
| Did you run this program on the provided test data?
|
| I believe it has the same catch in it I posted about in Robo's code
| earlier today, though it displays it differently. If I run it 10 or
| 20 times, it eventually hangs on me.
|
| James Edward Gray II
|
|
|

Yes, I did this. I have run the program 10000 times now and it never hung on me or produced false answers. I'm using

[penguin 42] ~ > ruby -v
ruby 1.8.1 (2004-04-24) [i686-linux-gnu]

Hmm, I just configured my system to use ruby 1.9

[penguin 110] ~ > ruby -v
ruby 1.9.0 (2004-08-03) [i686-linux]

and now it also began to hang...

.... busy working ...

So, after having this message open in my editor for too long now, it "seems" I have found the problem. I changed the lines

def choose_santas( list )
list.each do |person, possible_santas|
begin santa = possible_santas[rand( possible_santas.length )] end until verify_santa( list, person, santa )
list.each_value { |value| value.delete( santa ) if Array === value }
list[person] = santa
end
end

to this

def choose_santas( list )
list.each do |person, possible_santas|
begin
santa = possible_santas[rand( possible_santas.length )]
end until verify_santa( list, person, santa )
list.each_value { |value| value.delete( santa ) if Array === value }
list[person] = santa
end
end

(the 'begin' ... 'end until' statements are on separate lines) and now the program also runs 10000 times

Bad thing about it: I don't really know why it works now :-(

Thomas

 

[James Edward Gray II]

Yes, I did this. I have run the program 10000 times now and it never
hung on me or produced false answers. I'm using

[penguin 42] ~ > ruby -v
ruby 1.8.1 (2004-04-24) [i686-linux-gnu]

I'm using ruby 1.8.2pre2 on Mac OS X.

Hmm, I just configured my system to use ruby 1.9

[penguin 110] ~ > ruby -v
ruby 1.9.0 (2004-08-03) [i686-linux]

and now it also began to hang...

.... busy working ...

So, after having this message open in my editor for too long now, it
"seems" I have found the problem. I changed the lines

def choose_santas( list )
list.each do |person, possible_santas|
begin santa = possible_santas[rand( possible_santas.length )] end
until verify_santa( list, person, santa )
list.each_value { |value| value.delete( santa ) if Array === value
}
list[person] = santa
end
end

I made the change you gave, and reran my tests. It still hung. I went
directly to your program and ran it manually, instead of through my
testing harness. It hung on the 19th attempt. All runs are using the
data set from the quiz.

I've tried to follow the logic in you're code and I believe I
understand the problem. Basically, you verify at each step that santa
selection is valid, but that doesn't always account for future steps.
Example, (with quiz data set):

Luke Skywalker gets Virgil Brigman for a santa
Your script validates this choice,
then removes Virgil from all possible santa lists.
Leia Skywalker gets Lindsey Brigman for a santa
Your script validates this choice,
then removes Lindsey from all possible santa lists.
Virgil Brigman gets Luke Skywalker for a santa
Your script validates this choice,
then removes Luke from all possible santa lists.
Lindsey Brigman gets Leia Skywalker for a santa
Your script validates this choice,
then removes Leia from all possible santa lists.
Bruce Wayne gets Gus Portokalos for a santa
Your script validates this choice,
then removes Gus from all possible santa lists.
Gus Portokalos gets Bruce Wayne for a santa
Your script validates this choice,
then removes Bruce from all possible santa lists.

The above step is where the trap is set. Bruce was the last valid name
in Toula Portokalos' possible santa list and he has now been removed.
That list is empty. Your script tries a final match for Toula, and
loops infinitely over an empty list since verify_santa() will never
return true now.

I hope that helps, but I'll apologize in advance if I'm
misunderstanding your algorithm.

James Edward Gray II

 

[Thomas Leitner]

On Wed, 6 Oct 2004 03:28:37 +0900

| On Oct 5, 2004, at 11:44 AM, Thomas Leitner wrote:
|
| > Yes, I did this. I have run the program 10000 times now and it never
| >
| > hung on me or produced false answers. I'm using
| >
| > [penguin 42] ~ > ruby -v
| > ruby 1.8.1 (2004-04-24) [i686-linux-gnu]
|
| I'm using ruby 1.8.2pre2 on Mac OS X.
|
| > Hmm, I just configured my system to use ruby 1.9
| >
| > [penguin 110] ~ > ruby -v
| > ruby 1.9.0 (2004-08-03) [i686-linux]
| >
| > and now it also began to hang...
| >
| > .... busy working ...
| >
| > So, after having this message open in my editor for too long now, it
| >
| > "seems" I have found the problem. I changed the lines
| >
| > def choose_santas( list )
| > list.each do |person, possible_santas|
| > begin santa = possible_santas[rand( possible_santas.length )]
| > end
| > until verify_santa( list, person, santa )
| > list.each_value { |value| value.delete( santa ) if Array ===
| > value
| > }
| > list[person] = santa
| > end
| > end
|
| I made the change you gave, and reran my tests. It still hung. I
| went directly to your program and ran it manually, instead of through
| my testing harness. It hung on the 19th attempt. All runs are using
| the data set from the quiz.
|
| I've tried to follow the logic in you're code and I believe I
| understand the problem. Basically, you verify at each step that santa
|
| selection is valid, but that doesn't always account for future steps.
|
| Example, (with quiz data set):
|
| Luke Skywalker gets Virgil Brigman for a santa
| Your script validates this choice,
| then removes Virgil from all possible santa lists.
| Leia Skywalker gets Lindsey Brigman for a santa
| Your script validates this choice,
| then removes Lindsey from all possible santa lists.
| Virgil Brigman gets Luke Skywalker for a santa
| Your script validates this choice,
| then removes Luke from all possible santa lists.
| Lindsey Brigman gets Leia Skywalker for a santa
| Your script validates this choice,
| then removes Leia from all possible santa lists.
| Bruce Wayne gets Gus Portokalos for a santa
| Your script validates this choice,
| then removes Gus from all possible santa lists.
| Gus Portokalos gets Bruce Wayne for a santa
| Your script validates this choice,
| then removes Bruce from all possible santa lists.
|
| The above step is where the trap is set. Bruce was the last valid
| name in Toula Portokalos' possible santa list and he has now been
| removed. That list is empty. Your script tries a final match for
| Toula, and loops infinitely over an empty list since verify_santa()
| will never return true now.

Yeah, you're right! I think I will invest more time next time in a good unit test Thanks for your help!

Thomas