Preferable Pairs

This is a solution to Ruby Quiz #165. The goal of the quiz is to pair up individuals based on their preferences trying to achieve the best possible pairings.

Here is the solution:

# This is a solution to RubyQuiz #165 named Preferable Pairs.  the
# problem description can be found at:
#
#    http://splatbang.com/rubyquiz/quiz.rhtml?id=165_Preferable_Pairs
#
# This solution uses a genetic algorithm to try to find the best
# possible set of pairings (called a partnership scheme).  It's not
# guaranteed to find the best, however.  A population of partnership
# schemes is created, and a new generation is created by mutating a
# random selection of the current population.  The previous population
# plus the new generation are combined, and the best of those plus a
# random selection of the remaining create the next population.  The
# fitness of a given scheme is the score, where lower scores equate to
# greater fitness.
#
# The latest version of this solution can be found at:
#
#     http://LearnRuby.com/code.html


require 'enumerator'


class Integer
  # produces a string with a character every so many digits from the
  # right; by default it's a comma every three digits
  def to_separated_s(separater = ",", every = 3)
    digits = to_s.split(//)
    cursor = every + 1
    while cursor <= digits.size
      digits.insert(-cursor, ",")
      cursor += every + 1
    end
    digits.join('')
  end
end


class Person
  attr_reader :name, :preferences

  def initialize(name, preferences)
    @name, @preferences = name, preferences
  end

  def score(other)
    @scores[other]
  end

  # transforms preference list form names to Person instances and adds
  # a scores hash to quickly go from partner to score (to avoid linear
  # search); this can only be done once all Persons are created
  def transform
    preferences.map! { |name| Person.lookup(name) }

    @scores = {}
    preferences.each_with_index do |other, index|
      @scores[other] = index
    end
  end

  class << self
    def people
      @people.values
    end
    
    def count
      @people.size
    end
    
    def lookup(name)
      @people[name]
    end

    def load(input)
      @people = {}
      while line = gets
        person = new($1, $2.split) if line.match /(.*): (.*)/
        @people[person.name] = person
      end

      # now transform everyone
      @people.values.each do |person|
        person.transform
      end
    end

    protected :new
  end
end


# Represents a pair of Persons, or possibly one Person and nil if
# there were originally an odd number of Persons.
class Partnership
  attr_reader :people

  def initialize(person1, person2)
    @people = [person1, person2]
  end

  def first
    @people.first
  end

  def second
    @people.last
  end

  # the score for a parternship of one person is always 0, otherwise
  # it's the sum of the squares of the indices of each Person in the
  # Partnership
  def score
    @score ||=
      first && second ?
        first.score(second) ** 2 + second.score(first) ** 2 :
        0
  end

  # true if only one person is in the Partnership
  def solo?
    !(first && second)
  end

  def to_s
    if first && second : "#{first.name} #{second.name}"
    elsif first : first.name
    else second.name
    end
  end
end


# A ParternshipScheme is a set of Partnerships where each Person
# appears in only one Partnership.
class ParternshipScheme
  attr_reader :partnerships

  def initialize(partnerships)
    raise problem unless partnerships.all? { |p| p.is_a? Partnership }
    @partnerships = partnerships
  end

  def score
    @score ||= @partnerships.inject(0) { |sum, p| sum + p.score }
  end

  # Picks two of the Parternships at random, swaps one person from
  # each, and generates a new scheme.  It's important that when we mix
  # up the two Partnerships that one person moves from the first
  # position to the second and another vice versa.  If people are
  # frozen in the first or second, then it limits the potential
  # Partnerships and ParternshipSchemes available.
  def mutate
    new_partnerships = @partnerships.dup
    partnership1 =
      new_partnerships.delete_at(rand(new_partnerships.size))
    partnership2 =
      new_partnerships.delete_at(rand(new_partnerships.size))
    new_partnerships <<
      Partnership.new(partnership1.first, partnership2.first)
    new_partnerships <<
      Partnership.new(partnership1.second, partnership2.second)
    ParternshipScheme.new(new_partnerships)
  end

  def to_s
    @partnerships.sort_by { |p|
      p.solo?.hash }.map { |partnership|
      partnership.to_s }.join("\n")
  end

  class << self
    def randomized(people)
      partnerships = []
      randomized = people.sort_by { rand }
      randomized.each_slice(2) do |p1, p2|
        partnerships << Partnership.new(p1, p2)
      end
      new(partnerships)
    end

    # given a fixed number of people returns how many pair
    # parternships are possible; one formula for this value is the
    # product of all odd values from 1..people.
    def possible_count(people)
      # people.factorial / (2 ** (people / 2)) / (people / 2).factorial
      (1..people).select { |p| p & 1 == 1 }.inject { |product, v|
        product * v }
    end
  end
end


if $0 == __FILE__
  case ARGV.size
  when 0 : Person.load(STDIN)
  when 1 : open(ARGV[0]) { |f| Person.load(f) }
  else
    STDERR.puts "Usage: #{$0} [data-file]"
    STDERR.puts "  stdin used if no data-file provided"
    exit 1
  end

  possible_scheme_count =
    ParternshipScheme.possible_count(Person.count)

  puts "Calculating for #{Person.count} people."
  puts "The number of possible partnership combinations is:\n    " +
    "#{possible_scheme_count.to_separated_s}."

  ## Determine the basic parameters for the genetic algorithm.

  # there is no great insight behind this formula other than that when
  # there were 20 people to be paired up, 400 seemed to work well for
  # both population_size and generations, so I used a logorithmic
  # scale to make it come out that way
  population_size =
    ((Math.log(possible_scheme_count) / Math.log(2))**1.8).to_i

  generations = population_size
  offspring = population_size / 2
  keep_best = population_size / 2
  keep_random = population_size + offspring - keep_best

  puts "Population: #{population_size} ; Generations: #{generations}"

  ## Create the initial population.
  
  population = []
  population_size.times do
    population << ParternshipScheme.randomized(Person.people)
  end

  ## Run through the generations.
  
  generations.times do |generation|
    # add offspring to population
    offspring.times do
      population << population[rand(population_size)].mutate
    end

    # sort new population by fitness
    population = population.sort_by { |scheme| scheme.score }

    # the next generation's pop. consists of keep_best best scoring
    # plus a random selection of the remaining non-best in the
    # population
    best = population[0, keep_best]
    random =
      population[keep_best..-1].sort_by { rand }[0, keep_random]
    population = best + random
  end

  ## Display the best results.

  puts "Score of best partnership combination found: " +
    "#{population.first.score.to_separated_s}."
  puts population.first
end