CODEWITHSUNDEEP
rubyarrays
Julio
Julio

Reputation: 6368

Check if array of integers increments in Ruby

I want to check if an arrays values once sorted are incrementing by 1

For example

[1, 2, 3, 4, 5] = TRUE
[1, 2, 8, 9, 10] = FALSE

Any suggestions are much appreciated

Upvotes: 10

Views: 6062

Answers (10)

Rahul Patel
Rahul Patel

Reputation: 1424

Try this

def increase_by_one?(array)
  temp = array.first
  array.each_with_index do |val, index|
   return false unless temp == val-index
  end
  true 
end

Upvotes: 0

evernoob
evernoob

Reputation: 1

a = [1,2,3,4,5]
a[a.size-1] == a[0] + a.size-1
TRUE

Upvotes: 0

mmdemirbas
mmdemirbas

Reputation: 9158

A short and efficient method

sort not required and comparison breaks at first counter-example.

def increase_by? (array, step)
    yes = true
    array.reduce { |l, r| break unless yes &= ( l+step == r ); l }
    yes
end

Upvotes: 0

the Tin Man
the Tin Man

Reputation: 160559

I go with this:

def is_consecutive_array?(ary)
  sorted_array  = ary.sort
  first_element = sorted_array.first
  last_element  = sorted_array.last
  ((last_element - first_element) == ary.size - 1) && (sorted_array[0].upto(sorted_array[-1]).to_a == sorted_array)
end

is_consecutive_array?([1,2])           # => true
is_consecutive_array?([1,2,3])         # => true
is_consecutive_array?([3,2,1])         # => true
is_consecutive_array?([-1,0,1])        # => true
is_consecutive_array?([1,3])           # => false
is_consecutive_array?([1, 2, 2, 2, 5]) # => false

This is a change from the previous version. I wasn't happy with it but couldn't put my finger on why. @sawa pointed out the flaw which is in the last test above. I added the && section to do an exhaustive check if the first test returns true. The overall effect shows up in this benchmark:

Benchmark.bm do |_bench|

  ary2 = ary[0 .. -3] + ary[-1,1]
  _bench.report { loops.times {
    is_consecutive_array?(ary2)
  }}

  _bench.report { loops.times {
    is_consecutive_array?(ary)
  }}

end
# >>       user     system      total        real
# >>   2.140000   0.200000   2.340000 (  2.328039)
# >>  18.430000   0.020000  18.450000 ( 18.442234)

Most arrays will not be consecutive, and will not have the right combination to fool the first test. For those that do, the second test should catch it.

EDIT: Here are some benchmarks to compare the various suggested methods. The answers up to this point in time have been preserved as closely as possible. I had to change the increase_by? answer because it was patching Array and wasn't sorting. I didn't want it to accidentally have a detrimental effect on the other tests or an unfair advantage.

NOTE: I raised the TIMEOUT_LIMIT because I also made the test array bigger.

require 'benchmark'
require 'timeout'

TIMEOUT_LIMIT = 60 # in seconds

ary = [*(1..10_000)]
loops = 10_000

def is_consecutive_array?(ary)
  sorted_array  = ary.sort
  first_element = sorted_array.first
  last_element  = sorted_array.last
  ((last_element - first_element) == ary.size - 1) && (sorted_array[0].upto(sorted_array[-1]).to_a == sorted_array)
end
is_consecutive_array?([1,2])           # => true
is_consecutive_array?([1,2,3])         # => true
is_consecutive_array?([3,2,1])         # => true
is_consecutive_array?([-1,0,1])        # => true
is_consecutive_array?([1,3])           # => false
is_consecutive_array?([1, 2, 2, 2, 5]) # => false

def sawa(a)
  b = a.dup
  x = b.delete(b.min)
  nil while b.delete(x+=1)
  b.empty?
end
sawa([1,2])   # => true
sawa([1,3])   # => false
sawa([1,3,3]) # => false

