user1934428 user1934428 - 4 months ago 8
Ruby Question

Ruby: Search record based on predicate - please suggest nicer solutions

(I already wrote a solution to the problem below, but would like to ask whether someone could suggest a cleaner solution, more being in the "Spirit" of Ruby).

PROBLEM: I have an (ordered) set of needles, an (ordered) set of elements in a haystack, and a predicate which takes a needle and a haystack element and yields true or false. The task is to find the first needle where there is some haystack element where the predicate is true, and then returns the haystack element. We are not interested in the needle. The needles and the haystack is represented as an Array.

For example, if

needles = [17,3,7,121]
haystack = [40,30,70]


and the predicate is

def p(needle, hay)
hay % needle == 0
end


the result should be 30, because for needle 17, no element in haystack fulfils the predicate, but for needle 3, the second element (30) does.

Here is my implementation:

found = nil
needles.find do |n|
found = haystack.find { |he| p(n,he) }
break if found
end


What I find a bit unnatural is that I basically throw away the result of the outer
find
and need to carry around the variable
found
, which eventually holds the result. I was looking for a more concise expression, which directly assigns the result to
found
, i.e.:

found = ......


Any ideas?

Answer

The important thing to note is that it's the haystack element you want to find, not the needle. Therefore, this variable needs to be the one in your outermost loop.

It would then by more idiomatic to use Enumerable#any? to check for the presence of needles which satisfy the predicate, since you really only care about the true/false return value.

The end result is:

haystack.find do |he|
  needles.any? { |needle| p(needle, he) }
end

EDIT: I misunderstood the question slightly, sorry. If we are ordering the needles, and finding the first haystack which satisfies the predicate the "highest-ordered" needle, then we could do:

haystack
  .select { |he| needles.any? { |needle| p(needle, he) } }
  .min_by { |he| needles.index { |needle| p(needle, he) } }

Or as an alternate (more efficient) solution, how about:

haystack.min_by do |he|
  needles.index { |needle| p(needle, he) } || Float::INFINITY  
end

This funny use of Float::INFINITY is used in case no needles match the condition for the haystack element, in which case the index method returns nil.