# Solution to Ruby Quiz #165
#
# This procedure *doesn't* find the *best* solution. Instead, it aims
# to give *good* results in an acceptable time interval.
#
# = Description of the algorithm
#
# 1. Find all possible pairs
#
# Given the following preferences matrix:
#
# A: C D E F B
# B: A C D F E
# C: B A F E D
# D: A B E F C
# E: F D A B C
# F: A B E D C
#
# the first step is to find all possible pairs:
#
# A <-> C - score: 1
# A <-> D - score: 1
# A <-> E - score: 8
# A <-> F - score: 9
# A <-> B - score: 16
# B <-> C - score: 1
# B <-> D - score: 5
# B <-> E - score: 25
# B <-> F - score: 10
# F <-> C - score: 20
# F <-> D - score: 18
# F <-> E - score: 4
# E <-> C - score: 25
# E <-> D - score: 5
# D <-> C - score: 32
#
# The score of a pair is given by:
#
# score of pair = score of first player + score of second player
#
# For example, the score of AC pair ( |AC| ) is given by:
#
# |AC| = 0 + 1 = 1
#
# 2. Sort pairs by score
#
# The pairs are sorted by score:
#
# A <-> C - score: 1
# A <-> D - score: 1
# B <-> C - score: 1
# F <-> E - score: 4
# E <-> D - score: 5
# B <-> D - score: 5
# A <-> E - score: 8
# A <-> F - score: 9
# B <-> F - score: 10
# A <-> B - score: 16
# F <-> D - score: 18
# F <-> C - score: 20
# E <-> C - score: 25
# B <-> E - score: 25
# D <-> C - score: 32
#
# 3. Select a subset of pairs
#
# A subset of the "best" pairings is then chosen:
#
# A <-> C - score: 1
# A <-> D - score: 1
# B <-> C - score: 1
# F <-> E - score: 4
#
# 4. For each pair produce a scheme
#
# Now, for each pair in the subset at point 3, the algorithm produces
# a scheme (a possible solution) traversing the set of all pairs
# sorted by score.
#
# For example:
#
# Given the pair AC taken from the "best" pairings subset and traversing
# the set of all the pairs sorted by score we obtain the scheme below:
#
# A <-> C
# F <-> E
# B <-> D
#
# In this example, four schemes will be produced.
#
# 5. Take the best scheme produced
#
# Finally, to give the "best" result, the procedure takes from all the
# generated schemes, the scheme with minimum score. In this case:
#
# A <-> D - score: 1
# B <-> C - score: 1
# F <-> E - score: 4
#
# Total score: 6
#

#
# Pair objects represent a pair of players.
#
class Pair
  include Comparable

  class << self
    #
    # Calculates the score of the given pair.
    #
    # Example:
    #
    #   preferences = {'A' => ['B', 'C'], 'B' => ['A', 'C'], 'C' => ['B', 'A']}
    #   Pair.score(preferences, 'A', 'B') #=> 0
    #
    def calc_score(preferences, player, other_player)
      preferences[player].index(other_player)**2 + preferences[other_player].index(player)**2          
    end
  end

  attr_reader :pair, :score
  alias :to_a :pair
  #
  # Initialize a pair of player with an associated score. If a score
  # is not given it defaults to 0.
  # 
  # Example:
  #
  #   pair = Pair.new('David', 'Joseph', 3)
  #
  def initialize(*args)
    @pair, @score = args[0..1], args[2] || 0
  end
  #
  # AC == AC
  # AC == CA
  #
  def ==(other_pair)
    @pair == other_pair.pair or @pair == other_pair.pair.reverse
  end
  def <=>(other_pair)
    score <=> other_pair.score
  end
  #
  # Check if the pair includes a player.
  #
  # Example:
  #
  #   pair = Pair.new('David', 'Joseph', 3)
  #   pair.include?('David') #=> true
  #
  def include?(player)
    @pair.include?(player)
  end
  # Pretty print pair.
  def to_s
    "#{@pair[0]} <-> #{@pair[1]} - score: #{score}\n"
  end
