secret
Last active

RPCFN submission

  • Download Gist
jacobhodes.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.