[QUIZ] Secret Santas (#2)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.grayproductions.net/ruby_quiz/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Honoring a long standing tradition started by my wife's dad, my friends all play
a Secret Santa game around Christmas time. We draw names and spend a week
sneaking that person gifts and clues to our identity. On the last night of the
game, we get together, have dinner, share stories, and, most importantly, try to
guess who our Secret Santa was. It's a crazily fun way to enjoy each other's
company during the holidays.

To choose Santas, we use to draw names out of a hat. This system was tedious,
prone to many "Wait, I got myself..." problems. This year, we made a change to
the rules that further complicated picking and we knew the hat draw would not
stand up to the challenge. Naturally, to solve this problem, I scripted the
process. Since that turned out to be more interesting than I had expected, I
decided to share.

This weeks Ruby Quiz is to implement a Secret Santa selection script.

Your script will be fed a list of names on STDIN. An example might be:

Luke Skywalker <[email protected]>
Leia Skywalker <[email protected]>
Toula Portokalos <[email protected]>
Gus Portokalos <[email protected]>
Bruce Wayne <[email protected]>
Virgil Brigman <[email protected]>
Lindsey Brigman <[email protected]>

Note: If you cannot tell, I made those addresses up and you'll need to replace
them with something meaningful. Please don't pester those people, should they
happen to be real.

The format for these names is:

FIRST_NAME space FAMILY_NAME space <EMAIL_ADDRESS> newline

We'll keep things simple and say that people only have two names, so you don't
have to worry about tricky names like Gray II.

Your script should then choose a Secret Santa for every name in the list.
Obviously, a person cannot be their own Secret Santa. In addition, my friends
no longer allow people in the same family to be Santas for each other and your
script should take this into account.

Output is obvious. E-mail the Santa and tell them who their person is.

The extra credit for this quiz is to convince all your friends how much fun this
can really be, so you can put your script to good use. Go forth spreading
holiday cheer into the world!

 

[Moses Hohman]

Hi James,

What should the script do if there is no solution for the input set,
e.g. the set is two people in the same family?

Moses

 

[James Edward Gray II]

Hi James,

What should the script do if there is no solution for the input set,
e.g. the set is two people in the same family?

Egad, knew I forgot to mention something! My bad, sorry. Told ya'll I
still need some breaking in at quiz writing. <laughs>

I will only feed your script valid combinations, so if you don't want
to worry about it, don't. If you do want to build in a sanity check, a
simple error message should be fine. Handle it however you are
comfortable.

James Edward Gray II

 

[Moses Hohman]

No worries, I probably should have figured that out for myself anyway,
but I felt like asking.

 

[Gavin Kistner]

Your script will be fed a list of names on STDIN.

I've never worked with STDIN before; does this mean a single call to
#gets will return a newline-delimited list of names, or I should loop
calls to #gets until it returns nil?

 

[Florian Gross]

I've never worked with STDIN before; does this mean a single call to
#gets will return a newline-delimited list of names, or I should loop
calls to #gets until it returns nil?

STDIN and ARGF are both IOs. STDIN reads from the standard input. ARGF
reads from the standard input and file names that are in ARGV.

IO#gets returns one line with a \n at the end or nil when there are no
more lines available.

There's also IO#read which returns the whole file as a String and
IO#readlines which returns the whole file as an Array of lines. (Each
with a \n at the end.)

Regards,
Florian Gross

 

[Joe Cheng]

Output is obvious. E-mail the Santa and tell them who their person is.

Will you accept solutions that just print out the e-mails instead of
sending them?

 

[James Edward Gray II]

Will you accept solutions that just print out the e-mails instead of
sending them?

Why? Are you not yet familiar with "net/smtp"? It's a standard lib,
so this is a good excuse to learn it and it's surprisingly simple...


There's no right and wrong answers to a Ruby Quiz. The goal is to
think, learn and have a little fun. Submit whatever does that for you.

James Edward Gray II

 

[Robo]

I'm still new to Ruby, but giving this a crack anyway.

I could have made more classes to model the problem better, but didn't
bother. Everything's done by a Hat with higher intelligence than regular
hats (that doesn't deserve a capital H).

To run, type "ruby santa.rb", then enter each person's name and email in
the format specified. When you're done the script tells you the result
of the selection.

The email part is a bit rogue, but that's just a matter of creating a
more comprehensive email message. It's disabled by default, just
uncomment the lines in Hat#notify.

It doesn't take into account of creating loops smaller than total number
of people. i.e. If there're 4 people, 3 of them maybe Secret Santas of
each other, leaving one stranded.

Robo

require 'net/smtp'

#a very smart Hat that even knows how to email
class Hat

#represents a member of the Christmas gathering
Member = Struct.newfirstName, :lastName, :email, :minion)

def initialize
@members = []
@pool = []
end

#put a new member into the hat
def put(firstName, lastName, email)
member = Member.new(firstName, lastName, email)
@members << member
@pool << member
end