end

#
# Scheme objects are responsible to calculate possible pairings.
#
class Scheme
  include Comparable

  attr_reader :players, :pairs, :pairings
  #
  # Initialize a scheme passing the players and the set of all
  # possible pairs (see SchemeGenerator).
  #
  def initialize(players, pairs)
    @players, @pairs = players, pairs    
  end
  #
  # Add a pair to the scheme.
  #
  # Example:
  #   
  #   scheme << Pair.new('David', 'Helen')
  #
  def <<(pair)
    @pairs << pair
  end
  #
  # Compares schemes by their score.
  #
  def <=>(other_scheme)
    score <=> other_scheme.score
  end
  #
  # Calculates the total score of the scheme.
  #
  def score
    @pairings.inject(0) do |sum, pair|
      sum + pair.score
    end    
  end
  #
  # Check if the given player is already in pair.
  #
  def include?(player)
    players_in_pair.include?(player)
  end
  #
  # Pretty print pairings and score.
  #
  def to_s
    @pairings.each { |pair| puts pair.to_s }
    puts "#{left_out} was left out" if left_out
    puts "\nTotal score: #{score}\n"
  end
  #
  # Traverses the pairs starting from the given pair and produces a
  # possible scheme of pairings.
  #
  def pair_off(pair)
    @pairings = []
    @pairings << pair
    @pairs.sort.each do |pair|
      @pairings << pair unless include?(pair.pair[0]) or include?(pair.pair[1])
    end
    self
  end
  #
  # If players are in odd number, returns an array containing the
  # player that was left out.
  #
  def left_out
    @players - players_in_pair if @players.size % 2
  end

  private

  def players_in_pair
    @pairings.collect { |pair| pair.pair }.flatten
  end

end

#
# SchemeGenerator generates possible schemes.
#
class SchemeGenerator
  attr_reader :players, :pairs, :preferences

  class << self
    #
    # Load a preferences matrix from the given file.
    #
    # Example:
    #
    #   generator = SchemeGenerator.load('example_a')
    #
    def load(file)
      require 'yaml'
      preferences = { }
      YAML::load_file(file).each { |player, prefs| preferences[player] = prefs.split }
      SchemeGenerator.new(preferences)
    end
  end
  #
  # Initialize a SchemeGenerator object with the given preferences matrix.
  #
  def initialize(preferences)
    @preferences = preferences
    find_all_players
    find_all_pairs
  end
  #
  # Calculates the score of the given pair.
  #
  def calc_pair_score(player, other_player)
    Pair.calc_score(@preferences, player, other_player)
  end
  #
  # Produces a set of possible solutions. The method select a subset
  # of the pairs with lower scores. Then, for each selected pair, a
  # scheme is calculated.
  #
  # Example:
  #  
  #   generator.pair_off.min # returns the "best" solution
  #
  def pair_off
    @schemes = []
    # Select all pairs that score from 0 to ((players.size - 1) / 2)**2
    # These are considered to be good pairs.
    @pairs.select { |pair| pair.score >= 0 and pair.score <= ((players.size - 1) / 2) ** 2 }.each do |pair|
      @schemes << Scheme.new(@players, @pairs).pair_off(pair)
    end
    @schemes
  end

  private

  #
  # Grab all players from the first row of preferences matrix.
  #
  def find_all_players
    @players = []
    first = @preferences.keys.first
    @players = @preferences[first].to_a.flatten << first
  end
  #
  # Find all possible pairs.
  #
  def find_all_pairs
    @pairs = []
    players = @players.dup
    players.reverse_each do |player|
      players.each do |other_player|
        @pairs << Pair.new(player, other_player, calc_pair_score(player, other_player)) unless player == other_player
      end
      players.pop
    end
    @pairs
  end

end

SchemeGenerator.load(ARGV[0]).pair_off.min.to_s if ARGV[0]