[QUIZ] Preferable Pairs (#165)

[Matthew Moss]

[Note: parts of this message were removed to make it a legal post.]

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

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]

Here is some quick code to generate sample preferences. Takes a single
optional argument (defaults to 10) which is the number of people to
generate. (I've got 34 names in here; if you want to try larger sets,
you'll have to add more names.)



NAMES = %w(Adam Anna Bob Betty Chuck David Daria Evan Ellen Fred Faye
Greg Gail Hank Helen Irene John Janet Laura Matt Maria Nadine Oleg
Olivia Peter Pamela Ric
k Rosa Steve Susan Theo Tracy Vicki Walter)

def sample(n)
names = NAMES.sort_by { rand }[0, n].sort
names.each do |name|
others = names.dup.reject { |other| other == name }.sort_by
{ rand }
puts "#{name}: #{others.join(' ')}"
end
end

sample(Integer(ARGV[0] || 10))

 

[Matthew Moss]

In addition to the sample generation code, here are some examples with
output produced from the initial version of my solution. I *think* I
have a good algorithm, but I haven't proven that it generates the
optimal solution.

Example A input:
Bob: Ellen Evan Vicki Helen Theo David Tracy Daria Matt
Daria: Helen Evan Ellen David Bob Matt Tracy Theo Vicki
David: Helen Matt Bob Daria Vicki Theo Evan Tracy Ellen
Ellen: Bob Daria Helen Evan Matt Theo Tracy Vicki David
Evan: Bob David Tracy Ellen Daria Vicki Helen Matt Theo
Helen: Theo Daria Tracy Bob Evan Matt Vicki David Ellen
Matt: Helen Ellen David Bob Theo Daria Tracy Evan Vicki
Theo: Ellen Bob David Tracy Vicki Helen Matt Daria Evan
Tracy: Evan Daria Bob Matt Ellen Vicki Theo Helen David
Vicki: Tracy Daria Theo Helen Bob Ellen Matt Evan David

Example A output:
Ellen Bob
Daria Helen
Tracy Evan
David Matt
Vicki Theo

Example B input:
David: John Hank Evan Gail Walter
Evan: David Hank Gail Walter John
Gail: David John Walter Evan Hank
Hank: Gail John Walter David Evan
John: Hank David Evan Gail Walter
Walter: Evan John Hank Gail David

Example B output:
David John
Walter Evan
Hank Gail

Example C input:
Anna: Betty Rosa Daria Helen Ellen Theo
Betty: Rosa Daria Anna Helen Theo Ellen
Daria: Rosa Theo Ellen Helen Betty Anna
Ellen: Betty Helen Rosa Daria Theo Anna
Helen: Theo Daria Anna Rosa Ellen Betty
Rosa: Daria Ellen Helen Betty Theo Anna
Theo: Daria Ellen Helen Betty Anna Rosa

Example C output:
Rosa Daria
Betty Anna
Helen Theo
Ellen

 

[ThoML]

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

What is the penalty for "unwanted" pairings, e.g.

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

with output:

David Joseph
Helen Vicki

Or is the list of preferences always complete, i.e. it always contains
all other players?

 

[Matthew Moss]

What is the penalty for "unwanted" pairings, e.g.

=A0 =A0 David: Helen Vicki
=A0 =A0 Helen: David
=A0 =A0 Joseph: Vicki Helen
=A0 =A0 Vicki: David

with output:

=A0 =A0 David Joseph
=A0 =A0 Helen Vicki

Or is the list of preferences always complete, i.e. it always contains
all other players?

Yes, always complete, the least preferred players will be toward the
end.

 

[Eric I.]

In addition to the sample generation code, here are some examples with
output produced from the initial version of my solution. I *think* I
have a good algorithm, but I haven't proven that it generates the
optimal solution.

Example B input:
David: John Hank Evan Gail Walter
Evan: David Hank Gail Walter John
Gail: David John Walter Evan Hank
Hank: Gail John Walter David Evan
John: Hank David Evan Gail Walter
Walter: Evan John Hank Gail David

Example B output:
David John
Walter Evan
Hank Gail

I think that scores 26. A score of 18 is achievable (see below),
although I don't know if it's optimal. With only 15 (I think)
potential partnership schemes when there are six people, it could be
verified, although I haven't done it.

David Evan
Hank John
Gail Walter

By the way, if there are n people, I believe the formula for the
number of partnership schemes is:

n! / (n / 2)! / 2**(n / 2)

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Wkshp June 16-18 Ann Arbor, Mich.
Ready for Rails Ruby Wkshp June 23-24 Ann Arbor, Mich.
Ruby on Rails Wkshp June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Wkshp June 23-27 Ann Arbor, Mich
Please visit http://LearnRuby.com for all the details.

 

[Matthew Moss]

Example B output:

I think that scores 26. =A0A score of 18 is achievable (see below),
although I don't know if it's optimal. =A0With only 15 (I think)
potential partnership schemes when there are six people, it could be
verified, although I haven't done it.

David Evan
Hank John
Gail Walter

Correct you are, sir. My algorithm is greedy, but after a certain
transform was done, which I had hoped would make greedy acceptable. I
guess not.

Back to the drawing board...

 

[Eric I.]

I used a genetic algorithm that tries to find the best solution
possible in a given number of iterations. It doesn't always find the
best, but generally does pretty well. And because there are
randomized aspects to each run, you can end up with different
solutions (of different scores) on consecutive runs. The code can be
found at:

http://learnruby.com/examples/ruby-quiz-165.shtml

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Wkshp June 16-18 Ann Arbor, Mich.
Ready for Rails Ruby Wkshp June 23-24 Ann Arbor, Mich.
Ruby on Rails Wkshp June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Wkshp June 23-27 Ann Arbor, Mich
Please visit http://LearnRuby.com for all the details.

 

[Eric I.]

By the way, if there are n people, I believe the formula for the
number of partnership schemes is:

    n! / (n / 2)! / 2**(n / 2)

An alternative (and more efficient) way to compute the number of
partnership schemes is to multiply all the odd values from 1..n. For
example, if there are eight people, then we have 1 * 3 * 5 * 7, or
105.

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
   Ruby Fundamentals Wkshp          June 16-18     Ann Arbor, Mich.
   Ready for Rails Ruby Wkshp       June 23-24     Ann Arbor, Mich.
   Ruby on Rails Wkshp              June 25-27     AnnArbor, Mich.
   Ruby Plus Rails Combo Wkshp      June 23-27     Ann Arbor, Mich
Please visithttp://LearnRuby.comfor all the details.

 

[ThoML]

Stable roommates or not, I have two solutions. The second one is
supposed to be exact. No fancy genetic batteries included.

Regards,
Thomas.


======================================================== #1
#!/usr/bin/env ruby19

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end


def match_names(data)
names = data.keys

# sort pairings
mt = Hash.new {|h, k| h[k] = []}
names.each do |k|
data[k].each_with_index do |l, v|
mt[v ** 2 + data[l].index(k) ** 2] << [k, l]
end
end

# collect pairs
pairs = []
catchexit) do
mt.entries.sort.each do |pri, opairs|
opairs.each do |ab|
if ab.all? {|n| names.include?(n)}
pairs << ab
names -= ab
throw :exit if names.size < 2
end
end
end
end

