Testing for overlapping arrays in Ruby

Say I have an array of arrays in Ruby,

[[100,300], [400,500]]

that I'm building by adding successive lines of CSV data.

What's the best way, when adding a new subarray, to test if the range covered by the two numbers in the subarray is covered by any previous subarrays?

In other words, each subarray comprises a linear range (100-300 and 400-500) in the example above. If I want an exception to be thrown if I tried to add [499,501], for example, to the array because there would be overlap, how could I best test for this?

-------------Problems Reply------------

Since your subarrays are supposed to represent ranges, it might be a good idea to actually use an array of ranges instead of an array of array.

So your array becomes [100..300, 400..500].

For two ranges, we can easily define a method which checks whether two ranges overlap:

def overlap?(r1, r2)
r1.include?(r2.begin) || r2.include?(r1.begin)
end

Now to check whether a range r overlaps with any range in your array of ranges, you just need to check whether overlap?(r, r2) is true for any r2 in the array of ranges:

def any_overlap?(r, ranges)
ranges.any? do |r2|
overlap?(r, r2)
end
end

Which can be used like this:

any_overlap?(499..501, [100..300, 400..500])
#=> true

any_overlap?(599..601, [100..300, 400..500])
#=> false

Here any_overlap? takes O(n) time. So if you use any_overlap? every time you add a range to the array, the whole thing will be O(n**2).

However there's a way to do what you want without checking each range:

You add all the ranges to the array without checking for overlap. Then you check whether any range in the array overlaps with any other. You can do this efficiently in O(n log n) time by sorting the array on the beginning of each range and then testing whether two adjacent ranges overlap:

def any_overlap?(ranges)
ranges.sort_by(&:begin).each_cons(2).any? do |r1,r2|
overlap?(r1, r2)
end
end

Category:ruby Views:0 Time:2010-12-21
Tags: ruby arrays

