[SUMMARY] Secret Santas (#2)

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

  1. Ruby Quiz

    Ruby Quiz Guest

    Please allow me a quick clarification, before I talk about this week's quiz.
    Joe Cheng asked:

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

    My answer to this is simply that you may submit whatever you like to a Ruby
    Quiz. There's no right and wrong answers here. However, when I define a
    specification in a quiz, that's what I'm prepared to benchmark, test and
    summarize. Please understand if I do not include altered solutions in those
    processes. (This has been added to the Ruby Quiz FAQ.)

    Let's move on to the problem at hand.

    As many have now pointed out, this problem is trickier than it first appears.
    The first solution that came to my mind when playing with this problem was
    simple:

    1. Choose a name from the list.
    2. Filter all matching surnames out of the Santa list.
    3. Assign a random Santa from the list in step 2, to the name in step 1.
    4. Repeat until all names are assigned...

    As I quickly learned, that doesn't quite work. The easiest way to see why it
    doesn't work is to consider three families, one member each:

    Skywalker can be assigned as a Santa for Portokalos.
    Portokalos can then be assigned as the Santa for Skywalker.
    And then we're stuck! There are no matches left for Brigman or whoever.

    Depending on how you implement the above, you'll probably get incorrect output
    or get stuck in an infinite loop at this point. That was when I personally
    began to take this problem seriously, and look at other options. Let's see what
    others found.

    The submitted solutions are more or less variations on three major themes:

    Random Sorts
    Circular Lists and/or Family Grouping
    "Hill Climbing" Algorithms

    Let's examine each of those in turn, starting with random sorts. Here's the
    code from my own submission that handles this:

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

    The idea there is simple, keep randomly shuffling $santas until we can verify
    that none of the match-ups share the same surname. That ensures no one will
    have themself or common family members, of course. This method does give us a
    good random shuffle of the match-ups, but unfortunately, the performance is far
    from stellar.

    Still, in a Secret Santa selection script, how critical is performance? This
    type of answer could be a viable solution in this case, though it usually isn't
    in the majority of "Real World" problems.

    The techniques in the second category of solutions, circular lists/family
    groupings, were quite varied. One solution built a circular linked list,
    separated family members in that list, and then assigned Santas straight down.
    Another tactic, used in more than one submission, was to separate the input into
    family groups, choose a member from the most populated family, and assign a
    Santa from the next highest populated family, until the list was exhausted.

    Algorithms like this are far more efficient that my random sort above,
    critically so in pathological cases. They do make a trade off though. These
    types of assignments are not unbiased and do not allow for all possible
    permutations of assignment. Consider this: in a circular list approach, it is
    impossible for two players of the game to be assigned to each other as Santas.
    That's not to say this is a minus of these algorithms, some groups may even
    prefer this behavior, but if you're looking for something quite random you
    probably need to look at little further.

    However, Niklas Frykholm submitted what I believe to be a variation of the
    family grouping theme that does produce unbiased matches. Here's the matching
    portion of his code:

    class Array
    def random_member(&block)
    return select(&block).random_member if block
    return self[rand(size)]
    end
    def count(&block)
    return select(&block).size
    end
    end

    class String
    def clean_here_string
    indent = self[/^\s*/]
    return self.gsub(/^#{indent}/, "")
    end
    end

    class Person
    attr_reader :first, :family, :mail
    def initialize(first, family, mail)
    @first, @family, @mail = first, family, mail
    end
    def to_s() "#{first} #{family} <#{mail}>" end
    end

    class AssignSanta
    def initialize(persons)
    @persons = persons.dup
    @santas = persons.dup
    @families = persons.collect {|p| p.family}.uniq
    @families.each { |f|
    if santa_surplus(f) < 0
    raise "No santa configuration possible"
    }
    end

    # Key function -- extra santas available for a family
    # if this is negative -- no santa configuration is possible
    # if this is 0 -- next santa must be assigned to this family
    def santa_surplus(family)
    return @santas.count {|s| s.family != family} -
    @persons.count {|p| p.family == family}
    end

    def call
    while @persons.size() > 0
    family = @families.detect { |f|
    santa_surplus(f)==0 and
    @persons.count{|p| p.family == f} > 0
    }
    person = @persons.random_member { |p|
    family == nil || p.family == family
    }
    santa = @santas.random_member{ |s|
    s.family != person.family
    }
    yield(person, santa)
    @persons.delete(person)
    @santas.delete(santa)
    end
    end
    end

    The exciting stuff is at the bottom, particularly the santa_surplus() method.
    Niklas' code tracks how many Santas are still available to all the families at
    each step and uses this information to avoid running out of options for future
    selections. But don't take my word for it, he posted a wonderful follow-up
    breakdown of exactly how it works to Ruby Talk:

    http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/114760

    The final type of solution was what is generally known as a "Hill Climbing"
    algorithm. Dennis Ranke explains his version nicely:

    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.

    Put another way, you start with a random and likely quite incorrect match-up,
    then correct it one swap at a time. Here's the code to match the description:

    class Person
    attr_reader :first, :last, :email
    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

    input = $stdin.read

    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

    Santas are randomly assigned in the first people.each() iteration above and then
    swapped until correct in the following people.each() iteration. I was surprised
    at how simple this solution came out, with such effective results.

    That's all I have time to cover, but that's certainly not all there is to see in
    the submitted solutions. I learn new tricks every time I read the code to put
    together one of these summaries. They're certainly worth a look, if you haven't
    given them one already. Other highlights include Warren Brown's rules based
    approach and Gavin Kistner's Ouroboros class for building circular lists, but
    again, I think all the solutions are worth examining.

    Before I wrap this up, let me congratulate Robo and Cristi BALAN who both
    claimed inexperience and promptly proved it false with working code. I singled
    Robo out in the discussion early on to hint at the quiz's complexity, but the
    truth is that his solution could work fine for the problem at hand. Who cares
    if you sometimes have to run it twice? I sure don't.

    My thanks to all who submitted and all those that just tolerate our babble on
    Ruby Talk. Look for Gavin's quiz tomorrow morning...
    Ruby Quiz, Oct 7, 2004
    #1
    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. Ruby Quiz

    [QUIZ] Secret Santas (#2)

    Ruby Quiz, Oct 1, 2004, in forum: Ruby
    Replies:
    54
    Views:
    461
    Thomas Leitner
    Oct 5, 2004
  2. Ara.T.Howard

    [SOLUTION] Secret Santas (#2)

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

    [SOLUTION] Secret Santas (#2)

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

    [SOLUTION] Secret Santas (#2)

    Peter McMaster, Oct 6, 2004, in forum: Ruby
    Replies:
    0
    Views:
    110
    Peter McMaster
    Oct 6, 2004
  5. Ruby Quiz
    Replies:
    0
    Views:
    134
    Ruby Quiz
    Sep 21, 2006
Loading...

Share This Page