How to do this properly in Ruby?

[tulamide]

Given an unsorted array of integers (fixnums) with possible duplicates, you want to find the one element from the array, that is closest to a number you compare with, so that the result is equal or higher than the number you compared with.

- The original array needs to stay intact
- If there is no equal or higher number in the original, algorithm should wrap around the array

Simple Example:

array = 0,1,2,3,5,7,9,11
first number to try = 8 => should result in 9
next number to try = 11 => should result in 11
final number to try = 12 => should result in 0


Here's what I came up with (real example, btw., so the numbers in the array are exactly as I would use them)

Code: Select all

num = 11
a = [2, 4, 6, 7, 9, 11, 1, 2]
b = a.dup.insert(0,num) #make a shallow copy of a and insert our number
b.sort! #sort the new array
b[(b.index(num) + 1) % b.length] # spit out the number that is next to the one we're looking for, modulo'd by array length

#this results in 11

Code: Select all

num = 11
a = [1, 3, 5, 6, 8, 10, 0, 1]
b = a.dup.insert(0,num)
b.sort!
b[(b.index(num) + 1) % b.length]

#this results in 0

Is there a better way? Better in terms of "more lightweight", less cpu stress. Not in terms of compacted code that does the same, or code that saves on RAM.

I hope that I thought too complicated, and that there is a better way!

[Tronic]

Hi Tulamide,
I think you can use the bsearch method for this case.

Code: Select all

num = 5
a = [2, 4, 6, 7, 9, 11, 1, 2]
a.sort.bsearch{|x| x >= num} || 0 # => 6 

--edit to make the result is 0(zero) if nothing.

[TheOm]

I would probably use min_by with the difference to the target number. It's O(n) and no temporary array.

Code: Select all

num = 20
a = [2, 4, 6, 7, 9, 18, 1, 7]

closest = a.min_by { |e| e >= num ? e - num : Float::INFINITY }

[tulamide]

Thank you, guys!

@tronic
I already chatted with you on slack, but for the others reading here: bsearch is a Ruby 2+ feature, but my code needs to be Flowstone 3.x compatible.

@TheOm
Awesome! Exactly what I'm after, and faster!
May I ask what the trick is to get it working correctly, when number is higher than any number in the array? I see that it does FLOAT::INFINITY, but I don't understand why this leads to the first value in the array, and in general the thinking behind this trick.

[Tronic]

I post this here as alternative method, more or less performat of other?

Code: Select all

num = 5
a = [2, 3, 4]
a.sort.find{|x| x >= num} || a.first # =>2

[TheOm]

I post this here as alternative method, more or less performat of other?

Code: Select all

num = 5
a = [2, 3, 4]
a.sort.find{|x| x >= num} || a.first # =>2

That will only work if the array is sorted. It will return the first element that's greater than num, not necessarily the closest.

May I ask what the trick is to get it working correctly, when number is higher than any number in the array? I see that it does FLOAT::INFINITY, but I don't understand why this leads to the first value in the array, and in general the thinking behind this trick.

If you think about how min_by could be implemented it would look something like this.

Code: Select all

def my_min_by(ar, &block)
  enum = ar.each
  
  begin
    e = enum.next
  rescue StopIteration
    return nil
  end
  
  min_elem = e
  min_value = block.call(e)
  
  loop do
    e = enum.next
    block_result = block.call(e)
    if block_result < min_value
      min_value = block_result
      min_elem = e
    end
  end

  return min_elem
end

Since the min_elem is only updated when the block_result is lower than (and not equal) to the last minimum value, if you have multiple values with the same block_result it will return the first one.

Now, I don't think that it's actually guaranteed to return the first of several equivalent elements. So if you want to be on the safe side you could add a check like this:

Code: Select all

closest = a.min_by { |e| e >= num ? e - num : Float::INFINITY }
if closest < num
  closest = a[0]
end

[tulamide]

May I ask what the trick is to get it working correctly, when number is higher than any number in the array? I see that it does FLOAT::INFINITY, but I don't understand why this leads to the first value in the array, and in general the thinking behind this trick.

If you think about how min_by could be implemented it would look something like this.

Code: Select all

def my_min_by(ar, &block)
  enum = ar.each
  
  begin
    e = enum.next
  rescue StopIteration
    return nil
  end
  
  min_elem = e
  min_value = block.call(e)
  
  loop do
    e = enum.next
    block_result = block.call(e)
    if block_result < min_value
      min_value = block_result
      min_elem = e
    end
  end

  return min_elem
end

Since the min_elem is only updated when the block_result is lower than (and not equal) to the last minimum value, if you have multiple values with the same block_result it will return the first one.

Now, I don't think that it's actually guaranteed to return the first of several equivalent elements. So if you want to be on the safe side you could add a check like this:

Code: Select all

closest = a.min_by { |e| e >= num ? e - num : Float::INFINITY }
if closest < num
  closest = a[0]
end

Yes! Of course! I was thinking in reverse order, regarding the provided value in the block (e - num, geez, how could I not see it?). Now infinity makes sense! I will also test, if it ever returns the "wrong" value. If not I'd prefer to spare the if-clause.
Thanks alot for the explanation!

[tulamide]

I'm so sorry!
I made a mistake while explaining the scenario and the required outcome. This time I hopefully do it detailed enough to rule out any edge cases! If you still have patience, I wouldn't mind perfecting my own attempt.

There's an array of 8 integer numbers.
The numbers are always positive, in the range of 0 to 11.
There will be duplicates in the array at various positions and various counts.
it should find the first of duplicates, position-wise from left to right. Below is a code example where the number 2 is the first and last element of the array. If we are looking for 3 and follow the conditions I lay out here, the result could become the first "2", when the last "2" is found first, although it should result in "4".

The array will be compared to a number n that's also in the range 0 to 11.
For now I concentrate on finding the closest number >= n, but in the end I try to implement user selectable search for either the closest higher or the closest lower number (never mixed, there will always be exactly one number output).

For closest >= n, the following applies (for <= n it would be the opposite):
If the number we're looking for isn't matched exactly and a higher number doesn't exist in the array, the algorithm has to return the value next to the max value in the array, position-based, not value-based. For example: a = 10, 2 and n = 11, should result in 2
Furthermore, if that max value of the array happens to be the last element of the array, position-wise, then the first element of the array should be the result. For example: a = 3, 5, 10 and n = 11, should result in 3

I had difficulties doing that with :min_by, so I worked with :find, and of course it is yet again a rather complicated code. But it fulfills all conditions. I will work with this code for now, to get other things done, but please take the opportunity to improve it. I will exchange it for the better code at any time!

Code: Select all

@test = [2, 4, 6, 7, 9, 11, 1, 2] # a real occurence of such an array
num = 5 #use any value from 0 to 11 to test

nextaftermax = @test.find_index(@test.max) + 1 #Getting the position-wise next value after max, even if out of range

result = @test.find { |e| e - num >= 0 } #first occurrence is fine, this can result to nil as well
result.nil? ? @test[nextaftermax] || @test.first : result
#the last line will later serve as the return value from a method

I count on your knowledge and helpfulness. But if you think, that this solution is already quite fast, please say so! We don't need to explode our heads then, trying to improve it.