secret
Last active

Ruby Challenge 2

  • Download Gist
README
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
Content:
1. How I chose to solve the problem
2. Usage
3. Strange behavior of Time.parse
4. Copyright
 
1. How I chose to solve the problem
 
As stated, the problem is ambiguous. Given the following array:
["11:00pm","2:00am","3;00am"]
 
We cannot, without additionnal information, know if the plane is meant to arrive at:
- 11pm, and was once 3 hours late and then 4 hours late
- 2am and was once 3 hours early and once 1 hour late
- 2am and was once 1 hour late, and once 21 hours late
etc...
 
So I basically chose to find all those permutations, find the average and calculate the standard error for each.
The lowest standard error is normally the "right" solution, but you have to decide that as a human.
 
Additionnaly, the algorithm is able to tell you that with this input: [6am, 6pm], there are 2 solutions that are strictly equivalent
(same standard error).
 
The problem is that I have to calculate this for every possible permutation, ie 2^n where n is my number of args.
While there is only n possible average, I have to check the std error in each permutation.
 
As you can guess, if there is too many arguments, the program just takes forever. I never tested beyond 18.
 
Since the algorithm already scales very badly, I tried to cache a lot of things, since a lot of the calculus are essentially the same.
While the performance boost is noticeable, it only push back the problem a few steps further.
 
2. Usage
 
This works in ruby 1.8 and 1.9.
Sorry I wanted to do a nice bin/ and lib/ structure, but can't figure how to do that in gist, so...
irb -r loicpaillotin.rb
 
then call average_time_of_day(["9:02pm","9:12pm","9:12pm","9:23pm"])
 
3. Strange behavior of Time.parse
 
I encountered a strange behavior of Time.parse during my dev.
 
For example Time.parse( (84423.0).to_s works
Time.parse( (180.0).to_s fails
 
It turns out that Date._parse returns a hash like this { :min => 1, :sec 80 }
Which of course makes Time.parse fail.
 
I am not sure that Time.parse was intended to be used that way, but I find it confusing anyways. It either should or shouldn't work,
not work some of the times and fail some of the time.
 
4. Copyright Loic Paillotin (http://www.loicpaillotin.com/)
 
I doubt this is of any use outside of the Ruby Learning Challenge, but if it is, feel free to do whatever with this code.
loicpaillotin.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
#!/usr/bin/ruby
$:.unshift File.join(File.dirname(__FILE__), '..', 'lib')
 
require "time"
require "mean_array"
require "solution"
 
def average_time_of_day (times)
solutions = Solution.new
 
Solution.convert_time_to_minutes!(times)
 
permutations = [ times ]
 
# first permutation to process is the input.
solutions << times
 
i = 0
while i < times.length do
max = permutations.length
j = 0
while j < max do
new = permutations[j].dup
new.clean
new[i] += 86400
 
solutions << new
permutations << new
 
j+=1
end
i+=1
end
 
solutions.pretty_print
end
mean_array.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
#!/usr/bin/ruby
# Adding mean and std_error to Array, with cleaning of cache to be called when
# In our problem, the array is not going to be modified so I can cache the values
# I calculated. This is not designed to be used outside of this particular context.
#
class Array
# Reset cached values
def clean
@a_mean = nil
@a_std_error = nil
end
 
# Compute and cache mean (average, I mean... nevermind)
def mean
unless @a_mean
@a_mean = sum.to_f / size
end
@a_mean
end
 
def sum
mysum = 0
each { |val| mysum+=val }
mysum
end
 
# Compute and cache std_error. I divide it by 60 so that it is roughly
# the order of magnitude of minutes.
def std_error
unless @a_std_error
m = mean()
mysum = 0
each { |val| mysum+= (val-mean)**2 }
@a_std_error = (Math.sqrt(mysum)) / 60
end
@a_std_error
end
end
solution.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
# Solution computing and printing
class Solution
 
@@time_cache = {}
 
def initialize
@solutions = {}
end
 
# calculates the mean for the array and store the solution.
def <<(permutation)
p_std_error = permutation.std_error
p_mean = Solution.minutes_to_readable(permutation.mean)
 
if not @solutions[p_mean]
@solutions[p_mean] = {
:array => permutation,
:std_error => p_std_error,
:mean => p_mean,
}
else
if p_std_error < @solutions[p_mean][:std_error]
@solutions[p_mean][:std_error] = p_std_error
end
end
end
 
def pretty_print
puts "The solution with the lowest standard error is probably the one you are looking for " +
"but I can't be certain since the input is ambiguous"
 
@solutions.keys.sort_by { |k| @solutions[k][:std_error] }.each do |key|
puts "\tMean: #{key}\tStd error: " + sprintf("%.02f",@solutions[key][:std_error].to_s)
end
end
 
# Converts original time to seconds
#
def self.convert_time_to_minutes!(times)
base_time = Time.parse("0:00am")
times.each_index do |i|
times[i] = Time.parse(times[i]) - base_time
end
end
 
# See README for my discoveries about Time.parse
# I cache the result since I'm likely to encounter the same conversion a large
# number of times, see README if you want to now why
#
def self.minutes_to_readable(t)
unless @@time_cache[t]
t = t.to_i
mins = (t/60) % 60
hours = (t/3600) % 24
t = Time.parse("#{hours}:#{mins}")
@@time_cache[t] = t.strftime("%I:%M%p")
end
@@time_cache[t]
end
 
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.