fair_distribution.rb

require 'utils'
require 'swap'

# A very simple algorithm based on incremental balancing of job queues.
# Initially, the first queue has all the jobs that are gradually distributed
# across available queues. The algorithm doesn't take much memory since it
# does not involve the recursive traversing of the options tree and
# doesn't store lots of intermediate data.
class FairDistribution
  
  def initialize(jobs, num_of_queues)
    @queues = [ jobs.sort.reverse ]
    (num_of_queues - 1).times { @queues << [] }

    # Balance the queues until they are perfectly balanced
    while !balance_all_queues do; end
  end
  
  # Time required for all queues processing
  def time_required
    @queues.map { |q| q.sum }.max
  end
  
  # The actual distribution of jobs across the queues
  def distribution
    @queues
  end
  
  private
  
  # Runs through all queues and balances them against each other.
  # Makes one pass only and returns FALSE if there was nothing changed
  # during the pass.
  def balance_all_queues
    updated = false
    
    @queues.each_with_index do |q1, qi1|
      (qi1+1 ... @queues.size).each do |qi2|
        res = balance_queues(q1, @queues[qi2])
        updated ||= res
      end
    end
    
    return !updated
  end
  
  # Balances the two queues between themselves by finding the best possible
  # swap of jobs between them. If there's nothing to be improved, returns FALSE.
  def balance_queues(q1, q2)
    delta = q1.sum - q2.sum
    return false if delta == 0
    
    best_swap       = nil
    best_swap_delta = delta.abs
          
    q1.each_combination do |c1|
      best_swap, best_swap_delta = choose_better_swap(c1, [], delta, best_swap, best_swap_delta)
    
      q2.each_combination do |c2|
        best_swap, best_swap_delta = choose_better_swap(c1, c2, delta, best_swap, best_swap_delta)
      end
    end
  
    best_swap.apply(q1, q2) unless best_swap.nil?
      
    return !best_swap.nil?
  end
  
  # Sees if the swap we have at hand is better than our current best
  # swap and replaces the latest if it is.
  def choose_better_swap(c1, c2, delta, best_swap, best_swap_delta)
    unless c1 == c2
      s = Swap.new(c1, c2, delta)
      best_swap, best_swap_delta = s, s.delta if s.delta < best_swap_delta 
    end
    
    return best_swap, best_swap_delta
  end
end

fair_distribution_acceptance.rb

require 'test/unit'
require 'fair_distribution'

class FairQueueTest < Test::Unit::TestCase

  def test_basic1
    jobs              = [10, 15, 20, 24, 30, 45, 75]
    number_of_presses = 2
    
    exp_max           = 110
      
    fd = FairDistribution.new(jobs, number_of_presses)
    assert_equal exp_max, fd.time_required

    # A Solution
    #     [75, 20, 15],
    #     [45, 30, 24, 10,]
  end
  
  def test_basic2
    jobs              = [1.0, 4.75, 2.83, 1.1, 5.8, 3.5, 4.4]
    number_of_presses = 4
    
    exp_max           = 6.33
    exp_distribution  = [
        [1.0, 4.75],
        [2.83, 3.5],
        [1.1, 4.4], 
        [5.8]
      ]
      
    fd = FairDistribution.new(jobs, number_of_presses)
    assert_equal exp_max, fd.time_required
    assert_distributions_are_equivalent exp_distribution, fd.distribution
  end
  
  def test_basic3
    jobs              = [0.23, 0.47, 0.73, 1.5, 3.0, 3.2, 1.75, 2.3, 0.11, 0.27, 1.09]
    number_of_presses = 4
    
    exp_max           = 3.73
      
    fd = FairDistribution.new(jobs, number_of_presses)
    assert_equal exp_max, fd.time_required
  
    # A Solution
    #     [3.2, 0.47],
    #     [3.0, 0.73],
    #     [2.3, 1.09, 0.23],
    #     [1.75, 1.5, 0.27, 0.11]
  end #if ARGV[0] == "full" # only use this TC if 'full' is added as an argument.
  
  def test_basic4
    jobs = [5,5,4,4,3,3,3]
    number_of_presses = 3
  
    exp_max = 9
    exp_distribution = [
      [5,4],
      [5,4],
      [3,3,3],
    ]
    fd = FairDistribution.new(jobs, number_of_presses)
    assert_equal exp_max, fd.time_required
    assert_distributions_are_equivalent exp_distribution, fd.distribution
  end

  def test_basic5
    fd = FairDistribution.new([0.23, 0.47, 0.73, 1.5, 3.0, 3.2], 4)
    assert_equal 3.2, fd.time_required
    assert_distributions_are_equivalent [[3.0], [3.2], [0.23, 0.47, 0.73], [1.5]], fd.distribution
  end
    
  private

  def assert_distributions_are_equivalent(dist1, dist2, msg=nil)
    failure_message = "Distributions not equivalent: #{msg}: #{dist1.inspect} not equivalent to #{dist2.inspect}"
    assert(distributions_are_equivalent?(dist1, dist2), failure_message)
  end

  def distributions_are_equivalent?(dist1, dist2)
    return false if dist1.size != dist2.size
    my_dist1 = dist1.dup
    my_dist2 = dist2.dup
    
    my_dist1.reject! {|queue1|
      dist2.detect {|queue2| arrays_have_same_elements?(queue1, queue2)}
    }
    
    my_dist2.reject! {|queue2|
      dist1.detect {|queue1| arrays_have_same_elements?(queue1, queue2)}
    }
    
    my_dist1.empty? && my_dist2.empty?
  end
  
  def arrays_have_same_elements?(arr1, arr2)
    arr1.size == arr2.size && (arr1 - arr2).empty?
  end
