Best way to write this method?

derek · April 22, 2010, 3:39pm

Could my code below be more Ruby-esque or simpler (using Ruby methods I
might not know)?

def range_overlaps?(a, b)
array = a.to_a & b.to_a
!array.empty?
end

def overlaps?(a, b)

Check if days overlap; if not, no reason to continue method

if not range_overlaps?(a.keys, b.keys)
return false
else
a.each_key { |i|
b.each_key { |j|
# Check each element of each array to see if any ranges overlap
if range_overlaps?(a[i], b[j])
return true
end
}
}
end
return false
end

---- Examples of Usage ----
def get_time(s)
temp = s.split("-")
Time.parse(temp[0], Time.now)…Time.parse(temp[1], Time.now)
end

a = {:m => [get_time(“9:00am-10:00am”), get_time(“10:15am-11:45am”)], :w
=> [get_time(“9:00am-10:00am”)]}
b = {:m => [get_time(“10:30am-12:00am”)], :w =>
[get_time(“10:30am-12:00am”)]}
c = {:m => [get_time(“9:00am-10:00am”)], :w =>
[get_time(“9:00am-10:00am”)], :f => [get_time(“9:00am-10:00am”)]}
d = {:t => [get_time(“9:00am-10:00am”)], :r =>
[get_time(“9:00am-10:00am”)]}

puts overlaps?(a,b) # => false
puts overlaps?(a,c) # => true
puts overlaps?(a,d) # => false

derek · April 23, 2010, 7:59am

If you guys need some better clarification as to what these methods do:

Parameter explanation:
Each hash passed into overlaps?(x,y) will have a key (day of the week)
linked to an array of ranges (times through the day).
E.g.
x = { :monday => [1…3, 4…6], :wednesday => [1…3] }
y = { :monday => [1…3], :wednesday => [4…5] }

Methods explanation:
These methods are used to make sure that no two hashes have conflicting
times (ranges in the array for each key) on the same day (same key).

In the above example, the overlaps? method would see that both x and y
hashes have the same keys (meaning they’re on the same days), so it
would continue to investigate the values further. (If they didn’t share
at least one common day, their times could never conflict because they’d
be on different days.)

In the next step, the code compares every range in the array (of every
key) of the two hashes, and ensures that no two times overlap on the
same day.

Does this make it any clearer? Or is no one answering this because I’ve
made it as simple/Ruby-esque as it can get?

Thanks,
Derek

derek · April 23, 2010, 10:33am

2010/4/23 Derek C. [email protected]:

These methods are used to make sure that no two hashes have conflicting
same day.

Does this make it any clearer? Or is no one answering this because I’ve
made it as simple/Ruby-esque as it can get?

I would start out by creating at least two or three classes. One for
what is a Hash in your case (maybe call it TimeTable or such), one for
a list of ranges and maybe one for a TimeRange (which could make sure
parameter values are legal, i.e. in the range 0…23 etc.).

Then I would place those methods in classes appropriate for it and the
code will become much more readable and maintainable.

Regarding the algorithm, I believe you are not checking what you
described in this piece of code:

a.each_key { |i|
b.each_key { |j|
# Check each element of each array to see if any ranges overlap
if range_overlaps?(a[i], b[j])
return true
end
}
}

If I’m not mistaken that will check all days vs. each other. You
probably rather want:

require ‘set’
…
(a.keys.to_set + b.keys).any? do |day|
r1 = a[day]
r2 = b[day]
r1 && r2 && range_overlaps?(r1, r2)
end

(With my suggested change that line would rather look like

r1 && r2 && r1.overlaps? r2

since then you had a class where to stuff the overlap check into.)

Kind regards

robert

derek · April 23, 2010, 6:51pm

You are right about my initial coding being incorrect. I noticed it
hours after first posting, and changed it to:

def elements_overlap?(a, b)
array = a.to_a & b.to_a
!array.empty?
end

def overlaps?(a, b)
if not elements_overlap?(a.keys, b.keys)
return false
else
a.each_key { |i| # :m, :w
if elements_overlap?(a[i], b[i])
return true
end
}
end
return false
end

