Forum: Ruby Finding gaps in a sorted sequence

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.
C6c36c5c5443ca863468bfea1790ff84?d=identicon&s=25 Pete Hodgson (Guest)
on 2008-11-06 18:41
(Received via mailing list)
Hi Folks,

Given a sorted enumeration I need to find the first gap in a sequence.

e.g.
3 == find_gap [1,2,4,5]
nil == find_gap [1,2,3,4]

Here's the best I can come up with

def first_gap( seq )
  seq.each_cons(2) do |l,r|
    _next = l.next
    return _next if r!= _next
  end
  nil
end

but it seems rather ugly. Anyone have a more elegant implementation?

Cheers,
Pete
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2008-11-06 19:07
(Received via mailing list)
On Thu, Nov 6, 2008 at 12:39 PM, Pete Hodgson <phodgson@lyris.com>
wrote:
> Given a sorted enumeration I need to find the first gap in a sequence.
>
> e.g.
> 3 == find_gap [1,2,4,5]
> nil == find_gap [1,2,3,4]

$ cat bar.rb
def find_gap array
  f = array.first
  l = array.last
  s = l - f + 1

  return nil if s == array.size

  if array.size == 2
    return f + 1
  end

  c = array.size / 2
  if array[c] != f + c
    a = find_gap(array[0..c])
  else
    b = find_gap(array[c..-1])
  end

  a ? a : b
end

p find_gap([1,2,4,5])
p find_gap([1,2,3,4])
p find_gap([1,2,3,4,5,6,7,11,12])
p find_gap([2,3,4,5,6,7,11,12])

$ ruby bar.rb
3
nil
8
8
D7908f05c89e965f6bc5308ad6f41256?d=identicon&s=25 Siep Korteling (steenslag)
on 2008-11-06 21:52
Pete Hodgson wrote:
> Hi Folks,
>
> Given a sorted enumeration I need to find the first gap in a sequence.
>
> e.g.
> 3 == find_gap [1,2,4,5]
> nil == find_gap [1,2,3,4]
>
> Here's the best I can come up with
>
> def first_gap( seq )
>   seq.each_cons(2) do |l,r|
>     _next = l.next
>     return _next if r!= _next
>   end
>   nil
> end
>
> but it seems rather ugly. Anyone have a more elegant implementation?
>
> Cheers,
> Pete

The following does not quite meet your specs (it returns an array with
all gaps, empty if there are no gaps). Anyway, here is my try:

def find_gaps( ar )
  (ar.first .. ar.last).to_a - ar
end

p find_gaps( [1,2,4,5] )
p find_gaps( ["a", "b", "d", "e", "h"] )

require 'date'
d1 = Date.new(2008,11,6)
d2 = Date.new(2008,11,7)
d3 = Date.new(2008,11,9)
puts find_gaps( [d1,d2,d3] )

=> [3]
=> ["c", "f", "g"]
=> 2008-11-08

hth,

Siep
5f4f7a23e3d0134123a66015bdc4edd1?d=identicon&s=25 Zeekar (Guest)
on 2008-11-06 23:25
(Received via mailing list)
PH = Pete Hodgson
SK = Siep Korteling

PH> Given a sorted enumeration I need to find the first gap in a
sequence.
PH> e.g.
PH> 3 == find_gap [1,2,4,5]
PH> nil == find_gap [1,2,3,4]

SK> The following does not quite meet your specs (it returns an array
with
SK> all gaps, empty if there are no gaps). Anyway, here is my try:
>
> def find_gaps( ar )
>   (ar.first .. ar.last).to_a - ar
> end

Given the above definition, it's easy to get Pete's behavior exactly:

def find_gap( ar )
    find_gaps(ar).first
end

And then you have a choice of methods to use, depending on whether you
need the full list or just the first gap.
8666d1ebabcea440585dfe831a4af9f1?d=identicon&s=25 Brian Adkins (Guest)
on 2008-11-07 05:22
(Received via mailing list)
Pete Hodgson <phodgson@lyris.com> writes:

> def first_gap( seq )
>   seq.each_cons(2) do |l,r|
>     _next = l.next
>     return _next if r!= _next
>   end
>   nil
> end
>
> but it seems rather ugly. Anyone have a more elegant implementation?

I think your version is pretty readable. However, it appears you do
pay a 60% speed penalty with the Enumerator version. So I guess it
depends on whether conciseness and readability are more important than
efficiency, or not.

