Ruby Challenge 2

README

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

#!/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

#!/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

# 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