Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD
From: Robert Klemme on 24 Apr 2010 04:06
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/
From: Robert Dober on 24 Apr 2010 04:16
On Sat, Apr 24, 2010 at 2:08 AM, steve ross <cwdinfo(a)gmail.com> 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

From: steve ross on 24 Apr 2010 13:37
On Apr 24, 2010, at 1:16 AM, Robert Dober wrote:
>
> On Sat, Apr 24, 2010 at 2:08 AM, steve ross <cwdinfo(a)gmail.com> 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.

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 :)
From: Caleb Clausen on 24 Apr 2010 13:41
On 4/23/10, steve ross <cwdinfo(a)gmail.com> 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

From: Robert Dober on 24 Apr 2010 14:12
On Sat, Apr 24, 2010 at 7:37 PM, steve ross <cwdinfo(a)gmail.com> wrote:
> On Apr 24, 2010, at 1:16 AM, Robert Dober wrote:
>>
>> On Sat, Apr 24, 2010 at 2:08 AM, steve ross <cwdinfo(a)gmail.com> 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.
>
> 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| <<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.

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

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD