-
-
Save eregon/43c82d5127d5d05ebe2e 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
# RPCFN6: Fair Distribution | |
# Benoit Daloze | |
# | |
# I used some random strategy to keep things really fast, with a simple algorythm of adding a job in the Press with the less time | |
# Enjoy :) | |
# Let's add some more 'literal' methods to Array. That is easier(and lighter) to maintain than creating classes. | |
class Array | |
def sum | |
self.inject(:+) | |
end | |
def average | |
sum.to_f / length | |
end | |
def standard_deviation | |
Math.sqrt( 1.0/length * ( map { |x_i| x_i**2 }.sum ) - average**2 ) | |
end | |
# time of: | |
# - a Distribution = the maximum time needed by a press | |
# - a Press = The sum of the times of the jobs | |
def time | |
@time ||= begin | |
if Array === first # Distribution | |
times.max | |
else # Press | |
sum | |
end | |
end | |
end | |
# Distribution methods | |
def times | |
map { |press| press.time } | |
end | |
end | |
class FairDistribution | |
def initialize(jobs, presses) | |
@jobs, @presses = jobs, presses | |
end | |
def time_required | |
distribution.time | |
end | |
def distribution | |
@distribution ||= begin | |
# We got here many ways, because I'm simply adding a job in the Press that takes the less time | |
# 1) Sure way, far too long | |
# jobs_sets = @jobs.permutation # len! test3(11) => 39 916 800 | |
# 2) Very fast way, but doesn't work for test_basic4 | |
# jobs_sets = [ | |
# @jobs, | |
# @jobs.sort, | |
# @jobs.sort.reverse | |
# ] | |
# 3) Cool&Fast way, solve all(100%) with **4(in 1.1s) and often(92%) with **3(in 0.1s) | |
# 97/100 with **3.3(in 0.2s !) | |
jobs_sets = (@jobs.length**3.3).to_i.times.map { @jobs.shuffle } | |
bad_distribution = [ Array.new(@presses, [@jobs.sum]) ] | |
jobs_sets.inject(bad_distribution) { |good_dists, jobs| | |
# First choice: the less time for the distribution | |
dist = jobs.each_with_object( Array.new(@presses) { [] } ) { |job, presses| | |
presses.min_by { |p| p.sum or 0 } << job # We add the job to the Press that takes (currently) the less time | |
} | |
max, best = dist.time, good_dists.first.time | |
# Some optimisation: keep only the best time(s) | |
if max < best # We want to keep the fastest, and drop the others | |
[dist] | |
elsif max == best # Another good candidate: we add it | |
good_dists << dist | |
else # A slower Distribution, we discard it | |
good_dists | |
end | |
}.min_by { |presses| | |
# Second choice: minimal standard deviation of times of each Press of the Distribution | |
presses.times.standard_deviation | |
} | |
end | |
end | |
end | |
if __FILE__ == $0 | |
jobs = [10, 15, 20, 24, 30, 45, 75] | |
number_of_presses = 2 | |
exp_max = 110 | |
fd = FairDistribution.new(jobs, number_of_presses) | |
p "#{fd.time_required} must be #{exp_max}" | |
p fd.distribution | |
end |
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
n = 100 | |
ruby = '/path/to/ruby' | |
error_counter = 0 | |
n.times { | |
result = `#{ruby} test_solution_acceptance.rb full` | |
# Started | |
# ..F.. | |
# Finished | |
result =~ /Started\n([.F]{5})\nFinished/ | |
results = $1.chars.map { |t| t == '.' } | |
errors = results.count(false) | |
if errors > 1 | |
puts "#{errors} errors!" | |
print '^' | |
elsif errors == 1 | |
error_counter += 1 | |
print 'v' | |
else | |
print '.' | |
end | |
} | |
puts "#{error_counter} errors/#{n} tests = #{((n-error_counter).to_f/n*100).round}%" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment