Re: Preferable Pairs (#165)

Ruby
1

This sounds a lot like the Stable Marriage Problem.

----- Original Message ----
From: Matthew M. [email protected]
To: ruby-talk ML [email protected]
Sent: Friday, June 6, 2008 12:43:43 PM
Subject: [QUIZ] Preferable Pairs (#165)

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

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can! (A
    permanent, new website is in the works for Ruby Q. 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 T. 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.