Instantly share code, notes, and snippets.

# peashutop/jacobhodes.rbSecret Created Feb 20, 2010

RPCFN submission
 # RPCFN Six: Fair Distribution # Submitted February 20, 2010 # Slightly revised March 9, 2010 # Author: Jacob Hodes # Distributes an array of numeric values into num_buckets buckets # such that the sums of each bucket are as equal as possible # # For fascinating background re: the hard math (and physics!) behind this problem, # see http://www.americanscientist.org/issues/pub/the-easiest-hard-problem # # Example usage: fd = FairDistribution.new([5,5,4,4,3,3,3], 3) # fd.distribution => [ [5,4], [5,4], [3,3,3] ] # fd.max_bucket_sum => 9 # class FairDistribution attr_reader :values, :num_buckets def initialize(values_array, num_buckets) @values, @num_buckets = values_array, num_buckets end # Lazily initialize @distribution, @max_bucket_sum, and @average_bucket_sum. # The first two are expensive operations. The third is not, but I'm following # Jay Fields's recommendation to build classes with only attributes, rather than # juggling both attributes and instance variables throughout a class's methods. # see http://blog.jayfields.com/2007/07/ruby-lazily-initialized-attributes.html # def distribution @distribution ||= distribute_fairly end def max_bucket_sum @max_bucket_sum ||= distribution.map {|bucket| bucket.sum}.max end # Since the values_array passed to a FairDistribution object might represent a variety of things, # we use max_bucket_sum as a generic method name. Here we provide the more specific method name # requested by the challenge test suite: # alias :time_required :max_bucket_sum def average_bucket_sum @average_bucket_sum ||= values.sum.to_f / num_buckets end private # Distributes the values among the buckets such that each bucket's sums are as equal as possible # Returns the best possible distribution (or one of the best, in case of ties). # # The sort works as follows: # Within each distribution, find the deviance between each bucket's sum and the ideal (average) bucket sum # Sort the distribution's buckets from highest deviance to lowest # Then, sort the distributions as a whole based on these arrays of deviance values # def distribute_fairly num_usable_buckets = num_buckets > values.length ? values.length : num_buckets possible_distributions = values.segmentations(num_usable_buckets) sorted_distributions = possible_distributions.sort_by do |dist| dist.map { |bucket| (average_bucket_sum - bucket.sum).abs }.sort.reverse end sorted_distributions.first end end class Array # Sums the numeric values of a one-dimensional array # Non-numeric values add 0 to the running total # Examples: [1,2,3,'a'].sum => 6 # ['a',[1,2]].sum => 0 # def sum inject(0) {|total, value| value.is_a?(Numeric) ? total + value : total } end # Returns an array of all possible ways to divide self into num_segs segments # This is a combination-style method, i.e. order is not important # Example: [3,4,5].segmentations(2) => [ [[3, 4], [5]], [[3, 5], [4]], [[3], [4, 5]] ] # def segmentations(num_segs) return [[self]] if num_segs == 1 return [ map { |el| [el] } ] if length == num_segs arr_copy = clone nth_el = arr_copy.pop arr_copy.segmentations(num_segs-1).append_to_each(nth_el) + arr_copy.segmentations(num_segs).append_within_each(nth_el) end # These helper methods can't be private, since #segmentations invokes them with specific receivers protected # Appends a new element to the end of each subarray # Assumes an array of dimension == 3, e.g. the array returned by Array#segmentations # Example: [[[3,4]], [[3],[4]]].append_to_each(5) ==> [[[3,4], [5]], [[3],[4],[5]]] # def append_to_each(appendee) map { |el| el << [appendee] } end # Appends a new element within each subarray # Assumes an array of dimension == 3, e.g. the array returned by Array#segmentations # Example: [[[3,4]], [[3],[4]]].append_within_each(5) ==> [[[3,4,5]], [[3,5],[4]], [[3],[4,5]]] # def append_within_each(appendee) result = [] each do |subarray| subarray.each_with_index do |group, j| subarray_copy = subarray.clone subarray_copy[j] = group + [appendee] result << subarray_copy end end result end end