# add remaining singles
pairs << names unless names.empty?

return pairs
end


if __FILE__ == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" ")}.join("\n")

if $DEBUG
def assess(data, pairs)
pairs.inject(0) do |s, e|
a, b = e
if a and b
va = data[a].index(b) ** 2
vb = data.index(a) ** 2
s + va + vb
else
s
end
end
end
puts assess(data, pairs)
end
end



======================================================== #2
#!/usr/bin/env ruby19

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end


def optimize(data, pairings, names, range, pairs=[], weight=0,
maxweight=nil)
bestpairs = nil
maxweight ||= pairings.keys.max ** 2 + 1
for pos in range
weight1 = weight + pos
break if weight1 >= maxweight
pairings[pos].each do |pair|
if names & pair == pair
pairings[pos].delete(pair)
pairs << pair
begin
names1 = names - pair
if names1.size < 2
bestpairs = pairs.dup
bestpairs << names1 unless names1.empty?
return [weight1, bestpairs]
elsif pos < maxweight - weight1
w1, p1 = optimize(data, pairings, names1,
pos..range.max, pairs, weight1, maxweight)
if p1 and w1 < maxweight
maxweight = w1
bestpairs = p1
end
end
ensure
pairs.pop
pairings[pos].unshift(pair)
end
end
end
end
return [maxweight, bestpairs]
end