#match each Secret Santa to a person
def match
@members.each do |santa|
santa.minion = draw(santa)
notify(santa)
end
end

#draw a person out of the hat for a Secret Santa
def draw(santa)
validPool = filter(santa)
person = validPool.at(rand(validPool.size))
@pool.delete(person)
end

#filter out people who're in the same family as Secret Santa
def filter(santa)
@pool.select do |member|
member.lastName != santa.lastName
end
end

#notify each Secret Santa who they'll be watching over
def notify(santa)
if santa.minion != nil
msg = "#{santa.firstName} #{santa.lastName} is watching over " +
"#{santa.minion.firstName} #{santa.minion.lastName}"
else
msg = "#{santa.firstName} #{santa.lastName} is watching over nobody"
end

puts msg

#Net::SMTP.start('smtp.example.com', 25) do |smtp|
# smtp.send_message(msg, '(e-mail address removed)', santa.email)
#end
end
end

def main
h = Hat.new
while (s = gets()) != nil
s.scan(/^(.*?) (.*?) <(.*?)>$/) do |firstName, lastName, email|
h.put(firstName, lastName, email)
end
end
h.match
end

if __FILE__ == $0
main
end

 

[Thomas Leitner]

And here is my version of the second quiz. It does not use 'net/smtp' but shows the chosen santas on the console.

Thomas


-----------------------------------------------
#!/usr/bin/env ruby

Person = Struct.new( :first, :last, :email )

# Parses one line and extract the data items
def parse_name( name )
person = Person.new( *name.split[0..2] )
if person.first.nil? || person.last.nil? || person.email.nil?
puts "Invalid input: #{name.inspect}"
exit
end
return person
end

# Reads lines from the given IO object and returns a Hash with all persons as keys
def parse_names( io )
list = {}
list[parse_name( STDIN.readline )] = nil until io.eof
return list
end

# Associates each person with a list of possibile Santas
def build_santa_lists( list )
list.each_key do |person|
possible_santas = list.keys
possible_santas.reject! { |other_person| other_person.last == person.last }
list[person] = possible_santas
end
end

# A Santa is correct if there is no other person for whom only the selected Santa is left
def verify_santa( list, person, santa )
list.each do |key, value|
return false if key != person && value == [santa]
end
return true
end

# Choose a Santa for each person
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

# Mail the Santas which person they have got
def mail_santas( list )
list.each do |person, santa|
santa = Person.new('<no valid santa found>', '', '') if santa.nil?
puts "Santa #{santa.first} #{santa.last} #{santa.email} for #{person.first} #{person.last} #{person.email}"
end
end

list = parse_names( STDIN )
build_santa_lists list
choose_santas list
mail_santas list

 

[Gavin Kistner]

My solution to the Quiz #2 is at http://phrogz.net/RubyLibs/quiz/2/

The general approach is:
a) Create a randomized array of Person objects (having parsed the
input).
b) Turn the array into a circular list, and separate any adjacent
family members.
c) Send email (or, if $DEBUG is set, spit out a message), treating
adjacent pairs in the list as giver/receivers.

I initially wrote it treating the array as a circular list, but then
decided I wanted a real circular list class. It's not well tested yet,
but if you like, the Ouroboros class I created is free for the horking.
(It's in the above url, as well as documented and available in main
http:/phrogz.net/RubyLibs/)

I thought I had a better, less-hackish solution than the
pseduo-bubble-sort method I used to separate adjacent duplicates. I
sorted people into family bins, randomized the families, and then
pulled people out from one bin at a time. The benefit was supposed to
be better family separation (to limit occurrances of John Doe from
giving to Bob Smith who gave right back to Jane Doe). Unfortunately, I
didn't think of the case of a single many-member family overpowering
the pool, where early even distribution ends up with only members from
that family left at the end.

I was thinking about weighting my choices by the number of people in
each bin, but since the above solution works, I decided to scrap it.


The interesting thing about this quiz is...my extended family does the
same thing, and up until now no one had thought to automate the
no-same-family rule. The list of members was randomized in excel (much
like Ruby: sort names by an adjacent random number column) and then the
list manually massaged to ensure no family members were adjacent.

I'd never worked with STDIN or SMTP before, so this was a great
exercise for me. Looking forward to looking through other's solutions.
Thanks again for a fun quiz!

 

[Gavin Kistner]

#filter out people who're in the same family as Secret Santa
def filter(santa)
@pool.select do |member|
member.lastName != santa.lastName
end
end

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 about
it).

Filtering the pool is quite nice.

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

 

[Joe Cheng]

My solution first divides people into their families. I build up a list
of santas (where each person gives to the next in the list, and the tail
gives to the head) by:

1) For the first santa, choose from the family with the most people.
2) For all other santas, choose from the family with the most remaining
people that is not the family of the last santa.

I wasn't able to think of any situations that would thwart this strategy.

