-
-
Save peashutop/a460231c78f2a90180ab to your computer and use it in GitHub Desktop.
RPCFN submission
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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