Best way to write this method?

[Derek Cannon]

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, 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 Cannon]

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

 

[Robert Klemme]

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.
=A0x =3D { :monday =3D> [1..3, 4..6], :wednesday =3D> [1..3] }
=A0y =3D { :monday =3D> [1..3], =A0 =A0 =A0 :wednesday =3D> [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?

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, 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 =3D a[day]
r2 =3D 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

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Derek Cannon]

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, b)
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 Cannon

 

[steve ross]

=20
def elements_overlap?(a, b)
array =3D 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
beforeeach) do
@a =3D [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=

 

[Robert Dober]

On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon

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

 

[steve ross]

=20
On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon
=20
Hmm? Do I miss something here?
=20
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 =3D=3D 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.=

 

[Robert Klemme]

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

 

[Robert Dober]

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.

 

[steve ross]

=20

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 . ]
=20
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 =

 

[Caleb Clausen]

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

 

[Robert Dober]

This one looks like at least O(n*m). Maybe I'm wrong about that. In any cas=
e, 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.

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 ch=
eck any intermediate ranges. Again, it's an interesting problem, but if the=
re are numerous tests it can be incredibly time consuming because of the nu=
mber of comparisons. The pruning I suggest keeps these comparisons to a min=
imum. Probably premature optimization, but I happen to know this one
no I am sorry, look at this example a=3D[1..2,9..10], b=3D[ 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| <<your code here>> } }
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.

--=20
The best way to predict the future is to invent it.
-- Alan Kay

 

[Ed Howland]

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 =3D REDay.new 9,00,10,00
eighjt_to_eleven =3D REDay.new 8,00,11,00

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

mon_8_11 =3D mon & eight_to_eleven
wed_9_10 =3D wed & nine_to_eleven

These are based on Martin Fowler's Temporal Expressions.

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

Cheers,
Ed

Ed Howland
http://greenprogrammer.wordpress.com
http://twitter.com/ed_howland



This one looks like at least O(n*m). Maybe I'm wrong about that. In any ca=
se, 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.

I missed the discontiguous part of the problem and focused on the overla=

p. 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 c=
heck any intermediate ranges. Again, it's an interesting problem, but if th=
ere are numerous tests it can be incredibly time consuming because of the n=
umber of comparisons. The pruning I suggest keeps these comparisons to a mi=
nimum. Probably premature optimization, but I happen to know this one

no I am sorry, look at this example a=3D[1..2,9..10], b=3D[ 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
=A0a.any?{ |ar| b.any?{ |br| <<your code here>> } }
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.