Skip to content

@peashutop /jacobhodes.rb secret
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
RPCFN submission
# RPCFN Six: Fair Distribution
# Submitted February 20, 2010
# Slightly revised March 9, 2010
# Author: Jacob Hodes <jacob@peashutop.com>
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.