by Brian Candler
Write a Ruby class which can tell you whether the current time (or any given time) is within a particular "time window". Time windows are defined by strings in the following format:
# Sat Sun # all day Sat and Sun, no other times
# Sat Sun 0700-0900 # 0700-0900 on Sat and Sun only
# Mon-Fri 0700-0900 # 0700-0900 on Monday to Friday only
# Mon-Fri 0700-0900; Sat Sun # ditto plus all day Sat and Sun
# Fri-Mon 0700-0900 # 0700-0900 on Fri Sat Sun Mon
# Sat 0700-0800; Sun 0800-0900 # 0700-0800 on Sat, plus 0800-0900 on Sun
Time ranges should exclude the upper bound, i.e. 0700-0900 is 07:00:00 to 08:59:59. An empty time window means "all times everyday". Here are some test cases to make it clearer:
def test_window_1
w = TimeWindow.new("Sat-Sun; Mon Wed 0700-0900; Thu 0700-0900 1000-1200")
assert ! w.include?(Time.mktime(2007,9,25,8,0,0)) # Tue
assert w.include?(Time.mktime(2007,9,26,8,0,0)) # Wed
assert ! w.include?(Time.mktime(2007,9,26,11,0,0))
assert ! w.include?(Time.mktime(2007,9,27,6,59,59)) # Thu
assert w.include?(Time.mktime(2007,9,27,7,0,0))
assert w.include?(Time.mktime(2007,9,27,8,59,59))
assert ! w.include?(Time.mktime(2007,9,27,9,0,0))
assert w.include?(Time.mktime(2007,9,27,11,0,0))
assert w.include?(Time.mktime(2007,9,29,11,0,0)) # Sat
assert w.include?(Time.mktime(2007,9,29,0,0,0))
assert w.include?(Time.mktime(2007,9,29,23,59,59))
end
def test_window_2
w = TimeWindow.new("Fri-Mon")
assert ! w.include?(Time.mktime(2007,9,27)) # Thu
assert w.include?(Time.mktime(2007,9,28))
assert w.include?(Time.mktime(2007,9,29))
assert w.include?(Time.mktime(2007,9,30))
assert w.include?(Time.mktime(2007,10,1))
assert ! w.include?(Time.mktime(2007,10,2)) # Tue
end
def test_window_nil
w = RDS::TimeWindow.new("")
assert w.include?(Time.mktime(2007,9,25,1,2,3)) # all times
end
end
Quiz Summary
I've said it before, and I'll say it again this time: I love the easy problems. I'm always impressed by the creativity in the solutions for them. The tricks solvers manage to sneak into their code are so great. Let me show you a few highlights from this week's solutions.
For the first trick, let's have a peek at Eric's send()-changes-the-rules comparison:
# Equality is defined as a TimeSpecifier on the RHS being in the
# this range.
def ==(time_spec)
# do either a < or a <= when comparing the end of the range
# depending on value of @include_end
end_comparison = @include_end ? :<= : :<
# NOTE: the call to the send method below is used to call the
# method in end_comparison
if @start_t < @end_t
time_spec >= @start_t && time_spec.send(end_comparison, @end_t)
else # a reverse range, such as "Fri-Mon", needs an ||
time_spec >= @start_t || time_spec.send(end_comparison, @end_t)
end
end
# ...
In this code Eric is doing a range inclusion test. The interesting aspect is that the range can include or exclude the end point, just like Ruby's native Range class. To handle that, Eric sticks a Symbol for a comparison operator in a variable and lets send() sort it out during the actual comparison.
Here's another trick, this time from Gordon. It's a terrific yet simple recursive parser for the time formats allowed by this quiz:
#recursive method to parse input string
def parse(token)
case token
when ""
REWeek.new(0)
when /^(.+);(.+)/ # split at semicolons
parse($1) | parse($2)
when /(\D+) (\d.+)/ # split days and times
parse($1) & parse($2)
when /(\D+) (\D+)/, /(\d+-\d+) (\d+-\d+)/ # split at spaces
parse($1) | parse($2)
when /([A-Z][a-z][a-z])-([A-Z][a-z][a-z])/ # create range of days
REWeek.new(Runt.const_get($1), Runt.const_get($2))
when /([A-Z][a-z][a-z])/ # create single day
DIWeek.new(Runt.const_get($1))
when /(\d\d)(\d\d)-(\d\d)(\d\d)/ #create time range
start = Time.mktime(2000,1,1,$1.to_i,$2.to_i)
# 0600-0900 should work like 0600-0859,
stop = Time.mktime(2000,1,1,$3.to_i,$4.to_i) - 1
REDay.new(start.hour, start.min, stop.hour, stop.min)
end
end
# ...
To understand this code, you need to know that Gordon used Runt to do the actual time comparisons. Runt's time objects (REWeek, DIWeek, and REDay) can be "anded" and "ored" together using the & and | operators. Have a look at how elegant that makes the above parser.
I'm going to simplify the code a bit to show this next one, but the idea is straight out of Ken's solution. Have a look at how he handles optional captures in a regular expression:
DAY_RE = /\b(?:#{DAYS.join("|")})\b/
DAYS_RE = /(#{DAY_RE})(?=[;\s]|$)|(#{DAY_RE})-(#{DAY_RE})/
def show_match(day_str)
day_str.scan(DAYS_RE) do |day, start_day, end_day|
day &&= DAYS.index(day)
start_day &&= DAYS.index(start_day)
end_day &&= DAYS.index(end_day)
p [day, start_day, end_day]
end
end
show_match("Mon; Wed-Fri")
# >> [1, nil, nil]
# >> [nil, 3, 5]
The interesting part here was the use of the &&= operator. This Regexp can match in two ways: a single day name or two day names as a range. Because of that, we don't know which variables will be set inside the scan() block. Ken shows that this doesn't really matter though, as we can perform index conversion on just those that are set with a little operator magic.
To show a final trick, don't forget that you can get a free initialize() method plus accessors from Struct to bootstrap your class building. This is a classic Ruby idiom and we saw it in two different forms this week. First, using inheritance by Philip:
# ...
class Range < Struct.new(:day_parts, :time_parts)
# ...
end
end
Or using the under-documented block parameter to the constructor as Yossef showed:
class TimeInterval
# ...
UnboundTime = Struct.new(:hour, :minute) do
# ...
end
# ...
end
Alright, enough fancy stuff. Let's get to a solution already.
Last week, Jesús had the huge all-features-included solution, but this week he gives us the the short and sweet version. Let's examine that below.
Jesús breaks the problem down into two classes. The first class represents some range of time:
class TimeRange
def initialize(s)
@day_of_week = []
@hour = []
s.strip.split(" ").each do |range|
if (match = range.match(/(\d{4})-(\d{4})/))
@hour << (match[1].to_i...match[2].to_i)
elsif (match = range.match(/([a-zA-Z]{3})-([a-zA-Z]{3})/))
first = Time::RFC2822_DAY_NAME.index(match[1])
second = Time::RFC2822_DAY_NAME.index(match[2])
if (first < second)
@day_of_week << (first..second)
else
@day_of_week << (first..(Time::RFC2822_DAY_NAME.size-1))
@day_of_week << (0..second)
end
else
@day_of_week << ( Time::RFC2822_DAY_NAME.index(range) ..
Time::RFC2822_DAY_NAME.index(range) )
end
end
end
# ...
This is the main parser for the solution. It tokenizes a given time range and processes hour ranges, day ranges, and individual days. All of these pieces are added to the @day_of_week and @hour Arrays as Ranges representing the times they include. Days are handled as indexes in an Array loaded by the Ruby standard library and hours and minutes are converted to simple Integers.
The thing to note in the parser is how days are handled. First, a Range of days can be tricky index-wise. For example, Friday to Sunday would be the Range 5..0 and that doesn't make sense. To handle that, Jesús adds two Ranges in such cases: 5..6 and 0..0 for our example. Then Ruby's standard Range membership tests will function for the problem. Single days are treated similarly by adding a Range with the same start and end point.
Let's have a look at the rest of that class:
def include?(time)
dow = time.wday
hour = time.strftime("%H%M").to_i
any?(@day_of_week, dow) and any?(@hour, hour)
end
def any?(enum, value)
return true if enum.empty?
enum.any?{|x| x.include?(value)}
end
end
# ...
Together, these methods tell if a passed Time object occurs in this TimeRange. The include?() method first converts the Time object into the formats stored in the internal Range objects. After that, a hand-off is made to any?() to verify that both the days and times match-up.
The last step is to wrap these TimeRange objects in the interface dictated by the quiz:
class TimeWindow
def initialize(s)
@ranges = []
s.split(";").each do |part|
@ranges << TimeRange.new(part)
end
end
def include?(time)
return true if @ranges.empty?
@ranges.any? {|x| x.include?(time)}
end
end
Creating a TimeWindow is as simple as, split()ing the input on ";" characters and creating a new TimeRange from each chunk. This makes the include?() test trivial as well, since it can just forward the call to all of the TimeRange objects and see if any of them accept.
My usual thanks to all for being so creative and giving me cool examples to show off in this summary.
Tomorrow we will dig into just how editors are constructed...