end

swap.rb

require 'utils'

# Single swap operation. It knows what move from one queue to another and
# what will be the delta between those queues after the operation.
class Swap

  attr_reader :delta

  def initialize(from_q1, from_q2, current_delta)
    @from_q1 = from_q1
    @from_q2 = from_q2
    @delta   = (current_delta + 2 * (from_q2.sum - from_q1.sum)).abs
  end
  
  # Applies the swap
  def apply(q1, q2)
    @from_q1.each do |j|
      q2 << q1.delete_at(q1.index(j))
    end

    @from_q2.each do |j|
      q1 << q2.delete_at(q2.index(j))
    end
  end
end

swap_test.rb

require 'test/unit'
require 'swap'

class SwapTest < Test::Unit::TestCase
  
  def test_swap_returns_correct_positive_delta
    current_delta = 10 # q1.sum - q2.sum = 10
    from_q1 = [ 1, 2 ] # 1 + 2 = 3
    from_q2 = [ 3, 4 ] # 3 + 4 = 7
    
    swap = Swap.new(from_q1, from_q2, current_delta)
    assert_equal 10 - 2 * (3 - 7), swap.delta
    
    # We multiply by 2 since we not only take [1, 2] from q1, but also add them to q2
    # which makes the difference twice as big.
  end
  
  def test_swap_returns_correct_negative_delta
    current_delta = 10 # q1.sum - q2.sum = 10
    from_q1 = [ 3, 4 ] # 3 + 4 = 7
    from_q2 = [ 1, 2 ] # 1 + 2 = 3
    
    swap = Swap.new(from_q1, from_q2, current_delta)
    assert_equal 10 - 2 * (7 - 3), swap.delta
  end
  
  def test_applying_changes_should_move_elements_between_queues
    q1 = [ 1, 1, 2 ]
    q2 = [ 3, 4 ]
    
    swap = Swap.new([ 1, 2 ], [ 3 ], -3)
    swap.apply(q1, q2)
    
    assert_equal [ 1, 3 ], q1
    assert_equal [ 4, 1, 2 ], q2
  end
  
end

utils.rb

# Simple additions to the generic array that are used to calculate the
# sum of items and iterate over the elements in a specific fashion.
class Array

  # Returns the sum of all values in the array
  def sum
    self.inject(0.0) do |memo, value|
      memo + (value.is_a?(Array) ? value.total : value)
    end
  end
  
  # Iterates over all unique (based on their sum) combinations of elements.
  # [1,2,3] -> [1], [1,2], [1,2,3], [2], [2, 3] (see [3] is omitted as being equial to [1,2])
  def each_combination(i = 0, c = [], sums = [], &block)
    (i ... self.size).each do |x|
      combo = c + [ self[x] ]
      sum = combo.sum
      
      unless sums.include?(sum)
        sums << sum
        block.call combo
        each_combination(x + 1, combo, sums, &block)
      end
    end
  end

end

utils_test.rb

require 'test/unit'
require 'utils'

class UtilsTest < Test::Unit::TestCase
  
  def test_each_combination_should_invoke
    c = []
    [1, 2, 3].each_combination { |combo| c << combo }
    assert_equal [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], c
  end

  def test_uniqueness_of_each_combination
    c = []
    [1, 2, 1].each_combination { |combo| c << combo }
    assert_equal [[1], [1, 2], [1, 2, 1], [1, 1]], c
  end
  
end