From: Dustin Barker <dustin.barker@...>
Date: 2008-06-09T05:39:57+09:00
Subject: Re: [QUIZ] Preferable Pairs (#165)

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[i].push(entry)
     matrix[j].push(entry)
   end
end

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

matches = []

(matrix.size - 2).downto(1) do |i|
   matrix = matrix.sort { |a,b| b[i][2] <=> a[i][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[i].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