def match_names(data)
names = data.keys

# sort pairings
pairings = Hash.new {|h, k| h[k] = []}
maxpos = 0
names.each do |k|
data[k].each_with_index do |l, v|
w = v ** 2 + data[l].index(k) ** 2
maxpos = w if w > maxpos
pairings[w] << [k, l]
end
end

# collect pairs
weight, pairs = optimize(data, pairings, names, 0..maxpos)

return pairs
end


def assess(data, pairs)
pairs.inject(0) {|s, e| s + assess_pair(data, e)}
end


def assess_pair(data, pair)
a, b = pair
if a and b
va = data[a].index(b) ** 2
vb = data.index(a) ** 2
va + vb
else
0
end
end


if __FILE__ == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" ")}.join("\n")
puts assess(data, pairs) if $DEBUG
end

 

[Dustin Barker]

Here's my solution - I think I've got it, but haven't found a way to
prove whether or not it's optimal yet ;-)

-Dustin

# parse input file
# make a hash, key is player, value is array of preferred matches
# in order of preference
preferences = {}
File.open(ARGV[0]) do |file|
while line = file.gets
a = line.split
player = a[0][0...a[0].size-1]
preferences[player] = a[1...a.size]
end
end

# score each individual preference, first choice gets 0 score
# i.e. lower scores are better
keys = preferences.keys

matrix = keys.collect { |k| Array.new }
keys.each_with_index do |player, i|
keys.each_with_index do |oplayer, j|
next if j < i + 1 # process above main diagonal
# storing score, which is position of oplayer in preference list
s1 = preferences[player].index(oplayer)
s2 = preferences[oplayer].index(player)
score = s1 + s2
entry = [player, oplayer, score]
matrix.push(entry)
matrix[j].push(entry)
end
end

matrix.size.times do |i|
matrix = matrix.sort { |a,b| a[2] <=> b[2] }
end

matches = []

(matrix.size - 2).downto(1) do |i|
matrix = matrix.sort { |a,b| b[2] <=> a[2] }
end

while matrix.size > 0
matrix = matrix.sort { |a,b| a[0][2] <=> b[0][2] }

match = matrix.first.first
matches.push([match[0], match[1]])

matrix.size.times do |i|
matrix.delete_if do |pmatch|
pmatch.include?(match[0]) || pmatch.include?(match[1])
end
end
matrix.delete_if { |row| row.empty? }

end

matches.each do |match|
puts "#{match[0]} #{match[1]}"
end

# find the odd one...
puts keys - matches.flatten.uniq

 

[Eric Mahurin]

[Note: parts of this message were removed to make it a legal post.]

I have a solution at the end of this message. This solution finds the
optimal solution. I believe this problem is NP-complete, so a fast optimal
solution for large inputs is out of the question. But, there are some
things that I did that give significant performance improvement:

* Used memoization to not recalculate costs for subsets that have already
been computed. This reduced the complexity from O(n!) to O(2**n).

* Divided finding the pairs into 2 phases: finding min cost, and finding
pairs based on min costs. This simplified the bottleneck of finding the min
cost and reduced its overhead. Given the min costs, the pairs can be found
in O(n**2).

* Mapped each player to a bit index/mask. This allowed a set of players to
be represented as simply an Integer/Fixnum.

* Applied some O(1) bit-searching techniques I developed about 10 years ago
on the hardware side (x86 BSR - bit-scan-reverse).

* No small objects are created (and garbage collected) during the algorithm.

Eric

#!/usr/bin/env ruby

Infinity = 1.0/0.0

class PreferrablePairs

