How to create a nested loop with Ruby the "Right Way!"?

Question

I'm in the process of learning Ruby, taking a Berkeley's MOOC, and, in some of these MOOC's homework we have an exercise that says:

Define a method sum_to_n? which takes an array of integers and an additional integer, n, as arguments and returns true if any two elements in the array of integers sum to n. An empty array should sum to zero by definition.

I already created two methods that can do the job, but I'm not comfortable with any of them because I think they are not written in the Ruby Way. I hope some of you can help me to learn which would be the right way!

The first method I made uses the each method for both iterations, but what I don't like about this method is that every number is summed with every other number, even with the same number, doing something like this:

arr[1, 2, 3, 4] => 1+1, 1+2, 1+3, 1+4, 2+1, 2+2, 2+3, 2+4, 3+1, 3+2... 4+3, 4+4

As you can see, there's a lot of repeated sums, and I don't want that.

This is the code:

def sum_to_n?(arr, n)
  arr.each {|x| arr.each {|y| return true if x + y == n && x != y}}
  return true if n == 0 && arr.length == 0
  return false
end

With the other method I got what I wanted, just a few sums without repeating any of them or even summing the same numbers, but it looks HORRIBLE, and I'm pretty sure someone would love to kill me for doing it this way, but the method does a great job as you can see:

arr[1, 2, 3, 4] => 1+2, 1+3, 1+4, 2+3, 2+4, 3+4

This is the code:

def sum_to_n?(arr, n)
  for i in 0..arr.length - 1
    k = i + 1
    for k in k..arr.length - 1
      sum = arr[i] + arr[k]
      if sum == n
        return true
      end
    end
  end
  return true if n == 0 && arr.length == 0
  return false
end

Well, I hope you guys have fun doing a better and prettier method as I did trying.

Thank you for your help.

Answer 1

I like rohitpaulk's answer but it fails when n doubles x. We should remove x from the array before sending include? n - x.

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?
  arr.any? { |x| arr.tap { arr.delete_at arr.index x }.include? n - x }
end

Lam Phan's answer using a hash is the best

Answer 2

i wonder why no answers here using hash ?

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?

  h = {}
  arr.any? { |x| complement = h[n-x]; h[x] = true; complement }
end

puts sum_to_n?([1,2,3,4,5,7], 6) # true
puts sum_to_n?([6,2,3,5,7,9], 6) # false
puts sum_to_n?([3,4,5,3], 6) # true
puts sum_to_n?([3,4,5,7], 6) # false
puts sum_to_n?([], 6) # false
puts sum_to_n?([], 0) # true

Answer 3

I had a thought that the beginning of any answer to this question should probably start with pruning the array for superfluous data:

Can't use this:

  arr.select! { |e| e <= n } # may be negative values      

But this might help:

  arr.sort!
  while arr[0] + arr[-1] > n # while smallest and largest value > n
    arr.delete_at(-1) # delete largest vaue
  end

Answer 4

I came across this on CodeWars. The accepted answer sure does look very Rubyish, but that is at the cost of performance. Calling arr.combination(2) results in a lot of combinations, it'd be simpler to go over the array element by element and search whether the 'complement' sum - element exists. Here's how that'd look like -

def sum_to_n?(arr, n)
  (arr.empty? and n.zero?) or arr.any? { |x| arr.include?(n - x) }
end

Answer 5

This one will do it in O(n.log(n)) rather than O(n²):

a = 1, 2, 3, 4

class Array
  def sum_to? n
    unless empty?
      false.tap {
        i, j, sorted = 0, size - 1, sort
        loop do
          break if i == j
          a, b = sorted[i], sorted[j]
          sum = a + b
          return a, b if sum == n
          sum < n ? i += 1 : j -= 1
        end
      }
    end
  end
end

a.sum_to? 7 #=> [3, 4]

Answer 6

Beside @jorg-w-mittag's answer. I found another solution using 'permutation'.

https://stackoverflow.com/a/19351660/66493

def sum_to_n?(arr, n)
  (arr.empty? && n.zero?) || arr.permutation(2).any? { |a, b| a + b == n }
end

I didn't know about permutation before. Still like @jorg-w-mittag answer because its more readable.

Answer 7

I'd write it like this:

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?
  arr.combination(2).any? {|a, b| a + b == n }
end

That seems to be a pretty Rubyish solution.