Forum: Ruby Finding an interval in a sorted array?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
A87f7a014c624587fab0d3d78c5b9c18?d=identicon&s=25 Bil Kleb (Guest)
on 2006-05-05 19:25
(Received via mailing list)
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,
Ced5fff44ff8929fc974012ea108b284?d=identicon&s=25 Sergey Volkov (Guest)
on 2006-05-05 20:47
(Received via mailing list)
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?
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2006-05-05 20:53
(Received via mailing list)
On Sat, 6 May 2006, Bil Kleb wrote:

>   end
>     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
>

this ought to get you going


   class Array
     #
     # 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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-05-05 22:02
(Received via mailing list)
2006/5/5, Bil Kleb <Bil.Kleb@nasa.gov>:
>     end
>       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]

Kind regards

robert
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-05-05 22:20
(Received via mailing list)
2006/5/5, Robert Klemme <shortcutter@googlemail.com>:
> >       # elegant code goes here
> >       assert_equal [1,2], data.interval_containing( 1.6)
>   end
> 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]

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
A87f7a014c624587fab0d3d78c5b9c18?d=identicon&s=25 Bil Kleb (Guest)
on 2006-05-10 13:20
(Received via mailing list)
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,
This topic is locked and can not be replied to.