Create a gist now

Instantly share code, notes, and snippets.

@loicpaillotin /README Secret
Created Oct 14, 2009

What would you like to do?
Ruby Challenge 2
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:
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
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 (
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.
$:.unshift File.join(File.dirname(__FILE__), '..', 'lib')
require "time"
require "mean_array"
require "solution"
def average_time_of_day (times)
solutions =
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[i] += 86400
solutions << new
permutations << new
# 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
# Compute and cache mean (average, I mean... nevermind)
def mean
unless @a_mean
@a_mean = sum.to_f / size
def sum
mysum = 0
each { |val| mysum+=val }
# 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
# Solution computing and printing
class Solution
@@time_cache = {}
def initialize
@solutions = {}
# 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,
if p_std_error < @solutions[p_mean][:std_error]
@solutions[p_mean][:std_error] = p_std_error
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)
# 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
# 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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment