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

# [QUIZ] Secret Santas (#2)

Joe Cheng
Guest
Posts: n/a

 10-03-2004
> Hmm, maybe I'm not awake yet this morning, but to me the solution seems
> impossible from the start, by definition. The 5 Skywalkers need to be
> santas for non-Skywalkers, of which there are only 4 choices. I can't
> make that work out, but please correct me if I'm wrong.

Ahh, you're both totally right. I didn't do a check on the
last-to-first relationship. I guess it's me who's not awake yet

James Edward Gray II
Guest
Posts: n/a

 10-03-2004
On Oct 3, 2004, at 10:09 AM, Gavin Kistner wrote:

> Very nice, Robo. Whenever I've thought of "random except for ____"
> type solutions, I've never gotten beyond thinking of "keep picking
> random items until you meet the criteria" (which is a dumb way to go
>
> Filtering the pool is quite nice.

But does it work? I chose the test data after much thought.

My second run (it may take multiple tries):

% ruby Robo.rb < quiz_data.txt
Luke Skywalker is watching over Toula Portokalos
Leia Skywalker is watching over Gus Portokalos
Toula Portokalos is watching over Luke Skywalker
Gus Portokalos is watching over Lindsey Brigman
Bruce Wayne is watching over Leia Skywalker
Virgil Brigman is watching over Bruce Wayne
Lindsey Brigman is watching over nobody

Note the last line. Then examine the earlier lines to figure out why...

James Edward Gray II

Dennis Ranke
Guest
Posts: n/a

 10-03-2004
Hi!

I didn't have the time to implement a complete solution, but at least I'd
like to show my algorithm for assigning the santas.
I start by assigning a random santa to everyone without caring about the
constraints. Then I go through the list of people and for each one not
having a correct santa I swap santas with someone else, so that both have
correct santas afterwards.
As far as I can see, this will only fail when no solution is possible and
should be reasonably unbiased.

Here is the code:

class Person
attr_accessor :santa

def initialize(line)
m = /(\S+)\s+(\S+)\s+<(.*)>/.match(line)
raise unless m
@first = m[1].capitalize
@last = m[2].capitalize
@email = m[3]
end

def can_be_santa_of?(other)
@last != other.last
end
end

people = []
input.each_line do |line|
line.strip!
people << Person.new(line) unless line.empty?
end

santas = people.dup
people.each do |person|
person.santa = santas.delete_at(rand(santas.size))
end

people.each do |person|
unless person.santa.can_be_santa_of? person
candidates = people.select {|p| p.santa.can_be_santa_of?(person) &&
person.santa.can_be_santa_of?(p)}
raise if candidates.empty?
other = candidates[rand(candidates.size)]
temp = person.santa
person.santa = other.santa
other.santa = temp
finished = false
end
end

people.each do |person|
printf "%s %s -> %s %s\n", person.santa.first, person.santa.last,
person.first, person.last
end

--
exoticorn/farbrausch

Gavin Kistner
Guest
Posts: n/a

 10-03-2004
On Oct 3, 2004, at 9:09 AM, Gavin Kistner wrote:
> Hrm, which gives me a good idea for my Ouroboros#separate_duplicates
> method; currently if I find a family duplicate I just swap the second
> one with it's following neighbor, and either hope that it's not the
> same family or wait until the next pass in the loop to fix that one. I
> suspect I would get much quicker sorting if I 'filtered' the
> pool...search ahead for the next person who isn't in the same family
> and swap them.
>
> That smells like it should be an O(n) performer, rather than ~O(n^2).

Indeed, with 3072 people in the pathological case (where half are one
family, one quarter another, one eighth another, etc.) the above
optimization brings the time down to 20 seconds, instead of 254 seconds
using the code I originally created

I've updated Ouroboros.rb to reflect the new, more efficient code.
For the overly-curious who want to see the slow code, the new and old
methods are below (with irrelevant bits trimmed out).

def separate_duplicates!
max_crawls = @size*@size
keys = {}
@all.each{ |list_item|
keys[list_item] = block_given? ? yield(list_item) : list_item
}

crawls=0
dup_distance = 0
while dup_distance < @size && (crawls < max_crawls)
if keys[@current] == keys[@current.next]
dup_distance = 0
n = 1
begin; swapper = self[n+=1]; end until (keys[@current] !=
keys[swapper]) || (n==@size)
self.swap( @current.next, swapper )
else
dup_distance += 1
end
self.increment
crawls+=1
end
raise "Error: #separate_duplicates! was unsuccessful after
#{crawls} rounds." if dup_distance < @size
self
end

