From: James Edward Gray II <james@...>
Date: 2004-10-06T03:28:37+09:00
Subject: Re: [SOLUTION] Secret Santas (#2)

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.

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

James Edward Gray II