def initialize
# remaining bit pattern => cost (init to no remaining => 0)
# size will be O(2**n)
# only patterns with an even number of bits set will be used
@cost = [0]
#@cost = {0=>0} # Hash could be used just as well (little slower)
@mask = 1 # next mask to use
# mask <=> name maps
@mask2name = {}
@name2mask = Hash.new { |name2mask, name|
# create a new entry when it is missing
begin
@mask2name[@mask] = name
name2mask[name] = @mask
ensure
# post operation
@mask <<= 1
end
}
end

# throw out all cached costs - for more than just pairs
# O(2**n)
def flush
@mask.times { |rem|
# little trick for masking lowest bit set (applied twice)
rem2 = rem&(rem-1)
rem2 = rem2&(rem2-1)
next if rem2.zero? # 2 or fewer bits of mask set
@cost[rem] = nil
}
end

# add a cost between a pair
def add(first, second, cost)
mask = @name2mask[first]|@name2mask[second]
@cost[mask] = (@cost[mask]||0)+cost
end

# fill-in default costs for unassociated pairs
# ensure we have an even number of entries
def fill(defcost=0, evenname="", evencost=0)
mask1 = 1
while mask1<@mask
mask2 = mask1<<1
while mask2<@mask
@cost[mask1|mask2] ||= defcost
mask2 <<= 1
end
mask1 <<= 1
end
if (@name2mask.size&1).nonzero?
# add another entry when we have an odd number
mask2 = @name2mask[evenname]
mask1 = 1
while mask1<@mask
@cost[mask1|mask2] ||= evencost
mask1 <<= 1
end
end
end

# cost for a remaining set of entries
# O(2**n) if @cost is not cached (n=remaining entries)
# O(n**2) if @cost is cached
# O(n!+) if memoization is disabled
def cost(remaining=@mask-1)
bestcost = Infinity
# iterate through all pairs in remaining
mask1 = 1
# little trick find the next set bit from mask1
while (mask1 = remaining&~(remaining-mask1)).nonzero?
rem1 = remaining&~mask1 # remove first from remaining
mask2 = mask1
while (mask2 = rem1&~(rem1-mask2)).nonzero?
rem2 = rem1&~mask2 # remove second from remaining
# cost is for this pair + cost of remaining pairs
# ||= does memoization for us (change to || to not do it)
cost = @cost[mask1|mask2] + (@cost[rem2]||=cost(rem2))
# keep the min cost
if cost<bestcost
bestcost = cost
end
mask2 <<= 1
end
mask1 <<= 1
end
bestcost
end

# pair the entries up
# needs to know what the best cost is first
# yields each pair
# O(n**2) w/ memoization
# O(n!+) w/o memoization
def pair(bestcost, remaining=@mask-1) # :yield: first, second
while (mask1 = remaining&~(remaining-1)).nonzero?
rem1 = remaining&~mask1
mask2 = mask1
while (mask2 = rem1&~(rem1-mask2)).nonzero?
# @cost[...] => (@cost[...]||cost(...)) to skip memoization
if
(cost0=@cost[mask0=mask1|mask2])+@cost[rem1&~mask2]==bestcost
# yield a best pairings
yield(@mask2name[mask1], @mask2name[mask2])
bestcost -= cost0
remaining &= ~mask0
break
end
mask2 <<= 1
end
end
end

end

require 'strscan'

preferrable = PreferrablePairs.new
scanner = StringScanner.new("")

STDIN.each_line { |line|
scanner.string = line
scanner.scan(/\s*/)
first = scanner.scan(/\w+/) or next
scanner.scan(/\s*\:/) or next
order = 0
while scanner.scan(/\s*/) and second = scanner.scan(/\w+/)
preferrable.add(first, second, order*order)
order += 1
end
}
preferrable.fill

require 'benchmark'

pairs = nil
cost = nil

4.times {
Benchmark.bm { |b|
pairs = ""
b.report {
cost = preferrable.cost
preferrable.pair(cost) { |first, second|
pairs.concat("#{first} #{second}\n")
}
}
preferrable.flush
}
}

STDERR.puts(cost)
puts(pairs)

 

[Eric Mahurin]

[Note: parts of this message were removed to make it a legal post.]