def separate_duplicates_old!
#...
while dup_distance < @size && (crawls < max_crawls)
if keys[@current] == keys[@current.next]
dup_distance = 0
self.swap( @current.next, self[2] )
else
dup_distance += 1
end
self.increment
crawls+=1
end
#...
end

Joe Cheng
Guest
Posts: n/a

 10-03-2004
Fixed my solution to check for tail and head being in same family, and
also add a sorting "bonus" to the family of the head to ensure that
condition doesn't arise if it doesn't have to.

---

# Represents a family.
class Family

def initialize(name)
@name = name
@members = []
@bonus = 0
end

# Number of people in family.
def count
@members.length
end

# Give a sorting bonus--a family with
# the bonus will always appear before
# any families with the same count but
# no bonus
def give_bonus
@bonus = 0.1
end

# The count with sorting bonus included
def count_with_bonus
count + @bonus
end

# Pop the last member off.
def pop
@members.pop
end

# Compare by count/bonus.
def <=>(other)
count_with_bonus <=> other.count_with_bonus
end
end

class Person

def initialize(first_name, last_name, email)
@first_name = first_name
@last_name = last_name
@email = email
end

def to_s
"#{@first_name} #{@last_name} <#{@email}>"
end
end

familyTable = Hash.new {|h,k| h[k] = Family.new(k)}

while line = gets
line =~ /(\w+) (\w+) <(.+)>/
first, last, email = \$1, \$2, \$3

familyTable[last].members << Person.new(first, last, email)
end

puts
puts "Processing..."

families = familyTable.values
santas = []

while families.length > 0

families.sort!.reverse!

if families.first.count == 0
# nobody is left; we're done
break
end

if santas.length == 0
# for the very first santa, choose someone from
# the largest family
santas << families.first.pop
families.first.give_bonus
else
success = false

# find largest family that is not one's own
families.each do |family|
if family.name != santas.last.last_name
santas << family.pop
success = santas.last
break
end
end

raise "No solution." unless success
end
end

if santas.length > 0 && santas.first.last_name == santas.last.last_name
raise "No solution."
end

puts "Success!"
puts

lastSanta = santas.last
santas.each do |santa|
puts santa.to_s + " => " + lastSanta.to_s
lastSanta = santa
end

Joe Cheng
Guest
Posts: n/a

 10-03-2004
Gavin Kistner wrote:
> Indeed, with 3072 people in the pathological case

Hey Gavin, do you mind e-mailing that test data to <(E-Mail Removed)>?
I'm feeling lazy.

Martin Ankerl
Guest
Posts: n/a

 10-03-2004
# This implementation is heavily optimized to be as fast to
# carefull I have tried to find an implementation
# that is as simple to understand as possible, but does work.
require 'net/smtp'

Person = Struct.new("Person", :firstName, :familyName, :email)

# extract people from input stream
santas = Array.new
santas.push Person.new(first, family, email)
end
santas
end

# get an ordering where each santa gets a person who is
# outside his family. This implementation is extremely simple,
# as it assumes it is always possible to find a correct solution.
# Actally it is so simple that it hurts. I would never use this
# in production-level code.
def orderPeople(santas)
isCorrectlyOrdered = false
while !isCorrectlyOrdered
# get a random order
people = santas.sort_by { rand }

# check if the random order does meet the requirements
i = 0
i += 1 while i<santas.size &&
santas[i].familyName==people[i].familyName
isCorrectlyOrdered = i<santas.size
end
people
end

# send santa a mail that he/she is responsible for person's presents
def sendMail(santa, person)
msg = ["Subject: Santa news", "\n",
"You are santa for #{person.firstName} #{person.familyName}" ]

Net::SMTP.start("localhost") do |smtp|
smtp.sendmail(msg, "santa delegator", santa.email)
end
end

if __FILE__ == \$0
people = orderPeople(santas)

santas.each_index do |i|
santa = santas[i]
person = people[i]
puts "'#{santa.firstName} #{santa.familyName}' is santa for
'#{person.firstName} #{person.familyName}'"
# if you really want to send mails, uncomment the following
line.
#sendMail(santa, person)
end
end

Gavin Kistner
Guest
Posts: n/a

 10-03-2004
On Oct 3, 2004, at 10:59 AM, Joe Cheng wrote:
> Gavin Kistner wrote:
>> Indeed, with 3072 people in the pathological case

>
> Hey Gavin, do you mind e-mailing that test data to
> <(E-Mail Removed)>? I'm feeling lazy.

See the ZecretZanta#simulate_participants method in
http://phrogz.net/RubyLibs/quiz/2/ZecretZanta.rb