I, too, just print out the names at the console instead of e-mailing.
And there is also nothing random about my strategy, so given the same
input you will always get the same output. It would be a simple matter
to shuffle the members within the families though; that would mix things
up a little.

Note to other submitters, the following is a good edge case to test:

Luke1 Skywalker <[email protected]>
Luke2 Skywalker <[email protected]>
Luke3 Skywalker <[email protected]>
Luke4 Skywalker <[email protected]>
Leia Skywalker <[email protected]>
Toula Portokalos <[email protected]>
Gus Portokalos <[email protected]>
Bruce Wayne <[email protected]>
Virgil Brigman <[email protected]>

---

# Represents a family.
class Family
attr_reader :name, :members

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

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

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

# Compare by size.
def <=>(other)
count <=> other.count
end
end

class Person
attr_reader :first_name, :last_name, :email

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

puts "Success!"
puts

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

 

[ts]

J> Luke1 Skywalker <luke@_______.___>

Please, stop to post *valid* domain name

Thanks,


Guy Decoux

 

[Joe Cheng]

Note to other submitters, the following is a good edge case to test:

Luke1 Skywalker <[email protected]>
Luke2 Skywalker <[email protected]>
Luke3 Skywalker <[email protected]>
Luke4 Skywalker <[email protected]>
Leia Skywalker <[email protected]>
Toula Portokalos <[email protected]>
Gus Portokalos <[email protected]>
Bruce Wayne <[email protected]>
Virgil Brigman <[email protected]>

I thought it might be a good idea for me to explain exactly what is
interesting about this test case. There are 5 Skywalkers and 4
non-Skywalkers. So the moment a non-Skywalker is assigned to another
non-Skywalker, a solution is impossible.

(Gavin, your solution warned me that the input contained duplicate
e-mails... nice!)

 

[James Edward Gray II]

J> Luke1 Skywalker <luke@_______.___>

Please, stop to post *valid* domain name

This was my fault, originally. I should have checked them before I
posted and I didn't. My apologies. I'll be more careful in the
future.

James Edward Gray II

 

[Joe Cheng]

J> Luke1 Skywalker <luke@_______.___>

Please, stop to post *valid* domain name

Oops, sorry...!

I hope nobody's solutions are actually sending e-mails by default...

 

[Gavin Kistner]

Luke1 Skywalker <[email protected]>
Luke2 Skywalker <[email protected]>
Luke3 Skywalker <[email protected]>
Luke4 Skywalker <[email protected]>
Leia Skywalker <[email protected]>
Toula Portokalos <[email protected]>
Gus Portokalos <[email protected]>
Bruce Wayne <[email protected]>
Virgil Brigman <[email protected]>

I think you need one other non-Skywalker, don't you?

If we arrange them so the each person 'gives' to the person below:

Luke1 Skywalker <[email protected]>
Toula Portokalos <[email protected]>
Luke2 Skywalker <[email protected]>
Gus Portokalos <[email protected]>
Luke3 Skywalker <[email protected]>
Bruce Wayne <[email protected]>
Luke4 Skywalker <[email protected]>
Virgil Brigman <[email protected]>
Leia Skywalker <[email protected]>

It all works until the end, when Leia is giving to Luke1.
(Otherwise, Leia doesn't give to anyone, and Luke1 receives from no
one.)

 

[James Edward Gray II]

I thought it might be a good idea for me to explain exactly what is
interesting about this test case. There are 5 Skywalkers and 4
non-Skywalkers. So the moment a non-Skywalker is assigned to another
non-Skywalker, a solution is impossible.

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.

James Edward Gray II

 

[James Edward Gray II]

I had to rewrite my solution, because the true program takes more
things into account than I mentioned in the quiz, but this is pretty
much a direct simplification.

I used a random sort, which of course, isn't at all elegant.

James Edward Gray II

#!/usr/bin/env ruby

require "net/smtp"

unless ARGV.size == 1
puts "Usage: #{$0} SMTP_SERVER\n"
exit
end

$players = STDIN.readlines.map { |line| line.chomp }
$santas = $players.sort_by { rand }

def check_families?
$players.each_with_index do |who, i|
return false if who[/\S+ </] == $santas[/\S+ </]
end
return true
end

$santas = $players.sort_by { rand } until check_families?

Net::SMTP.start(ARGV[0]) do |server|
$santas.each_with_index do |santa, i|
message = <<END_OF_MESSAGE
From: Secret Santa Script <[email protected]>
To: #{santa}
Subject: Secret Santa Pick

#{santa[/\S+/]}:

You have been chosen as the Secret Santa for #{$players}. Merry
Christmas.

Secret Santa Selection Script (by James)
END_OF_MESSAGE
begin
server.send_message(
message,
"(e-mail address removed)",
santa[(santa.index("<") + 1)...santa.index(">")] )
rescue
puts "A message could not be sent to #{santa}.\n#{$!}"
end
end
end

__END__