secret
Last active

  • Download Gist
average_time_of_day.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
# Himansu Desai (himansudesai@hotmail.com)
 
require 'cyc_time.rb'
require 'set.rb'
 
=begin
Program Notes:
-------------------
1. The algorithm/approach was more interesting for this problem than actual coding techniques + the code was getting large so
an attempt was made to reduce program size by not doing much error checking or other features that would be needed in a
real deployed application. Hopefully that does not disqualify my contest entry.
2. The program was shortened to not use optargs or spit out useful error messages to the user. It does not accept spaces
between times. Hopefully this will not disqualify the entry. The program can be used as:
ruby average_time_of_day "7:01am","7:02am","7:03am" - without space after the comma.
 
Algorithm Notes:
---------------------
1. Times are assumed to fall within a contiguous 24 HOUR period. There seemed no other obvious ways to deal with this. If the
flight arrives at 2pm and 3pm, there is no way to know if it is 3pm the next day or 10 days from now or 1 day early. So all times
are treated as falling within one circular 24 hr period.
2. Given a set of times, a chain of segments are created between them to do further analysis.
3. Time is treated as cyclical. A "segment" has two times (head and tail) and a length in minutes. Given two times, there can only
be one segment between them, the one that yields in a smaller segment. For example, between 7pm and 6am, there is a segment
with 7pm as the head and 6am as the tail and it is 11 hrs long. The other segment with 6am as the head would be 13 hrs long and
is not valid. If the times are exactly 12 hrs off, then we take any one of the two segments for further analysis.
4. Out of multiple valid segments that have time t1 as the 'head', take the shortest one of them and that is the ONE segment with
t1 as the head that we will now use for creating a chain
5. Given a chain of segments, it can be "closed" or "open". For example, the 3 segments
7pm(head)-->1am(tail)
1am(head)-->4am(tail) and
4am(head)-->6am(tail)
constitute an open chain because there is no valid segment from 6am to 7pm closing it. On the other hand, the 4 segments
7pm(head)-->1am(tail)
1am(head)-->4am(tail) and
4am(head)-->10am(tail)
10am(head)-->7pm(tail)
constitute a closed chain because the tail of the last segment is the head of the first.
 
a) For open chains, it is easy - use the head of the first segment as the head of the entire chain. Compute differences from that head
time and then add the average difference back to the head time to get the average flight arrival time. NOTE: If there is more than
one arrival at the same time, this averaging method give extra weight to that time because that time will be counted multiple times.
b) For close chains, throw out the "largest" segment. What remains is the chain we use to compute the average per (a) above. The
idea is that time is circular so we pick the times that are closely clustered together to figure out when the "earliest" (head of the chain)
arrival time is and when the "latest" (tail of the chain) is.
Consider 7pm, 12am, 5am, 10am. The way we know 7pm as the earliest time and 10am as the latest time (instead of any other
combination) is that the segment from 10am to 7pm is 9hrs long which is longer than any of the other 5 hr segments.
6. Times can be uniformly spread across a 24 hr period - For example 12:10am, 12:10pm, 6:10am, 6:10pm
a) Uniform spread with no duplicates - OUT OF LUCK. You don't have a good guess on when you need to be at the airport
b) Uniform spread with duplicate times - Take the time with the largest recurrence and suggest that to the user as when the plane is
most likely to arrive.
=end
 
all_times = []
ARGV.first.split(",").each do |e|
all_times << CycTime.new(e)
end
 
unique_times = CycTime.remove_duplicates(all_times)
 
duplicate_times = (unique_times.size < all_times.size) ? true : false
 
segments = CycTime.compute_segments(unique_times)
if (segments.size == 1)
seg = segments[segments.keys[0]]
head = seg[:head]
tail = seg[:tail]
diff = ( tail.minutes_from(head) / 2).to_i
avg_time = head.add(diff)
puts "Average flight arrival time = #{avg_time}"
else
seg_chain = CycTime.analyze_segments(segments)
if (seg_chain[:uniform_segments])
if (!duplicate_times)
puts "WARNING! Times are uniformly distributed over a 24 hours period. Show up at the airport when you can."
else
time = CycTime.most_repeating(all_times)
puts "Average flight arrival time = #{time}"
end
else
head = seg_chain[:head]
total_time = 0
all_times.each do |t|
total_time += t.minutes_from(head)
end
avg_diff = (total_time / (all_times.size)).to_i
puts "#{head.add(avg_diff)}"
end
end
cyc_time.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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
# Himansu Desai (himansudesai@hotmail.com)
 
class CycTime < Object
attr_accessor :hrs, :mins, :pm
class CycSegment < Struct.new(:head, :tail, :mins); end
class CycSegmentChain < Struct.new(:head, :uniform_segments); end
 