And I tested it, and it seemed to work in all the following instances:

a = {:monday => [get_time(“9:00am-10:00am”)], :wednesday =>
[get_time(“11:00am-12:00pm”)] }
b = {:monday => [get_time(“11:00am-12:00pm”)], :wednesday =>
[get_time(“9:00am-10:00am”)] }
c = {:tuesday => [get_time(“9:00am-10:00am”)], :thursday =>
[get_time(“11:00am-12:00pm”)] }
d = {:monday => [get_time(“11:00am-12:00pm”)], :wednesday =>
[get_time(“2:00pm-5:00pm”), :friday => [get_time(“9:00am-10:00am”)], ] }
e = {:monday => [get_time(“6:00am-8:00am”), get_time(“9:00am-10:00am”)],
:wednesday => [get_time(“6:00am-8:00am”)] }

M1W2 and M2W1 share times => expected false

puts overlaps?(a, b) # => false

Same times and days => expected true

puts overlaps?(a, a) # => true

Same times; different days => expected false

puts overlaps?(a, c) # => false

Different times, same time F2 as M1W1 => expected false

puts overlaps?(a, d) # => false

Second time on M2 overlaps M1 time => expected true

puts overlaps?(a, e) # => true

I do appreciate your response Robert. If you wouldn’t mind educating me
a little further on your approach to this problem… I don’t understand
how adding multiple classes to this code would be implemented. If you
wouldn’t mind giving me a brief summary of what you’d think would belong
in these classes you purposed, I’d be very grateful!

– Derek C.

derek · April 24, 2010, 12:32am

On Fri, Apr 23, 2010 at 6:53 PM, Derek C.
[email protected] wrote:

Hmm? Do I miss something here?

def arys_distinct? aa, ba
(aa.map(&:to_a).flatten & ba.map(&:to_a).flatten).empty?
end
def overlaps? a, b
a.any?{ |aday, ar|
b.any?{ |bday, br|
aday == bday && !arys_distinct?(ar, br)
}
}
end

derek · April 23, 2010, 8:49pm

On Apr 23, 2010, at 9:53 AM, Derek C. wrote:

def elements_overlap?(a, b)
array = a.to_a & b.to_a
!array.empty?
end

Here’s a simple out-of-bounds comparison for elements_overlap? It makes
the decision with, at most, two comparisons.

require ‘rubygems’
require ‘spec’

def elements_overlap?(a, b)
!((b.first > a.last) || (a.first > b.last))
end

describe “overlapping” do
before(:each) do
@a = [1, 2, 3, 4, 5]
end

it “should overlap if a begins before b, but ends during b” do
elements_overlap?([1, 2, 3, 4, 5], [2, 3, 4, 5, 6]).should be(true)
end

it “should overlap if a begins after b, but ends after b” do
elements_overlap?([4, 5, 6, 7], [2, 3, 4, 5, 6]).should be(true)
end

it “should overlap if a begins after b and ends before b” do
elements_overlap?([4, 5], [2, 3, 4, 5, 6]).should be(true)
end

it “should overlap if a begins before b and ends after b” do
elements_overlap?([1, 2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6]).should
be(true)
end

it “should not overlap if a begins before b and ends before b” do
elements_overlap?([1, 2], [3, 4, 5, 6]).should be(false)
end

it “should not overlap if a begins after b and ends after b” do
elements_overlap?([7, 8], [3, 4, 5, 6]).should be(false)
end
end

derek · April 24, 2010, 10:10am

On 23.04.2010 18:53, Derek C. wrote:

I do appreciate your response Robert. If you wouldn’t mind educating me
a little further on your approach to this problem… I don’t understand
how adding multiple classes to this code would be implemented. If you
wouldn’t mind giving me a brief summary of what you’d think would belong
in these classes you purposed, I’d be very grateful!

Oh, I had thought that I did that already. OK, here’s a short list:

TimeTable

maintains a collection of TimeRange per weekday
responsible for adding and removing TimeRanges
can check for overlap with another TimeTable

TimeRange

a time range within a single day
invariant 0 <= start < end <= 23
can check for overlap with another TimeRange

Overlap checks follow rules you gave.

Btw, I just notice that my implementation was stupid because it does to
much work. This is better

a.any? do |day, r1|
r2 = b[day] and range_overlaps?(r1, r2)
end

Kind regards

robert

derek · April 24, 2010, 2:08am

On Apr 23, 2010, at 3:31 PM, Robert D. wrote:

a.any?{ |aday, ar|
b.any?{ |bday, br|
aday == bday && !arys_distinct?(ar, br)
}
}
end

The algorithm I proposed for overlaps? is (by my count) at worst O(2).
This one looks like at least O(n*m). Maybe I’m wrong about that. In any
case, a good puzzle.

derek · April 24, 2010, 10:16am

On Sat, Apr 24, 2010 at 2:08 AM, steve ross [email protected] wrote:

The algorithm I proposed for overlaps? is (by my count) at worst O(2). This one looks like at least O(n*m). Maybe I’m wrong about that. In any case, a good puzzle.
Ah indeed that was the point I did not understand, it did not seem to
work for all cases. The arrays contain ranges which are not
contiguous. OP’s algorithm does not work either, but you correctly
translated it into an O(1).
[ O(2) is a funny way to say it BTW, but I got the picture ;). ]

Cheers
R.

derek · April 24, 2010, 7:38pm

On Apr 24, 2010, at 1:16 AM, Robert D. wrote:

R.
I missed the discontiguous part of the problem and focused on the
overlap. Still, the same approach works, as time spans are, by
definition ordered. Check the lower boundary, the upper boundary, then
and only then do you check any intermediate ranges. Again, it’s an
interesting problem, but if there are numerous tests it can be
incredibly time consuming because of the number of comparisons. The
pruning I suggest keeps these comparisons to a minimum. Probably
premature optimization, but I happen to know this one

derek · April 24, 2010, 7:42pm

On 4/23/10, steve ross [email protected] wrote:

def elements_overlap?(a, b)
!((b.first > a.last) || (a.first > b.last))
end

This is on the right track to the right implementation, but it won’t
handle this case correctly:
elements_overlap?(0…2,2…3) #=>should be false

derek · April 24, 2010, 8:12pm

On Sat, Apr 24, 2010 at 7:37 PM, steve ross [email protected] wrote:

Cheers
R.

I missed the discontiguous part of the problem and focused on the overlap. Still, the same approach works, as time spans are, by definition ordered. Check the lower boundary, the upper boundary, then and only then do you check any intermediate ranges. Again, it’s an interesting problem, but if there are numerous tests it can be incredibly time consuming because of the number of comparisons. The pruning I suggest keeps these comparisons to a minimum. Probably premature optimization, but I happen to know this one

no I am sorry, look at this example a=[1…2,9…10], b=[ 3…4] if it
were not for this I would write it in O(1) too, it is readable enough
and expanding the ranges looks bad (I know I did that ;).
So finally I like this
def overlaps a, b
a.any?{ |ar| b.any?{ |br| <> } }
end
although O(n*m) it will probably quite fast for reasonable values for
n and m as we loop over the ranges and not the expanded ranges now.
(and use the fast kernel Enumerable methods)

As a side note I am quite surprised that there is no
Enumerable#overlaps? or #distinct?.

Cheers
R.

derek · April 24, 2010, 9:53pm

I’d check out “runt” ]1\ Ruby temporal expressions. I’ve used these
before in a scheduling application to detect scheduling conflicts (two
meetings and attendees availably if they overlap - which seems to be
what you are checking).

Runt allows for English-like expressions

nine_to_ten = REDay.new 9,00,10,00
eighjt_to_eleven = REDay.new 8,00,11,00

mon = DIWeek.new Mon
wef = DIWeek.new Wed

mon_8_11 = mon & eight_to_eleven
wed_9_10 = wed & nine_to_eleven

These are based on Martin F.'s Temporal Expressions.

[1] http://runt.rubyforge.org/

Cheers,
Ed

Ed Howland

http://twitter.com/ed_howland