«

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
--
Posted via http://www.ruby-forum.com/.

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
--
Posted via http://www.ruby-forum.com/.

2010/4/23 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.
> =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[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 =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/

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 Cannon
--
Posted via http://www.ruby-forum.com/.

On Apr 23, 2010, at 9:53 AM, Derek Cannon wrote:
>=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
before(:each) 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=

On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon
<> 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


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

On Apr 23, 2010, at 3:31 PM, Robert Dober wrote:
>=20
> On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon
> <> wrote:
>=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.=

On 23.04.2010 18:53, Derek Cannon 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

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

On Sat, Apr 24, 2010 at 2:08 AM, steve ross <> 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.



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

On Apr 24, 2010, at 1:16 AM, Robert Dober wrote:
>=20
> On Sat, Apr 24, 2010 at 2:08 AM, steve ross <> 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 . ]
>=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 =