[QUIZ] Secret Santas (#2)

Discussion in 'Ruby' started by Ruby Quiz, Oct 1, 2004.

  1. Ruby Quiz

    Ruby Quiz Guest

    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 <>
    Leia Skywalker <>
    Toula Portokalos <>
    Gus Portokalos <>
    Bruce Wayne <>
    Virgil Brigman <>
    Lindsey Brigman <>

    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!
     
    Ruby Quiz, Oct 1, 2004
    #1
    1. Advertising

  2. Ruby Quiz

    Moses Hohman Guest

    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
     
    Moses Hohman, Oct 1, 2004
    #2
    1. Advertising

  3. On Oct 1, 2004, at 4:37 PM, Moses Hohman wrote:

    > 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
     
    James Edward Gray II, Oct 1, 2004
    #3
  4. Ruby Quiz

    Moses Hohman Guest

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

    On Oct 1, 2004, at 4:53 PM, James Edward Gray II wrote:

    > On Oct 1, 2004, at 4:37 PM, Moses Hohman wrote:
    >
    >> 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, Oct 2, 2004
    #4
  5. On Oct 1, 2004, at 6:50 AM, Ruby Quiz wrote:
    > 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?
    --
    (-, /\ \/ / /\/
     
    Gavin Kistner, Oct 2, 2004
    #5
  6. Gavin Kistner wrote:

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


    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
     
    Florian Gross, Oct 2, 2004
    #6
  7. Ruby Quiz

    Joe Cheng Guest

    > 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? :)
     
    Joe Cheng, Oct 2, 2004
    #7
  8. On Oct 2, 2004, at 5:09 PM, Joe Cheng wrote:

    >> 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? :)


    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...
    :D

    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
     
    James Edward Gray II, Oct 2, 2004
    #8
  9. Ruby Quiz

    Robo Guest

    [SOLUTION] Secret Santas (#2)

    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.new:)firstName, :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, '', 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
     
    Robo, Oct 3, 2004
    #9
  10. Re: [SOLUTION] Secret Santas (#2)

    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
     
    Thomas Leitner, Oct 3, 2004
    #10
  11. Re: [SOLUTION] Secret Santas (#2)

    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, Oct 3, 2004
    #11
  12. Re: [SOLUTION] Secret Santas (#2)

    On Oct 3, 2004, at 6:24 AM, Robo wrote:
    > #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).

    --
    (-, /\ \/ / /\/
     
    Gavin Kistner, Oct 3, 2004
    #12
  13. Ruby Quiz

    Joe Cheng Guest

    Re: [SOLUTION] Secret Santas (#2)

    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 <>
    Luke2 Skywalker <>
    Luke3 Skywalker <>
    Luke4 Skywalker <>
    Leia Skywalker <>
    Toula Portokalos <>
    Gus Portokalos <>
    Bruce Wayne <>
    Virgil Brigman <>

    ---

    # 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
     
    Joe Cheng, Oct 3, 2004
    #13
  14. Ruby Quiz

    ts Guest

    [OT] Re: [SOLUTION] Secret Santas (#2)

    >>>>> "J" == Joe Cheng <> writes:

    J> Luke1 Skywalker <luke@_______.___>

    Please, stop to post *valid* domain name

    Thanks,


    Guy Decoux
     
    ts, Oct 3, 2004
    #14
  15. Ruby Quiz

    Joe Cheng Guest

    Re: [SOLUTION] Secret Santas (#2)

    > Note to other submitters, the following is a good edge case to test:
    >
    > Luke1 Skywalker <>
    > Luke2 Skywalker <>
    > Luke3 Skywalker <>
    > Luke4 Skywalker <>
    > Leia Skywalker <>
    > Toula Portokalos <>
    > Gus Portokalos <>
    > Bruce Wayne <>
    > Virgil Brigman <>


    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!)
     
    Joe Cheng, Oct 3, 2004
    #15
  16. Re: [OT] Re: [SOLUTION] Secret Santas (#2)

    On Oct 3, 2004, at 10:23 AM, ts wrote:

    >>>>>> "J" == Joe Cheng <> writes:

    >
    > 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
     
    James Edward Gray II, Oct 3, 2004
    #16
  17. Ruby Quiz

    Joe Cheng Guest

    Re: [OT] Re: [SOLUTION] Secret Santas (#2)

    ts wrote:
    >>>>>>"J" == Joe Cheng <> writes:

    >
    >
    > 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...
     
    Joe Cheng, Oct 3, 2004
    #17
  18. Re: [SOLUTION] Secret Santas (#2)

    On Oct 3, 2004, at 9:19 AM, Joe Cheng wrote:
    > Luke1 Skywalker <>
    > Luke2 Skywalker <>
    > Luke3 Skywalker <>
    > Luke4 Skywalker <>
    > Leia Skywalker <>
    > Toula Portokalos <>
    > Gus Portokalos <>
    > Bruce Wayne <>
    > Virgil Brigman <>


    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 <>
    Toula Portokalos <>
    Luke2 Skywalker <>
    Gus Portokalos <>
    Luke3 Skywalker <>
    Bruce Wayne <>
    Luke4 Skywalker <>
    Virgil Brigman <>
    Leia Skywalker <>

    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.)
     
    Gavin Kistner, Oct 3, 2004
    #18
  19. Re: [SOLUTION] Secret Santas (#2)

    On Oct 3, 2004, at 10:29 AM, Joe Cheng wrote:

    > 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, Oct 3, 2004
    #19
  20. Re: [SOLUTION] Secret Santas (#2)

    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 <>
    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,
    "",
    santa[(santa.index("<") + 1)...santa.index(">")] )
    rescue
    puts "A message could not be sent to #{santa}.\n#{$!}"
    end
    end
    end

    __END__
     
    James Edward Gray II, Oct 3, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ara.T.Howard

    [SOLUTION] Secret Santas (#2)

    Ara.T.Howard, Oct 4, 2004, in forum: Ruby
    Replies:
    10
    Views:
    219
  2. Peter McMaster

    [SOLUTION] Secret Santas (#2)

    Peter McMaster, Oct 6, 2004, in forum: Ruby
    Replies:
    0
    Views:
    81
    Peter McMaster
    Oct 6, 2004
  3. Peter McMaster

    [SOLUTION] Secret Santas (#2)

    Peter McMaster, Oct 6, 2004, in forum: Ruby
    Replies:
    0
    Views:
    119
    Peter McMaster
    Oct 6, 2004
  4. Ruby Quiz

    [SUMMARY] Secret Santas (#2)

    Ruby Quiz, Oct 7, 2004, in forum: Ruby
    Replies:
    0
    Views:
    132
    Ruby Quiz
    Oct 7, 2004
  5. Ruby Quiz

    [QUIZ] Secret Agent 00111 (#94)

    Ruby Quiz, Sep 9, 2006, in forum: Ruby
    Replies:
    6
    Views:
    161
    Eric Torreborre
    Sep 21, 2006
Loading...

Share This Page