Matthew Moss ha scritto:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> 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.
>
>   

Hi all,

this procedure *doesn't* find the *best* solution. Instead, it aims
to give *good* results in an acceptable time.

Here the pasties:

http://pastie.org/212099
http://pastie.org/212100 (specs)

= Description of the algorithm

1. Find all possible pairs

Given the following preferences matrix:

A: C D E F B
B: A C D F E
C: B A F E D
D: A B E F C
E: F D A B C
F: A B E D C

the first step is to find all possible pairs:

A <-> C - score: 1
A <-> D - score: 1
A <-> E - score: 8
A <-> F - score: 9
A <-> B - score: 16
B <-> C - score: 1
B <-> D - score: 5
B <-> E - score: 25
B <-> F - score: 10
F <-> C - score: 20
F <-> D - score: 18
F <-> E - score: 4
E <-> C - score: 25
E <-> D - score: 5
D <-> C - score: 32

The score of a pair is given by:

score of pair = score of first player + score of second player

For example, the score of AC pair ( |AC| ) is given by:

|AC| = 0 + 1 = 1

2. Sort pairs by score

Then the pairs are sorted by score:

A <-> C - score: 1
A <-> D - score: 1
B <-> C - score: 1
F <-> E - score: 4
E <-> D - score: 5
B <-> D - score: 5
A <-> E - score: 8
A <-> F - score: 9
B <-> F - score: 10
A <-> B - score: 16
F <-> D - score: 18
F <-> C - score: 20
E <-> C - score: 25
B <-> E - score: 25
D <-> C - score: 32

3. Select a subset of pairs

A subset of the "best" pairings is then chosen:

A <-> C - score: 1
A <-> D - score: 1
B <-> C - score: 1
F <-> E - score: 4

4. For each pair produce a scheme

Now, for each pair in the subset at point 3, the algorithm produces
a scheme (a possible solution) traversing the set of all pairs
sorted by score.

For example:

given the pair AC taken from the "best" pairings subset, traversing
the set of all the pairs sorted by score we obtain the scheme below:

A <-> C
F <-> E
B <-> D

In this example, four schemes will be produced.

5. Take the best scheme produced

Finally, to give the "best" result, the procedure takes the scheme
with minimum score. In this case:

A <-> D - score: 1
B <-> C - score: 1
F <-> E - score: 4

Total score: 6

Thanks for the quiz.
Andrea