Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD
From: Derek Cannon on 22 Apr 2010 09:39
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/.

From: steve ross on 23 Apr 2010 14:48
On Apr 23, 2010, at 9:53 AM, Derek Cannon 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
From: Derek Cannon on 23 Apr 2010 01:59
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/.

From: Robert Dober on 23 Apr 2010 18:31
On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon
<novellterminator(a)gmail.com> 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

From: steve ross on 23 Apr 2010 20:08
On Apr 23, 2010, at 3:31 PM, Robert Dober wrote:
>
> On Fri, Apr 23, 2010 at 6:53 PM, Derek Cannon
> <novellterminator(a)gmail.com> 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 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.
 |  Next  |  Last
Pages: 1 2 3
Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD