[SUMMARY] Time Window (#144)

Discussion in 'Ruby' started by Ruby Quiz, Oct 25, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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...
     
    Ruby Quiz, Oct 25, 2007
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew Bewley via DotNetMonster.com

    window to window communication (window.opener)

    Andrew Bewley via DotNetMonster.com, Feb 3, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    1,058
    Andrew Bewley via DotNetMonster.com
    Feb 3, 2005
  2. flamesrock
    Replies:
    8
    Views:
    484
    Hendrik van Rooyen
    Nov 24, 2006
  3. 7stud --
    Replies:
    1
    Views:
    93
    Morton Goldberg
    Sep 20, 2007
  4. Ruby Quiz

    [QUIZ] Time Window (#144)

    Ruby Quiz, Oct 19, 2007, in forum: Ruby
    Replies:
    9
    Views:
    142
    Gordon Thiesfeld
    Oct 22, 2007
  5. Replies:
    4
    Views:
    182
Loading...

Share This Page