Velocity Reviews > Ruby > [QUIZ] Secret Santas (#2)

# [QUIZ] Secret Santas (#2)

James Edward Gray II
Guest
Posts: n/a

 10-05-2004
On Oct 4, 2004, at 7:31 PM, Jim Weirich wrote:

> 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

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
Guest
Posts: n/a

 10-05-2004
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
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>
<(E-Mail Removed)> -> <(E-Mail Removed)>

This is the script:

#!/usr/bin/ruby

class Friends
def initialize
@email = Hash.new
@members=0
@nb = []
end
@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
end
perms = permute(friends.email.keys)
perms.reject!{|tab|
res = false
for i in 0..tab.length-1
if friends.email[tab[i]] == friends.email[friends.nb[i]]
# same family
res = true
end
end
res
}
res = perms[rand(perms.length)]
for i in 0..res.length-1
puts "#{friends.nb[i]} -> #{res[i]}"
end

Thomas Leitner
Guest
Posts: n/a

 10-05-2004
On Mon, 4 Oct 2004 07:19:57 +0900
James Edward Gray II <(E-Mail Removed)> wrote:

| 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
Guest
Posts: n/a

 10-05-2004
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
then removes Virgil from all possible santa lists.
Leia Skywalker gets Lindsey Brigman for a santa
then removes Lindsey from all possible santa lists.
Virgil Brigman gets Luke Skywalker for a santa
then removes Luke from all possible santa lists.
Lindsey Brigman gets Leia Skywalker for a santa
then removes Leia from all possible santa lists.
Bruce Wayne gets Gus Portokalos for a santa
then removes Gus from all possible santa lists.
Gus Portokalos gets Bruce Wayne for a santa
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

James Edward Gray II

Thomas Leitner
Guest
Posts: n/a

 10-05-2004
On Wed, 6 Oct 2004 03:28:37 +0900
James Edward Gray II <(E-Mail Removed)> wrote:

| 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