From: ThoML <micathom@...>
Date: 2008-06-09T03:28:45+09:00
Subject: Re: Preferable Pairs (#165)

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 = []
    catch(:exit) 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[b].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[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