Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Chunk a Ruby array according to streaks within it

Tags:

ruby

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.

like image 989
Rich Armstrong Avatar asked Feb 24 '09 17:02

Rich Armstrong


2 Answers

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.

like image 76
glenn mcdonald Avatar answered Nov 08 '22 23:11

glenn mcdonald


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: ;)

like image 38
Sarah Mei Avatar answered Nov 09 '22 00:11

Sarah Mei