def self.remove_duplicates(times)
h = Hash.new
midnight = CycTime.new("12:00am")
times.each {|t| h[t.minutes_from(midnight)] = t}
s = Set.new
h.each_value { |t| s << t}
s
end
 
def self.most_repeating(times)
h = Hash.new
midnight = CycTime.new("12:00am")
times.each do |t|
mins = t.minutes_from(midnight)
end
times.each { |t| (h[t] == nil) ? h[t] = 1 : h[t] = h[t] + 1}
max_count = 0
max_time = nil
h.each_pair { |time, count| if h[time] > max_count then max_count = h[time]; max_time = time; end }
max_time
end
 
def self.compute_segments(times)
segments = {}
times.each do | t |
compare_list = times.clone.delete(t)
short_seg = segments[t]
compare_list.each do |other|
cur_seg = t.circ_segment(other)
short_seg = cur_seg if ( (cur_seg[:head] == t) && ((short_seg == nil) || (short_seg[:mins] > cur_seg[:mins]) ))
end
segments[t] = short_seg if (short_seg != nil)
end
segments
end
 
def self.analyze_segments(segments)
segs = segments.clone
head_seg = tail_seg = segs.delete(segs.keys[0])
count = segs.size
while (count > 1)
segs.each_pair do |time, seg|
if (seg[:tail] == head_seg[:head])
head_seg = seg
count -= 1
segs.delete(time)
break
elsif (seg[:head] == tail_seg[:tail])
tail_seg = seg
count -= 1
segs.delete(time)
break
end
end
end
last_seg = segs[segs.keys[0]]
if (last_seg[:head] == tail_seg[:tail])
tail_seg = last_seg
end
if (last_seg[:tail] == head_seg[:head])
head_seg = last_seg
end
if (head_seg == tail_seg)
seg_size = nil
identical = true
segments.each_value do |seg|
seg_size = seg[:mins] if (seg_size == nil)
identical = false unless seg[:mins] == seg_size
end
if identical then return CycSegmentChain.new(segments[segments.keys[0]][:head], true); end
 
largest_seg = nil
segments.each_pair { |time, seg| largest_seg = seg if ( (largest_seg == nil) || (seg[:mins] > largest_seg[:mins]) ) }
return CycSegmentChain.new(largest_seg[:tail], false)
else
return CycSegmentChain.new(head_seg[:head], false)
end
end
 
def add(mins)
am_pm = self.pm
add_hrs = mins / 60
add_mins = mins % 60
new_mins = self.mins + add_mins
if (new_mins > 59)
new_hrs = self.hrs + add_hrs + 1
new_mins = new_mins - 60
else
new_hrs = self.hrs + add_hrs
end
if (new_hrs > 11)
new_hrs = new_hrs - 12
am_pm = !am_pm
end
if (new_hrs == 0) then new_hrs = 12; end
as_str(new_hrs, new_mins, am_pm)
# new_mins = "#{new_mins}".rjust(2, '0')
# str = "#{new_hrs}:#{new_mins}#{(am_pm) ? 'pm' : 'am'}"
# str
end
 
def to_s
as_str(self.hrs, self.mins, self.pm)
# two_digit_mins = "#{self.mins}".rjust(2, '0')
# "#{self.hrs}:#{two_digit_mins}#{(self.pm) ? 'pm' : 'am'}"
end
 
def mins_12hr_format
(self.hrs == 12) ? (self.mins) : (self.hrs * 60) + self.mins
end
 
def minutes_from(time)
if (self.pm == time.pm)
diff = self.mins_12hr_format - time.mins_12hr_format if (self.pm == time.pm)
return (diff < 0) ? (1440 - diff) : diff
end
return 720 - (time.mins_12hr_format) + self.mins_12hr_format
end
 
def initialize(time)
if (time =~ /\d*:\d*\a*/)
time =~ /(\d*):(\d*)(\D*)$/
self.hrs = $1.to_i
self.mins = $2.to_i
self.pm = false
self.pm = true if ($3 == 'pm')
end
end
 
def circ_segment(other)
if (self.pm == other.pm)
if (other.mins_12hr_format > self.mins_12hr_format)
return CycSegment.new(self, other, (other.mins_12hr_format - self.mins_12hr_format))
else
return CycSegment.new(other, self, (self.mins_12hr_format - other.mins_12hr_format));
end
else
bigger = other; smaller = self
if (self.mins_12hr_format > other.mins_12hr_format) then bigger = self; smaller = other; end
return CycSegment.new(bigger, smaller, (720 - bigger.mins_12hr_format) + smaller.mins_12hr_format)
end
end
 
private
def as_str(h, m, pm)
two_digit_mins = "#{m}".rjust(2, '0')
"#{h}:#{two_digit_mins}#{(pm) ? 'pm' : 'am'}"
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.