I have a solution at the end of this message. This solution finds the
optimal solution. I believe this problem is NP-complete, so a fast optimal
solution for large inputs is out of the question. But, there are some
things that I did that give significant performance improvement:

* Used memoization to not recalculate costs for subsets that have already
been computed. This reduced the complexity from O(n!) to O(2**n).

* Divided finding the pairs into 2 phases: finding min cost, and finding
pairs based on min costs. This simplified the bottleneck of finding the
min
cost and reduced its overhead. Given the min costs, the pairs can be found
in O(n**2).

* Mapped each player to a bit index/mask. This allowed a set of players to
be represented as simply an Integer/Fixnum.

* Applied some O(1) bit-searching techniques I developed about 10 years ago
on the hardware side (x86 BSR - bit-scan-reverse).

* No small objects are created (and garbage collected) during the
algorithm.

I improved on this solution further:

* The outer loop in #cost was unnecessary. I believe the complexity before
was actually O(n*n*2**n) and now it should be O(n*2**n).

* Used Hash instead of Array for costs. Not sure why this helped (Array was
faster in previous solution).

The new solution is below. My previous solution could only reasonably
handle about 16 players and the new solution handles about 26 players.

Eric

#!/usr/bin/env ruby

Infinity = 1.0/0.0

class PreferrablePairs

def initialize
# remaining bit pattern => cost (init to no remaining => 0)
# size will be O(2**n)
# only patterns with an even number of bits set will be used
#@cost = [0] # Array
@cost = {0=>0} # Hash seems faster and takes less memory
@mask = 1 # next mask to use
# mask <=> name maps
@mask2name = {}
@name2mask = Hash.new { |name2mask, name|
# create a new player when it is missing
begin
@mask2name[@mask] = name
name2mask[name] = @mask
ensure
# post operation
@mask <<= 1
end
}
end

# throw out all cached costs - for more than just pairs
# O(2**n)
def flush
if @cost.respond_to?map!)
# Array
rem = -1
@cost.map! { |cost|
rem += 1
cost ? (((rem2=rem&(rem-1))&(rem2-1)).zero? ? cost : nil) :
nil
}
else
# Hash
@cost.delete_if { |rem, cost|
((rem2=rem&(rem-1))&(rem2-1)).nonzero?
}
end
end

# add a cost between a pair
def add(first, second, cost)
mask = @name2mask[first]|@name2mask[second]
@cost[mask] = (@cost[mask]||0)+cost
end

# ensure we have an even number of players
def even(name="", cost=0)
if (@name2mask.size&1).nonzero?
# add another player when we have an odd number
mask2 = @name2mask[name]
mask1 = 1
while mask1<@mask
@cost[mask1|mask2] ||= cost
mask1 <<= 1
end
end
end

# fill-in default costs for unassociated pairs
def fill(defcost=0, evenname="", evencost=0)
mask1 = 1
while mask1<@mask
mask2 = mask1<<1
while mask2<@mask
@cost[mask1|mask2] ||= defcost
mask2 <<= 1
end
mask1 <<= 1
end
end

# cost for a remaining set of players
# O(n*2**n) if @cost is not cached (n=remaining players)
# O(n) if @cost is cached
def cost(remaining=@mask-1)
bestcost = Infinity
# arbitrarily pick lowest remaining bit to pair
mask1 = remaining&~(remaining-1)
rem1 = remaining^mask1 # remove first from remaining
mask2 = mask1
# little trick find the next set bit from rem1
while (mask2 = remaining&~(remaining-(mask2<<1))).nonzero?
# cost is for this pair + cost of remaining pairs
cost = @cost[mask1|mask2] + (@cost[rem2=rem1^mask2]||cost(rem2))
# keep the min cost
bestcost = cost if cost<bestcost
end
@cost[remaining] = bestcost
end

# pair the players up
# cost should have been calculated already
# yields each pair
# O(n**2)
def pair(remaining=@mask-1) # :yield: first, second
bestcost = @cost[remaining]
while (mask1 = remaining&~(remaining-1)).nonzero?
mask2 = mask1
begin
mask2 = remaining&~(remaining-(mask2<<1))
end until