def array_increments_by?(step, array)
  sorted = array.sort
  lastNum = sorted[0]
  sorted[1, sorted.count].each do |n|
    if lastNum + step != n
      return false
    end
    lastNum = n
  end
  true
end
array_increments_by?(1,[1,2])   # => true
array_increments_by?(1,[1,3])   # => false
array_increments_by?(1,[1,3,3]) # => false

def continguous?(arr)
  a = arr.sort
  (a.first..a.last).to_a == a
end
continguous?([1,2])   # => true
continguous?([1,3])   # => false
continguous?([1,3,3]) # => false

def fgb(array)
  array.sort.each_cons(2).all? { |x,y| y == x + 1 }
end
fgb([1,2])   # => true
fgb([1,3])   # => false
fgb([1,3,3]) # => false

# changed from a monkey-patch on Array to avoid any unintended side-effects.
def increase_by?(ary, n)
  ary.sort # added sort to put on same ground as all other tests
  y = nil
  ary.each {|x| return false if y && ((x-y) != n); y=x}
  true
end
increase_by?([1,2],1)   # => true
increase_by?([1,3],1)   # => false
increase_by?([1,3,3],1) # => false

Benchmark.bm(20) do |_bench|

  begin
    testname = 'is_consecutive_array?'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { is_consecutive_array?(ary) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end

  begin
    testname = 'sawa'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { sawa(ary) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end

  begin
    testname = 'array_increments_by?'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { array_increments_by?(1, ary) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end

  begin
    testname = 'continguous?'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { continguous?(ary) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end

  begin
    testname = 'fgb'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { fgb(ary) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end

  begin
    testname = 'increase_by?'
    status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { increase_by?(ary, 1) } } }
  rescue Timeout::Error => e
    puts "#{testname} timed out"
  end
end

And the results against a consecutive array:

# >>                           user     system      total        real
# >> is_consecutive_array? 18.470000   0.020000  18.490000 ( 18.476536)
# >> sawa                sawa timed out
# >> array_increments_by? 37.070000   0.670000  37.740000 ( 37.734562)
# >> continguous?         18.720000   0.890000  19.610000 ( 19.590057)
# >> fgb                 fgb timed out
# >> increase_by?         41.510000   0.610000  42.120000 ( 42.090960)

Upvotes: 3

sawa
sawa

Reputation: 168101

This one doesn't require sort.

a = [2, 8, 1, 9, 10]
b = a.dup
x = b.delete(b.min)
nil while b.delete(x+=1)
b.empty?

Upvotes: 1

Jacob Relkin
Jacob Relkin

Reputation: 163258

Try this:

def array_increments_by?(step, array)
  sorted = array.sort
  lastNum = sorted[0]
  sorted[1, sorted.count].each do |n|
    if lastNum + step != n
      return false
    end
    lastNum = n
  end
  true
end

Usage:

array_increments?(1, [0,1,2,3]) #=> true
array_increments?(2, [0,2,4,6]) #=> true
array_increments?(2, [0,2,4,8]) #=> false

Upvotes: 5

steenslag
steenslag

Reputation: 80065

def continguous?(arr)
  a = arr.sort
  (a.first..a.last).to_a == a
end

a = [2,1,3,4,5]
p continguous?(a)
#=> true

Upvotes: 5

fgb
fgb

Reputation: 18569

array = [1,2,4,3]
array.sort.each_cons(2).all? { |x,y| y == x + 1 }

Upvotes: 39

Mahesh
Mahesh

Reputation: 34625

If the difference between a[i+1] and a[i] is not equal to 1, then it is obvious that they are not either in increasing order incremented by 1 or not at all in increasing order ( considering no two elements in the array are equal). Run the loop from zero to length of array minus 1.

Upvotes: 0

maerics
maerics

Reputation: 156434

class Array
  def increase_by?(n)
    y = nil
    self.each {|x| return false if y && ((x-y) != n); y=x}
    true
  end
end

[1, 2, 3, 4, 5].increase_by?(1) # => true
[1, 2, 8, 9, 10].increase_by?(1) # => false

Upvotes: 0

Related Questions