Reduce a Ruby array

Question

Summary: The basic question here was, I've discovered, whether you can pass a code block to a Ruby array which will actually reduce the contents of that array down to another array, not to a single value (the way inject does). The short answer is "no".

I'm accepting the answer that says this. Thanks to Squeegy for a great looping strategy to get streaks out of an array.

The Challenge: To reduce an array's elements without looping through it explicitly.
The Input: All integers from -10 to 10 (except 0) ordered randomly.
The Desired Output: An array representing streaks of positive or negative numbers. For instance, a -3 represents three consecutive negative numbers. A 2 represents two consecutive positive numbers.

Sample script:

original_array = (-10..10).to_a.sort{rand(3)-1}
original_array.reject!{|i| i == 0} # remove zero

streaks = (-1..1).to_a # this is a placeholder.  
# The streaks array will contain the output.
# Your code goes here, hopefully without looping through the array

puts "Original Array:"
puts original_array.join(",")
puts "Streaks:"
puts streaks.join(",")
puts "Streaks Sum:"
puts streaks.inject{|sum,n| sum + n}

Sample outputs:

Original Array:
3,-4,-6,1,-10,-5,7,-8,9,-3,-7,8,10,4,2,5,-2,6,-1,-9
Streaks:
1,-2,1,-2,1,-1,1,-2,5,-1,1,-2
Streaks Sum:
0


Original Array:
-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9,10
Streaks:
-10,10
Streaks Sum:
0

Note a few things:

• The streaks array has alternating positive and negative values.
• The sum of the elements streaks array is always 0 (as is the sum of the original).
• The sum of the absolute values of the streak array is always 20.

Hope that's clear!

Edit: I do realize that such constructs as reject! are actually looping through the array in the background. I'm not excluding looping because I'm a mean person. Just looking to learn about the language. If explicit iteration is necessary, that's fine.

Answer 1

original_array.each do |num|
  if streaks.size == 0
    streaks << num
  else
    if !((streaks[-1] > 0) ^ (num > 0))
      streaks[-1] += 1
    else
      streaks << (num > 0 ? 1 : -1)
    end
  end
end

The magic here is the ^ xor operator.

true ^ false  #=> true
true ^ true   #=> false
false ^ false #=> false

So if the last number in the array is on the same side of zero as the number being processed, then add it to the streak, otherwise add it to the streaks array to start a new streak. Note that sine true ^ true returns false we have to negate the whole expression.

Answer 2

new_array = original_array.dup
<Squeegy's answer, using new_array>

Ta da! No looping through the original array. Although inside dup it's a MEMCPY, which I suppose might be considered a loop at the assembler level?

http://www.ruby-doc.org/doxygen/1.8.4/array_8c-source.html

EDIT: ;)

Answer 3

Well, here's a one-line version, if that pleases you more:

streaks = original_array.inject([]) {|a,x| (a.empty? || x * a[-1] < 0 ? a << 0 : a)[-1] += x <=> 0; a}

And if even inject is too loopy for you, here's a really silly way:

  streaks = eval "[#{original_array.join(",").gsub(/((\-\d+,?)+|(\d+,?)+)/) {($1[0..0] == "-" ? "-" : "") + $1.split(/,/).size.to_s + ","}}]"

But I think it's pretty clear that you're better off with something much more straightforward:

streaks = []
original_array.each do |x|
  xsign = (x <=> 0)
  if streaks.empty? || x * streaks[-1] < 0
    streaks << xsign
  else
    streaks[-1] += xsign
  end
end

In addition to being much easier to understand and maintain, the "loop" version runs in about two-thirds the time of the inject version, and about a sixth of the time of the eval/regexp one.

PS: Here's one more potentially interesting version:

a = [[]]
original_array.each do |x|
  a << [] if x * (a[-1][-1] || 0) < 0
  a[-1] << x
end
streaks = a.map {|aa| (aa.first <=> 0) * aa.size}

This uses two passes, first building an array of streak arrays, then converting the array of arrays to an array of signed sizes. In Ruby 1.8.5, this is actually slightly faster than the inject version above (though in Ruby 1.9 it's a little slower), but the boring loop is still the fastest.