(cost0=@cost[mask0=mask1|mask2])+@cost[remaining^mask0]==bestcost
# yield a best pairings
yield(@mask2name[mask1], @mask2name[mask2])
bestcost -= cost0
remaining ^= mask0
end
end

end

require 'strscan'

preferrable = PreferrablePairs.new
scanner = StringScanner.new("")

STDIN.each_line { |line|
scanner.string = line
scanner.scan(/\s*/)
first = scanner.scan(/\w+/) or next
scanner.scan(/\s*\:/) or next
order = 0
while scanner.scan(/\s*/) and second = scanner.scan(/\w+/)
preferrable.add(first, second, order*order)
order += 1
end
}
preferrable.even
preferrable.fill # just in case some pairs are missing

require 'benchmark'

pairs = nil
cost = nil

2.times {
Benchmark.bm { |b|
pairs = ""
b.report {
cost = preferrable.cost
preferrable.pair { |first, second|
pairs.concat("#{first} #{second}\n")
}
}
preferrable.flush
}
}

STDERR.puts(cost)
puts(pairs)

 

[ThoML]

pairings[pos].delete(pair)
[...]
pairings[pos].unshift(pair)

I just realized that this behaves differently in ruby18 and ruby19
when used within an each loop. These lines could be removed.

Also, my submission generates too many pairs. The following sorts the
pairs so that a perfect match is included only once.

names.each do |k|
data[k].each_with_index do |l, v|
w = v ** 2 + data[l].index(k) ** 2
maxpos = w if w > maxpos
pair = [k, l].sort
pairings[w] << pair unless pairings[w].include?(pair)
end
end

In any case, my mostly naive approach lags far behind Eric M and Eric
I's solutions (which I find quite interesting BTW).

 

[ThoML]

Hi folks,

I'm terribly sorry for these repeated posts but I didn't like the
runtime behaviour of my second solution (especially in comparison to
Eric Mahurin's submission).

Here is a slightly modified version that makes cuts slightly earlier.
Up to 25 players appear acceptable on my laptop: 22 secs for 20 random
sets of 25 player each.

Regards,
Thomas.


#!/usr/bin/env ruby

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end

def optimize(pairings, names, pos, posmax, maxweight=nil)
bestpairs = nil
maxweight ||= pairings.size ** 2 + 1
while pos < posmax
pair, weight1 = pairings[pos]
break unless weight1 * (names.size / 2).floor < maxweight
pos += 1
if names & pair == pair
names1 = names - pair
if names1.size < 2
bestpairs = [pair]
bestpairs << names1 unless names1.empty?
return [weight1, bestpairs]
elsif (rv = optimize(pairings, names1, pos, posmax,
maxweight - weight1))
maxweight, bestpairs = rv
maxweight += weight1
bestpairs << pair
end
end
end
return bestpairs && [maxweight, bestpairs]
end

def match_names(data)
names = data.keys.sort

# sort pairings
pairings = Hash.new {|h, k| h[k] = []}
maxpos = 0
names.each do |k|
data[k].each_with_index do |l, v|
w = v ** 2 + data[l].index(k) ** 2
maxpos = w if w > maxpos
pair = [k, l].sort
pairings[w] << pair unless pairings[w].include?(pair)
end
end
pairings1 = []
pairings.each do |pri, pairs|
pairings1.concat(pairs.zip([pri] * pairs.size))
end
pairings1 = pairings1.sort_by {|a, b| b}

# collect pairs
weight, pairs = optimize(pairings1, names, 0, pairings1.size)

return pairs
end

def assess(data, pairs)
pairs.inject(0) {|s, e| s + assess_pair(data, e)}
end

def assess_pair(data, pair)
a, b = pair
if a and b
va = data[a].index(b) ** 2
vb = data.index(a) ** 2
va + vb
else
0
end
end

if __FILE__ == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" ")}.join("\n")
puts assess(data, pairs) if $DEBUG
end

 

[Andrea Fazzi]

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

 

[Andrea Fazzi]

Andrea Fazzi ha scritto:

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

I improved a bit the comment of my code:

http://pastie.org/212209

Andrea