--0-257138940-12129367724882
Content-Type: text/plain; charset=us-ascii

In fact, this *is* the Stable Roommates problem.


----- Original Message ----
From: Matthew Moss <matthew.moss / gmail.com>
To: ruby-talk ML <ruby-talk / ruby-lang.org>
Sent: Friday, June 6, 2008 12:43:43 PM
Subject: [QUIZ] Preferable Pairs (#165)

------------------

The three rules of Ruby Quiz 2:

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 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

     <http://splatbang.com/rubyquiz/>.

3.  Enjoy!
Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.
------------------

## Preferable Pairs (#156)

Imagine a pairs tournament: a competition where every player partners up
with another for the duration of the tournament. Everyone plays in a pair
and wins or loses in a pair.

But everyone arrives individually, and only pairs up at the start. Every
player has preferences for a partner; your task is to try and optimize those
preferences as best as possible.

The input is a series of lines containing names, such as:

    David: Helen Vicki Joseph
    Helen: David Vicki Joseph
    Joseph: Vicki Helen David
    Vicki: David Helen Joseph

Each line represents the preferences of the first named player (i.e. before
the colon). That player's preferred parters are listed after the colon, in
order of preference (i.e. most preferred first, least preferred last).

The output of your code should be the pairings, one pair per line. For the
example above, your output should look like this:

    David Helen
    Joseph Vicki

If an odd number of people were provided at the start, then one person will
be left out. That person's name should be output alone on the last line.

What determines the best pairing? A score will be calculated for your output
against the input. For each player, the partner is found in the player's
ordered list, as an index. So, for the above example:

    David: 0
    Helen: 0
    Joseph: 0
    Vicki: 2

Each individual's score is then squared, then all are added together. Here,
the final score is 4. The _lower_ your score, the better the match.

-- 
Matthew Moss <matthew.moss / gmail.com>



      
--0-257138940-12129367724882--