Finding an interval in a sorted array?

ruby-talk
1

Hello,

Surely there is a way to find an interval in a sorted array
without resorting to indices? (I'm drawing a blank.)

  require 'test/unit'

  class Array
    def interval_containing( x )
      # elegant code goes here
    end
  end

  class TestIntervalFinder < Test::Unit::TestCase
    def test_finds_intervals
      data = [ 0, 1, 2 ].sort
      assert_equal [0], data.interval_containing(-0.2)
      assert_equal [0], data.interval_containing( 0.0)
      assert_equal [0,1], data.interval_containing( 0.5)
      assert_equal [1], data.interval_containing( 1.0)
      assert_equal [1,2], data.interval_containing( 1.6)
      assert_equal [2], data.interval_containing( 2.0)
      assert_equal [2], data.interval_containing( 5.0)
    end
  end

Thanks,

···

--
Bil
http://fun3d.larc.nasa.gov

2

class Array
    def interval_containing( x )
        # elegant code goes here
        [select{|e|e<=x}[-1], select{|e|e>=x}[0]].compact.uniq
    end
end

% ruby tIntervalContaining.rb
Loaded suite tIntervalContaining
Started
.
Finished in 0.0 seconds.

1 tests, 7 assertions, 0 failures, 0 errors

···

---------

best
Sergey

----- Original Message ----- From: "Bil Kleb" <Bil.Kleb@nasa.gov>
To: "ruby-talk ML" <ruby-talk@ruby-lang.org>
Sent: Friday, May 05, 2006 1:25 PM
Subject: Finding an interval in a sorted array?

Hello,

Surely there is a way to find an interval in a sorted array
without resorting to indices? (I'm drawing a blank.)

require 'test/unit'

class Array
   def interval_containing( x )
     # elegant code goes here
   end
end

class TestIntervalFinder < Test::Unit::TestCase
   def test_finds_intervals
     data = [ 0, 1, 2 ].sort
     assert_equal [0], data.interval_containing(-0.2)
     assert_equal [0], data.interval_containing( 0.0)
     assert_equal [0,1], data.interval_containing( 0.5)
     assert_equal [1], data.interval_containing( 1.0)
     assert_equal [1,2], data.interval_containing( 1.6)
     assert_equal [2], data.interval_containing( 2.0)
     assert_equal [2], data.interval_containing( 5.0)
   end
end

Thanks,
--
Bil
http://fun3d.larc.nasa.gov

3

this ought to get you going

   class Array

···

On Sat, 6 May 2006, Bil Kleb wrote:

Hello,

Surely there is a way to find an interval in a sorted array
without resorting to indices? (I'm drawing a blank.)

require 'test/unit'

class Array
  def interval_containing( x )
    # elegant code goes here
  end
end

class TestIntervalFinder < Test::Unit::TestCase
  def test_finds_intervals
    data = [ 0, 1, 2 ].sort
    assert_equal [0], data.interval_containing(-0.2)
    assert_equal [0], data.interval_containing( 0.0)
    assert_equal [0,1], data.interval_containing( 0.5)
    assert_equal [1], data.interval_containing( 1.0)
    assert_equal [1,2], data.interval_containing( 1.6)
    assert_equal [2], data.interval_containing( 2.0)
    assert_equal [2], data.interval_containing( 5.0)
  end
end

Thanks,
--
Bil
http://fun3d.larc.nasa.gov

     #
     # extract any sequences in a sorted list
     #
     # [0, 1, 2, 4, 5].sequences #=> [0..2, 4..5]
     # [-5, -4, -4, -3, 0, 1].sequences #=> [-5..-4, -4..-3, 0..1]
     #
     def sequences list = self.sort
       distance = lambda do |a,b|
         (b - a).abs
       end
       continuous = lambda do |range, list|
         first, last = range.first, range.last
         a, b = list[first], list[last]
         ((list.empty? or (distance[a,b] == distance[first,last])) ? (a .. b) : nil)
       end
       discrete = lambda do |range, list|
         first, last = range.first, range.last
         edge = last + 1
         (edge >= list.length or distance[list[last], list[edge]] != 1)
       end
       sequence = lambda do |range, list|
         first, last = range.first, range.last
         (list[first] .. list[last])
       end

       last = list.length - 1
       a, b = 0, last

       accum =
       while a <= b and a < list.length and b < list.length
         range = a .. b

         if continuous[ range, list ]
           if discrete[ range, list ]
             accum << sequence[ range, list ]
             a, b = b + 1, last # move a and b up
           else
             b = b + (distance[b, last] / 2) # move b up
           end
         else
           b = a + (distance[a, b] / 2) # move b down
         end
       end
       accum
     end
   end

i think you need to re-write your test since an array could have the same
interval twice - eg test must be on a list of intervals

regards.

-a
--
be kind whenever possible... it is always possible.
- h.h. the 14th dali lama

4

Solutions - of course with inject:

module Enumerable
  def f1(x)
    [inject(nil) {|a,b| return [a,b] if (a||x)<=x && b>x; b}, nil]
  end

  def f2(x)
    inject {|a,b| return [a,b] if a<=x && b>x; b}
    nil
  end
end

irb(main):015:0> a=[0,1,2]
=> [0, 1, 2]
irb(main):016:0> a.f1 0.2
=> [0, 1]
irb(main):017:0> a.f2 0.2
=> [0, 1]
irb(main):018:0> a.f1 0
=> [0, 1]
irb(main):019:0> a.f1 -1
=> [nil, 0]
irb(main):020:0> a.f1 10
=> [2, nil]

Kind regards

robert

···

2006/5/5, Bil Kleb <Bil.Kleb@nasa.gov>:

Hello,

Surely there is a way to find an interval in a sorted array
without resorting to indices? (I'm drawing a blank.)

  require 'test/unit'

  class Array
    def interval_containing( x )
      # elegant code goes here
    end
  end

  class TestIntervalFinder < Test::Unit::TestCase
    def test_finds_intervals
      data = [ 0, 1, 2 ].sort
      assert_equal [0], data.interval_containing(-0.2)
      assert_equal [0], data.interval_containing( 0.0)
      assert_equal [0,1], data.interval_containing( 0.5)
      assert_equal [1], data.interval_containing( 1.0)
      assert_equal [1,2], data.interval_containing( 1.6)
      assert_equal [2], data.interval_containing( 2.0)
      assert_equal [2], data.interval_containing( 5.0)
    end
  end

--
Have a look: Robert K. | Flickr

5

PS: Sergey is right of course, you don't need a sorted sequence. Here
is a bit more verbose and slightly more efficient approach:

module Enumerable
  def f3(x)
    lo = hi = nil
    each do |n|
      lo = n if n <= x && ( lo.nil? || n > lo )
      hi = n if n > x && ( hi.nil? || n < hi )
    end
    [lo, hi]
  end
end

irb(main):022:0> [2,1,0].f3 0.5
=> [0, 1]
irb(main):023:0> [2,1,0].f3 5
=> [2, nil]
irb(main):024:0> [2,1,0].f3 -1
=> [nil, 0]

Cheers

robert

···

2006/5/5, Robert Klemme <shortcutter@googlemail.com>:

2006/5/5, Bil Kleb <Bil.Kleb@nasa.gov>:
> Hello,
>
> Surely there is a way to find an interval in a sorted array
> without resorting to indices? (I'm drawing a blank.)
>
> require 'test/unit'
>
> class Array
> def interval_containing( x )
> # elegant code goes here
> end
> end
>
> class TestIntervalFinder < Test::Unit::TestCase
> def test_finds_intervals
> data = [ 0, 1, 2 ].sort
> assert_equal [0], data.interval_containing(-0.2)
> assert_equal [0], data.interval_containing( 0.0)
> assert_equal [0,1], data.interval_containing( 0.5)
> assert_equal [1], data.interval_containing( 1.0)
> assert_equal [1,2], data.interval_containing( 1.6)
> assert_equal [2], data.interval_containing( 2.0)
> assert_equal [2], data.interval_containing( 5.0)
> end
> end

Solutions - of course with inject:

module Enumerable
  def f1(x)
    [inject(nil) {|a,b| return [a,b] if (a||x)<=x && b>x; b}, nil]
  end

  def f2(x)
    inject {|a,b| return [a,b] if a<=x && b>x; b}
    nil
  end
end

irb(main):015:0> a=[0,1,2]
=> [0, 1, 2]
irb(main):016:0> a.f1 0.2
=> [0, 1]
irb(main):017:0> a.f2 0.2
=> [0, 1]
irb(main):018:0> a.f1 0
=> [0, 1]
irb(main):019:0> a.f1 -1
=> [nil, 0]
irb(main):020:0> a.f1 10
=> [2, nil]

--
Have a look: Robert K. | Flickr

6

Sergey Volkov wrote:

class Array
   def interval_containing( x )
       # elegant code goes here
       [select{|e|e<=x}[-1], select{|e|e>=x}[0]].compact.uniq
   end
end

My officemate prompted this question. Here's his
"final answer":

  def interval_containing x
   lower, upper = partition{|i| i <= x}
   [lower.last, upper.first]
  end

  This leaves a nil in one of the slots if the interval is off one
  of the ends, which might be what I want. To pass the tests,
  the return value should be [lower.last, upper.first].uniq

Thanks for all the ideas,

···

--
Bil
http://fun3d.larc.nasa.gov