--- snip ---
require 'enumerator'
require 'benchmark'
include Benchmark

def first_gap list
  list.each_cons(2) do |l,r|
    _next = l.next
    return _next unless r == _next
  end
  nil
end

def other_gap list
  prev = nil
  list.each do |e|
    if prev && (n = prev.next) != e
      return n
    end
    prev = e
  end
  nil
end

t = (1..100).to_a

[100, 250, 500].each do |n|
  t = (1..n).to_a
  bm(5) do |x|
    x.report('first') { 1_000.times { first_gap(t) } }
    x.report('other') { 1_000.times { other_gap(t) } }
  end
end
--- snip ---

~/temp$ ruby first_gap.rb
           user     system      total        real
first  0.700000   0.250000   0.950000 (  0.957255)
other  0.430000   0.170000   0.600000 (  0.604145)
           user     system      total        real
first  1.720000   0.630000   2.350000 (  2.354915)
other  1.070000   0.420000   1.490000 (  1.490321)
           user     system      total        real
first  3.470000   1.250000   4.720000 (  4.838116)
other  2.120000   0.840000   2.960000 (  3.018840)
Ae16cb4f6d78e485b04ce1e821592ae5?d=identicon&s=25 Martin DeMello (Guest)
on 2008-11-07 08:21
(Received via mailing list)
On Thu, Nov 6, 2008 at 9:39 AM, Pete Hodgson <phodgson@lyris.com> wrote:
> Hi Folks,
>
> Given a sorted enumeration I need to find the first gap in a sequence.
>
> e.g.
> 3 == find_gap [1,2,4,5]
> nil == find_gap [1,2,3,4]

irb(main):001:0> g = [1,2,3,5,6,8,9,10]
=> [1, 2, 3, 5, 6, 8, 9, 10]

irb(main):002:0> gap = g.inject {|a, e| e == a.next ? e : (break
a.next)}
=> 4

martin
B4fefc9b9efe67fb32718f0ca1f8cba1?d=identicon&s=25 Suninny (Guest)
on 2008-11-07 09:20
(Received via mailing list)
unsubscribe
8666d1ebabcea440585dfe831a4af9f1?d=identicon&s=25 Brian Adkins (Guest)
on 2008-11-07 09:32
(Received via mailing list)
Martin DeMello <martindemello@gmail.com> writes:

> => [1, 2, 3, 5, 6, 8, 9, 10]
>
> irb(main):002:0> gap = g.inject {|a, e| e == a.next ? e : (break a.next)}
> => 4

Beautiful. Excellent use of inject :) I would've thought this would be
better performing also, but it lags the 'each' version by quite a bit:

           user     system      total        real
OP     3.490000   1.240000   4.730000 (  4.755358)
Brian  2.170000   0.830000   3.000000 (  3.000508)
Martin  3.320000   1.240000   4.560000 (  4.582286)

I still think I like it best though because it seems to be the most
natural Ruby solution to the original problem.
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2008-11-07 19:17
(Received via mailing list)
On Fri, Nov 7, 2008 at 9:28 AM, Brian Adkins <lojicdotcom@gmail.com>
wrote:
> Martin DeMello <martindemello@gmail.com> writes:
<snip>
> I still think I like it best though because it seems to be the most
> natural Ruby solution to the original problem.
Well not quite, it does not return nil if there is no gap, one has to
check if the return value is the last element of the array
and replace it with nil in that case.
One should know that inject is quite slow, but no reason not to use it
unless performance is a problem.

Cheers
Robert
--
C'est véritablement utile puisque c'est joli.

Antoine de Saint Exupéry
8666d1ebabcea440585dfe831a4af9f1?d=identicon&s=25 Brian Adkins (Guest)
on 2008-11-07 22:45
(Received via mailing list)
Robert Dober <robert.dober@gmail.com> writes:

> On Fri, Nov 7, 2008 at 9:28 AM, Brian Adkins <lojicdotcom@gmail.com> wrote:
>> Martin DeMello <martindemello@gmail.com> writes:
> <snip>
>> I still think I like it best though because it seems to be the most
>> natural Ruby solution to the original problem.
> Well not quite, it does not return nil if there is no gap,

D'oh! I missed that. Ok, I guess I like my version best again then :)
This topic is locked and can not be replied to.