--
(-, /\ \/ / /\/

Roeland Moors
Guest
Posts: n/a

 10-03-2004
Here is my solution.
It doesn't mail and I look for a radom santa until I get a
working combination.

# list of persons
\$list = []

# generate list of candidates for santas
def get_candidates(person)
cans = []
\$list.each do |p|
cans.push p unless
(p == person) ||
(p['last'] == person['last']) ||
(p['santa'] != -1)
end
cans
end

# get persons
while input = gets
person = Hash.new
person['first'], person['last'], person['mail'] = input.split
person['santa'] = -1
\$list.push person
end

# seek santa
def seek_santa
index = 0
wrong = false
\$list.each do |person|
candidates = get_candidates(person)
wrong = true if candidates.length == 0
return wrong if wrong
r = rand(candidates.length)
c = candidates[r]
\$list.find { |p| p == c }['santa'] = index
index += 1
end
wrong
end

print '.' while !seek_santa
puts '.'

# display solution
\$list.each do |person|
s = \$list[person['santa']]
puts "#{person['first']} #{person['last']} -> #{s['first']} #{s['last']}"
end

Gavin Kistner
Guest
Posts: n/a

 10-03-2004
On Oct 3, 2004, at 9:54 AM, James Edward Gray II wrote:
> \$santas = \$players.sort_by { rand } until check_families?

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

With the pathological case (where half the people are in the same
family) I think[1] that the chances of randomly picking a working
layout for pool size N are

N * ((N/2)-1)! / (N-1)!

If so, the chances of picking a working layout each time for a total
pool of 4 people is 66.66%, the chances for a pool of 6 people is 10%,
8 => 0.95%, 10 => .066%, and so on.

If my calculations are correct, by the time you reach 10 people in one
family and 10 other participants, your chance of picking a working case
drops to 6 in 100000000000. That's gotta take a long time to find a
correct layout.

Perhaps my math is wrong, your test case small, your computer really
fast, or your test case not pathological

- Gavin

[1] Statistics is not my strong suit. My reasoning is as follows:
Consider a pool of 6 participants:
Joe Smith
Jane Smith
Jim Smith
Bob Dole
Barbara Bush
Bill Clinton

The correct arrangement for this pathological case is an interleaving
of Smiths and others, for example:
Jane Smith
Bill Clinton
Joe Smith
Bob Done
Jim Smith
Barbara Bush

There is a 1/1 chance that SOMEONE will be picked for the first spot.
There is a 3/5 chance that the next person will be of the opposite
Smith/Non-Smith persuasion.
There is a 2/4 chance that the next person will be of the opposite
Non-Smith/Smith persuasion.
There is a 2/3 chance for the next.
There is a 1/2 chance for the next.
There is a 1/1 chance for the last.
The cumulative chance of all that occurring is the product:
3/5 * 2/4 * 2/3 * 1/2 = 1/10

For an 8 person pool, the chances are:
4/7 * 3/6 * 3/5 * 2/4 * 2/3 * 1/2 = 1/35
Re-arranged, that looks like:
(4*3*3*2*2) / (7*6*5*4*3*2 )
which is
(4 * 3*2 * 3*2 ) / ( 7*6*5*4*3*2 )
which is
(4 * 2 * 3! ) / 7!

Looking at this pattern, then, the chances of randomly picking a
working pattern for pathological pool size of N seems to be:

N/2 * 2 * ((N/2)-1)! / (N-1)! == N * ((N/2)-1)! / (N-1)!

Or, in Ruby:

class Fixnum; def factorial; t=1; 2.upto(self.to_i){ |i| t*=i }; t;
end; end

def chances( pool_size )
pool_size.to_f * (pool_size/2-1).factorial / (pool_size-1).factorial
end

40.times{ |i|
next if i%2==1;
puts "#{i} => #{chances i}"
}
0 => 0.0
2 => 2.0
4 => 0.666666666666667
6 => 0.1
8 => 0.00952380952380952
10 => 0.000661375661375661
12 => 3.60750360750361e-05
14 => 1.61875161875162e-06
16 => 6.1666728333395e-08
18 => 2.04044321691381e-09
20 => 5.96620823659007e-11
22 => 1.56257834767835e-12
24 => 3.70571940160874e-14
26 => 8.02905870348561e-16
28 => 1.60123677847291e-17
30 => 2.95794971392779e-19
32 => 5.08894574439191e-21
34 => 8.19243159608545e-23
36 => 1.23919133386167e-24
38 => 1.76761526601889e-26

(The 2.0 in the case of a pool size of 2 reflects that there are two
correct cases, I think. Or perhaps it reflects the fact that my math is
overly generous by a factor of 2