[SUMMARY] Time Window (#144)

[Ruby Quiz]

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:

DAYS = %w[Sun Mon Tue Wed Thu Fri Sat]
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 TimeWindow
# ...

class Range < Struct.newday_parts, :time_parts)
# ...
end
end

Or using the under-documented block parameter to the constructor as Yossef
showed:

# ...

class TimeInterval
# ...

UnboundTime = Struct.newhour, :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:

require '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...