secret
Last active

  • Download Gist
fair_distribution.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
# 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
test_shuffle.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
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}%"

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.