From: ThoML <micathom@...>
Date: 2008-06-09T22:54:59+09:00
Subject: Re: Preferable Pairs (#165)

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[b].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