CODEWITHSUNDEEP
ruby
bubbavox
bubbavox

Reputation: 23

#reduce loop within an #each loop isn't iterating through entire array

In the following program, the loop seems to stop after 2 runs, instead of 3 as expected. The expected value of sum_of_sums is 35, but here it is 23.

ary = [1,2,3,4]
sum_of_sums = 0
ary.each do  # => [1, 2, 3, 4]
  n=ary.shift  # => 1,         2
  sum_of_products = ary.reduce(0) do |memo,e|  # => [2, 3, 4], [3, 4]
                      memo+(n*e)  # => 2, 5, 9, 6, 14
                    end
  sum_of_sums += sum_of_products  # => 9, 23
end
sum_of_sums  # => 23

It works as expected with [1,2,3]:

ary = [1,2,3]
sum_of_sums = 0
ary.each do  # => [1, 2, 3]
  n=ary.shift  # => 1,      2
  sum_of_products = ary.reduce(0) do |memo,e|  # => [2, 3], [3]
                      memo+(n*e)  # => 2, 5, 6
                    end
  sum_of_sums += sum_of_products  # => 5, 11
end
sum_of_sums  # => 11

I'm trying to write a program which, for a set [a,b,c,d], computes ab + ac + ad + bc + bd + cd. I don't know how to express this pattern other than by example. And yes I could probably do it more explicitly, or more easily by factoring out terms, but I want to know why this loop isn't working!

EDIT: Thanks folks... It seems the problem was that the array was being modified with #shift within the #each loop. I ended up succeeding with this:

ary = [1,2,3,4]
sum = 0
until ary.count==1 do
  sum += ary.shift * ary.sum
end
sum

Upvotes: 2

Views: 109

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110725

Considering that your question has been answered I would like to suggest a more efficient way to perform the calculation. Notice that

(a+b+c)**2 = a**2 + b**2 + c**2 + 2*(ab + ac + bc)

so

ab + ac + bc = ((a+b+c)**2 - (a**2 + b**2 + c**2))/2

We therefore may write

def sum_of_cross_terms(arr)
  ((arr.sum)**2 - arr.reduce(0) { |t,n| t + n**2 })/2
end

sum_of_cross_terms([1, 2, 3])
  #=> 11

sum_of_cross_terms([1, 2, 3, 4])
  #=> 35

We see that the computational complexity of this calculation is O(arr.size), whereas the brute-force approach is O((arr.size)**2). An example of the latter is

def sum_of_cross_terms(arr)
  arr.combination(2).sum { |a,b| a*b }
end

Upvotes: 2

Casper
Casper

Reputation: 34328

Like spickermann said your are modifying the array you are iterating while iterating it. This will produce unexpected results.

If you want to use shift then construct the loop using something which is not affected by shifting (modifying) the array.

(ary.size-1).times.map { ary.shift * ary.sum }.sum

Without modifying the array it becomes a bit more verbose:

(ary.size-1).times.map { |i| ary[i] * ary.drop(i+1).sum }.sum

You could also make a duplicate before iteration:

ary.dup.map { ary.shift * ary.sum }.sum

Or using with_index:

ary.map.with_index { |n, i| n * ary.drop(i+1).sum }.sum

There are many other ways to do this too, but hopefully this gives you some ideas.

Upvotes: 1

Related Questions