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.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:
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…