Related post

  • What is the "right" way to iterate through an array in Ruby? 2008-11-22

    PHP, for all its warts, is pretty good on this count. There's no difference between an array and a hash (maybe I'm naive, but this seems obviously right to me), and to iterate through either you just do foreach (array/hash as $key => $value) In Ru

  • Ruby array manipulation (Ruby 1.8 and Rails 2.2) 2009-01-29

    I'm hopelessly trying to write a method to manipulate an array in ruby. I'm trying to generate all in-order permutations of an array where each item is in turn replaced by an outside item. An example... Given input: arr = ["a", "b", "c"] Desired outp

  • How to randomly sort (scramble) an array in Ruby? 2009-11-29

    I'd like to have my array items scrambled. Something like this: [1,2,3,4].scramble => [2,1,3,4] [1,2,3,4].scramble => [3,1,2,4] [1,2,3,4].scramble => [4,2,3,1] and so on, randomly --------------Solutions------------- Built in now: [1,2,3,4].

  • Dynamically Create Arrays in Ruby 2009-12-01

    Is there a way to dynamically create arrays in Ruby? For example, let's say I wanted to loop through an array of books as input by a user: books = gets.chomp The user inputs: "The Great Gatsby, Crime and Punishment, Dracula, Fahrenheit 451, Pride and

  • Is there a simple way to duplicate a multi-dimensional array in Ruby? 2010-01-11

    I have a 2-dimensional array in Ruby that I want to produce a working duplicate of. Obviously I can't do this; array=[[3,4],[5,9],[10,2],[11,3]] temp_array=array as any modifications I make to temp_array will also be made to array, as I have merely c

  • How to convert image file to byte array using ruby 2010-03-08

    hi I need to pass image as byte array to .NET SOAP web service. Can anyone give me example how to convert uploaded image file to byte array using ruby? --------------Solutions------------- If I understand your question correctly you are getting image

  • Stop duplicates from being added to an array of Ruby objects 2010-05-10

    how can I eliminate duplicate elements from an array of ruby objects using an attribute of the object to match identical objects. with an array of basic types I can use a set.. eg. array_list = [1, 3, 4 5, 6, 6] array_list.to_set => [1, 2, 3, 4, 5

  • How to set fixed number of elements of array in Ruby 2010-12-21

    How to set fixed number of elements of an array in Ruby. eg. a=["a","b","c","d"] Setting array size to 3 would output a=["a","b","cd"] --------------Solutions------------- class Array def squeeze(n, &p) p = Proc.new {|xs| xs.join} unless p arr =

  • Looping and creating an array in Ruby 2011-01-15

    Trying to port some old PHP code to Ruby and missing some key info on creating arrays in Ruby. The PHP code: foreach ($results as $r) { $array[$r['column']][] = $r } Is this the simplest way to do it in Ruby? Do I have to initialize the second array?

  • Strange behavior splitting arrays with Ruby (v1.9.2) 2011-01-30

    I am trying to handle an array with Ruby v1.9.2 but it has some strange behavior. The best explanation may be done with examples: CASE 1 TEST @test1 = "image/bmp, image/gif, image/jpg".split(',') Debug @test1: --- - image/bmp # why this?! - " image/g

  • Creating permutations from a multi-dimensional array in Ruby 2011-04-07

    I have the following multi-dimensional array in Ruby: [[1,2], [3], [4,5,6]] I need to have the following output: [[1,3,4], [1,3,5], [1,3,6], [2,3,4], [2,3,5], [2,3,6]] I have tried creating a recursive function, but I'm not having much luck. Are ther

  • d2: overlapping array copy 2011-05-14

    In order to find out which element occurs most often in a given array, I've been using the group function from std.algorithm. First I would sort the array (that doesn't seem to be necessary anymore), then pass it to group, and sort the tuple array, s

  • How do I print a multi-dimensional array in ruby? 2011-09-19

    What's the preferred method of printing a multi-dimensional array in ruby? For example, suppose I have this 2D array: x = [ [1, 2, 3], [4, 5, 6]] I try to print it: >> print x 123456 Also what doesn't work: >> puts x 1 2 3 4 5 6 ---------

  • Removing trailing empty values from an array in ruby 2011-09-30

    How to remove the trailing empty and nil values from an array in Ruby. The "Compact" function is not fullfil my requirement. It is removing all the 'nil' values from an array. But I want to remove the trailing empty and nil values alone. Please give

  • What is true way to find needed values from array of arrays in Ruby? 2011-10-09

    I have an array of arrays in Ruby: price_list = [ ['Brand-1', 'Model-1', 100.00], ['Brand-1', 'Model-2', 200.00], ['Brand-2', 'Model-1', 10.00], ['Brand-2', 'Model-2', 20.00], ['Brand-1', 'Model-1', 110.00], ['Brand-1', 'Model-2', 190.00], ['Brand-1'

  • How can you "explode" an array in Ruby? 2011-12-14

    I'd like to "explode" an array in Ruby in order to do a fast variable assignment i.e. a, b = ['first_var', 'second_var'] Is this possible? I've looked through the array docs and can't find anything that seems to offer this but it seems Rubyish... ---

  • How to declare a two-dimensional array in Ruby 2012-02-04

    I want a twodimensional array in Ruby, that I can access for example like this: if @array[x][y] == "1" then @array[x][y] = "0" The problem is: I don't know the initial sizes of the array dimensions and i grow the array (with the << operator). H

  • getting dimension of multidimensional array in ruby 2012-03-03

    I just started learning ruby. Now I need to figure out the dimension of a multidimensional array. I had a look at ruby-docs for the all the array methods, but I could not find a method that returns the dimension. Here is an example: For [[1, 2],[3,4]

  • Unordered array in Ruby 2012-04-20

    is there a class that represents an unordered array in ruby? I cannot use array because [1,2] != [2,1] And I cannot use set because I can only have unique elements. I kind of want a combination of both. A list that doesnt care about ordering and can

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.177 (s). 11 q(s)