From: Eric Mahurin <eric.mahurin@...>
Date: 2008-06-09T06:19:56+09:00
Subject: Re: [QUIZ] Preferable Pairs (#165)

------=_Part_21188_20244148.1212960079726
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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)

------=_Part_21188_20244148.1212960079726--