-
-
Save linki/9693f6996d461351437f to your computer and use it in GitHub Desktop.
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
# | |
# generates all possible distributions by splitting job list in distinct non empty subcollections with the help of Array's combination method | |
# then finds the best (see Array#chunk and FairDistribution#find_best_distribution for detailed explanation) | |
# | |
class Array | |
# | |
# returns the sum of all elements | |
# | |
# note: works best with homogenous numeric collections | |
# | |
def sum | |
inject(:+) | |
end | |
# | |
# calls array's combination method for each value in range and passes the block to it | |
# | |
# note: block must be given, unlike Array#combination | |
# | |
def combination_with_range(range, &block) | |
raise ArgumentError.new('please provide a block') unless block_given? | |
range.each do |chunk_size| | |
combination(chunk_size, &block) | |
end | |
end | |
# | |
# deletes each element of items only once in self | |
# | |
# unlike Array#- that deletes multiple items if eql? is true | |
# that is especially bad when dealing with duplicate integer values in a collection, like in this challenge | |
# | |
def delete_first(items) | |
items = [items] unless items.respond_to?(:each) | |
items.each do |item| | |
delete_at(index(item)) | |
end | |
self | |
end | |
# | |
# returns all possible combinations of distinct non empty subcollections that when unioned equal self | |
# if more than two subcollections are requested, calls itself recursive on the second chunk | |
# | |
# huh? | |
# | |
# computes all subcollections with minimum length of one and maximum length of all elements minus the number of the remaining chunks, | |
# so that every chunk can have at least one element | |
# | |
# that collection forms all possible combinations for the first chunk (order is ignored) | |
# | |
# for each of those combinations computes the collection of the remaining elements, that is the difference of self and that combination | |
# (duplicate items are only removed once per item in the second collection) | |
# | |
# both collections are combined and form one possible result which gets collected and finally returned | |
# | |
# if more than two chunks are requested the second subcollection gets recursively chunked in (chunks - 1) chunks | |
# the two collections are then combined by prepending the first collection to each element of the second collection | |
# | |
def chunk(chunks) | |
raise ArgumentError.new('please choose at least two chunks') if chunks < 2 | |
results = [] | |
min_chunk_size, max_chunk_size = 1, size - (chunks - 1) | |
combination_with_range(min_chunk_size..max_chunk_size) do |taken_items| | |
remaining_items = dup.delete_first(taken_items) | |
if chunks == 2 | |
results << [taken_items, remaining_items] | |
else | |
remaining_items.chunk(chunks - 1).each do |remaining_piece| | |
results << remaining_piece.unshift(taken_items) | |
end | |
end | |
end | |
results | |
end | |
end | |
class FairDistribution | |
def initialize(jobs, number_of_presses) | |
@jobs = jobs | |
@number_of_presses = number_of_presses | |
end | |
# | |
# required time is the time of the slowest press | |
# | |
def time_required | |
@time_required ||= distribution.map(&:sum).max | |
end | |
# | |
# returns the distribution considered as best | |
# | |
def distribution | |
@distribution ||= find_best_distribution | |
end | |
private | |
# | |
# computes and returns best distribution | |
# | |
# that is the distribution with the lowest required time | |
# if more than one distribution is found, returns the first one with the lowest standard deviation | |
# | |
# how: | |
# gets all possible distributions, | |
# for each one it computes the required time and standard deviation if needed, | |
# remembers the best, returns the best | |
# | |
# Array#chunk does the hard work | |
# | |
def find_best_distribution | |
required_time, best_distribution = nil, nil | |
all_distributions = @jobs.chunk(@number_of_presses) | |
all_distributions.each do |distribution| | |
time_required_by_distribution = distribution.map(&:sum).max | |
if required_time.nil? || time_required_by_distribution < required_time | |
best_distribution = distribution | |
required_time = time_required_by_distribution | |
else | |
if time_required_by_distribution == required_time | |
best_distribution = distribution if standard_deviation(distribution) < standard_deviation(best_distribution) | |
end | |
end | |
end | |
best_distribution | |
end | |
# | |
# returns the standard deviation of the given distribution | |
# | |
# (thanks for finally making me understand what standard deviation is all about :) | |
# | |
def standard_deviation(distribution) | |
u = distribution.map(&:sum).sum / distribution.size | |
Math.sqrt(distribution.map(&:sum).map{|x| (x-u)**2}.sum / distribution.size) | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment