Prev: [ANN] Ember 0.1.1
Next: Module "re-opening"
From: Robert Klemme on 23 Apr 2010 04:32
2010/4/23 Derek Cannon <novellterminator(a)gmail.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?

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

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

From: Derek Cannon on 23 Apr 2010 12:53
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/.

 | 
Pages: 1
Prev: [ANN] Ember 0.1.1
Next: Module "re-opening"