Ruby group array of ints by total without going over

In Ruby, I want to group an array of integers by a running total without the total going over a certain number. While keeping the integers in order.

I have this array of numbers from zero and one hundred:

numbers = [20, 40, 90, 20, 0, 10, 5, 30, 100, 40, 30]

I want to group them into sub-arrays so that the total within a sub-array never exceeds 100.

For example, the first two numbers 20 and 40 sum to 60. The next number, 90, would cause the running total to be higher than 100. Therefore [20, 40] will form one sub-array and [90] will form the next sub-array. Both sub-arrays are less than (or equal to) 100. The numbers are kept in order. It's not permissible to grab the number 90 and move it next to the number 10 to make an even group of 100, because those numbers are not adjacent in the input array.

Thus the output should look like this:

numbers_in_groups_of_less_than_100 = [
  [20, 40],
  [90],
  [20, 0, 10, 5, 30],
  [100],
  [40, 30]
]

I wonder if this is possible with Ruby's inject method, but I haven't figured out the right block to pass to it. Also, it seems to me that a while loop could be used to accomplish this, but I'm having trouble figuring out the specifics of how to trigger the breakup of the array and reset the counter.

Solution

You can use each_with_object which works similar to inject but does not require you to return the accumulated object from the block.

numbers = [20, 40, 90, 20, 0, 10, 5, 30, 100, 40, 30]

numbers_in_groups_of_less_than_100 = numbers.each_with_object([[]]) do |i, result|
  result << [] if result.last.sum + i > 100
  result.last << i
end

Here, we construct an initial result object as an array containing a single empty array which will form our first group. For each number, we then check if the last group can still be used. If it is (over-)full, we start a new group by appending a new empty array to the result and use this as the new group.

Note that some edge-cases are not checked here and you may have to decide if and how you want to handle those:

If the numbers array is empty, you would get an array with an empty group using he above code.
If any number is larger than 100, the above code would still but it into its own group. You may have to decide if this would be okay or if you want to check for this and raise an error.

As for the implementation: one could argue that it would be faster to retain or store the running sum of the last group instead of calculating it in each loop again. However, getting the sum of integers in an array is quite fast in Ruby. Unless you are dealing with a very large number of numbers, optimizing this would result in more complex code for an inconsequential gain on performance accordingly.