Skip to content

Instantly share code, notes, and snippets.

@milandobrota
Created October 11, 2009 14:31
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save milandobrota/ba70a62a95cbf461c0e8 to your computer and use it in GitHub Desktop.
require 'spec'
require File.join(File.dirname(__FILE__), 'milandobrota.rb')
describe Array do
it 'should calculate sum' do
[1, 3, 5, 2].sum.should == 11
end
it 'should do a circular shift left' do
a = [1, 2, 3, 4, 5]
a.circular_shl.should == [2, 3, 4, 5, 1]
a.should == [1, 2, 3, 4, 5]
end
it 'should break the fortune wheel' do
[1, 2, 5, 4, 3].spin_to(5).should == [5, 4, 3, 1, 2]
end
end
describe Time do
it 'should convert to a human readable format when in military' do
Time.parse('22:33').to_human.should == "10:33pm"
end
it 'should remove any leading zeroes while converting to a human readable format' do
Time.parse('09:33').to_human.should == "9:33am"
end
end
describe 'FlightTime' do
it 'should subtract times correctly' do
a = Time.parse('03:50')
b = Time.parse('04:10')
subtract_circulary(b,a).should == 20
end
it 'should subtract times correctly in a circular manner' do
a = Time.parse('23:59')
b = Time.parse('00:01')
subtract_circulary(b,a).should == 2
end
it 'should break circularity' do
time1 = Time.parse('21:50')
time2 = Time.parse('23:33')
time3 = Time.parse('00:44')
time4 = Time.parse('00:45')
time5 = Time.parse('00:46')
time6 = Time.parse('00:55')
times = [time4, time2, time3, time6, time1, time5]
break_circularity(times).should == [[time1, time2, time3, time4, time5, time6]]
end
it 'should break circularity multiple times and return multiple results' do
time1 = Time.parse('00:00')
time2 = Time.parse('06:00')
time3 = Time.parse('12:00')
time4 = Time.parse('18:00')
times = [time4, time2, time1, time3]
result = break_circularity(times)
result.should include([time1, time2, time3, time4])
result.should include([time2, time3, time4, time1])
result.should include([time3, time4, time1, time2])
result.should include([time4, time1, time2, time3])
result.size.should == 4
end
it 'should calculate average for sorted times' do
times = []
['23:55', '00:15', '00:35'].each do |time|
times << Time.parse(time)
end
average = average_time_for_sorted(times)
average.hour.should == 0
average.min.should == 15
end
it 'should find average time example 1' do
average_time_of_day(["11:51pm", "11:56pm", "12:01am", "12:06am", "12:11am"]).should == "12:01am"
end
it 'should find average time example 2' do
average_time_of_day(["6:41am", "6:51am", "7:01am"]).should == "6:51am"
end
end
Here is how I solved the problem:
The biggest problem was breaking time circularity. I presented the problem as a circle where each time corresponds to a point. Similar to a clock but with 24 hours instead of 12. So every flight time would correspond to a point on the circle. For the sake of simplicity imagine 2 points somewhere on the circle. Lets say we have 23:00 and 00:00. Next thing was to measure the distance between points. The average time would be right in the middle between those points (on the circle). The critical point was when I realized that there was a longer curve going around. That made another solution mathematically correct (11:30am), but semantically you wouldn't want it to be your average time. So I realized I have to break the circle. What I did was this:
* I sorted the times in an ascending order
* I found the longest curve between points and eliminated it
* The problem turns straight-forward
In order to calculate the average correctly, I subtracted the earliest time (I named it base time) from the other ones (normalized it), converted it into minutes, divided by total number of times and added it to the base time.
And that's it!!!
In case there is more than one longest curve, I did a calculation for every case and returned multiple results.
require 'time'
class Array
def sum
inject(0) {|sum, x| sum+x}
end
def circular_shl
a = self.clone
a << a.shift
end
def spin_to element
first_element_location = self.index(element)
(self * 2).slice(first_element_location, self.size)
end
end
class Time
def to_human
strftime("%I:%M%p").downcase.gsub(/^0/,"")
end
end
def subtract_circulary(time1, time2)
(((time1 - time2) % 86400) /60).round
end
def break_circularity(times)
times.sort!
time_diff = []
shifted_times = times.circular_shl
time_pairs = times.zip(shifted_times)
time_pairs.each do |time1, time2|
time_diff << [time1, time2, subtract_circulary(time2, time1)]
end
sorted = time_diff.sort{|a,b| b[2]<=>a[2]} #sorted by time difference descending
max_difference = sorted[0][2]
start_times = [sorted.first[1]]
(sorted.slice(1..-1)).each do |sorted_item|
if sorted_item[2] == max_difference
start_times << sorted_item[1]
else
break
end
end
results = []
start_times.each do |start_time|
results << times.spin_to(start_time)
end
results
end
def average_time_for_sorted(times)
base_time = times.first
normalized_times = times.collect {|time| subtract_circulary(time, base_time)}
normalized_average = normalized_times.sum/normalized_times.length
base_time + normalized_average * 60
end
def average_time_of_day(times)
time_array = times.collect {|time_string| Time.parse(time_string)}
results = []
break_circularity(time_array).each do |sorted_times|
results << average_time_for_sorted(sorted_times).to_human
end
if results.size > 1
results
elsif results.size == 1
results[0]
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment