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.

Solution 1

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.

Solution 2

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

Solution 3

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.

Solution 4

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]

View more solutions

Comments

[PJP]

While Ruby has for, we tend to ignore it because there are some side-effects, such as it leaving its intermediate variable hanging around to clutter the variable space, and it forcing us to iterate over the container using calculated indexes, rather than allowing each to pass in each item individually. Indexes missing the first or last element, or falling off the end, are common bugs in all languages, and each helps avoid that. So, while it might seem like a stylistic choice, it's really a defensive programming choice. And, welcome to Stack Overflow!

[Amadan]

It's not O(n) if it uses Array#sort.

[Boris Stitnicky]

You'r right, including Array#sort, it's (probably) O(n.log(n)), edited the answer.

[dancow]

Damn. I'm a Rubyist and even I'm surprised at how Rubyish that solution was. Well done.

[David Gomez]

This is exactly what I meant.

[fotanus]

You is a smart guy, I have no doubts about that. Can you Enlighten us with a generic answer for this question? Your works because a method that does what the OP wants exists, but what if you have a generic nested loops? Or you should not have any, and if you have you are doing it wrong?

[Mark Thomas]

permutation considers order important. This will result in redundant sums, e.g. a + b and b + a. Therefore combination is the better choice in this case.

[Mark Thomas]

Why do you need the first parenthetical expression? Empty arrays won't cause any? or include? to throw errors. It's a good answer, I just think it could be a little more concise.

[rohitpaulk]

@mark-thomas - "An empty array should sum to zero by definition" is what the question says - If it weren't for the first expression, sum_to_n?([], 0) would return false`.