Put an array into bins

Question

In this simple challenge you are given an input array L of non-negative integers and a number of bins b greater than 0 but no more than the length of L. Your code must return a new array M whose length is b and which has binned the array L. This is easiest explained with examples.

L = [1,0,5,1] and b = 2 returns M = [1,6].

L = [0,3,7,2,5,1] and b = 3 returns M = [3,9,6].

So far, so simple. However in this question b doesn't necessarily have to divide len(L). In this case the last bin will just have fewer numbers to make it up.

Each bin except possibly the last one must have the same number of numbers contributing to its total. The last bin must have no more numbers contributing to it than the other bins. The last bin must have as many numbers contributing to it as possible subject to the other rules.

L = [0,3,7,2,5,1] and b = 4 returns M = [3,9,6,0]. M = [10,8,0,0] is not an acceptable output as the third bin does not have the name number of numbers contributing to it as bins 1 and 2.

L = [0,3,7,2,5] and b = 2 returns M = [10,7]. M = [3, 14] is not an acceptable output as the last bin will have 3 elements contributing to it but the first has only 2.

L = [1,1,1,1,1,1,1] and b = 3 returns M = [3,3,1].

As a final rule, your code must run in linear time.

You may use any language or libraries you like and can assume the input is provided in any way you find convenient.

---

It turns out that there are some inputs which can't be solved. For example [1,1,1,1,1] and b=4. Your code can output whatever it likes for those inputs.

Answer 1

APL (Dyalog), 19 bytes

{+/⍺(⌈⍺÷⍨≢⍵)⍴⍵,⍺⍴0}

Try it online!

We append b zeros to the array before reshaping it into equal parts of ⌈⍺÷⍨≢⍵ (⌈ length of L ÷ b ⌉) and summing them, as depicted in ,⍺⍴0, since any amount of blank spots (which are not part of the original array) larger than b - 1 would be filled with at least b - 1 elements from other chunks, which makes the balancing point of the last group at maximum b - 1 difference from the rest. We use b > b - 1 because it is code golf.

For example, L with 15 elements and b = 3 wouldn't be grouped as

x x x x x x
x x x x x x
x x x 0 0 0

but rather as (note how the rightmost 2 xs "fills in" the leftmost zeros)

x x x x x
x x x x x
x x x x x

while a 16 elements array would be filled with 2 (3 - 1) blank spots, like

x x x x x x
x x x x x x
x x x x 0 0

Answer 2

Python 2, 65 bytes

f=lambda l,n:n and[sum(l[:len(l)/n+1])]+f(l[len(l)/n+1:],n-1)or[]

Try it online!

Answer 3

R, 75 71 70 63 bytes

function(L,b)colSums(matrix(L[1:(ceiling(sum(L|1)/b)*b)],,b),T)

Try it online!

This pads L with NA until the length is a multiple of b, then takes the column sums of L as a matrix with b columns, removing NA values.

Explaining as a stack-based language:

function(L,b){
      (ceiling(sum(L|1)/b*b)  # push the next multiple of b >= length(L), call it X
    1:..                      # push the range 1:X
  L[..]                       # use this as an index into L. This forces L
                              # to be padded to length X with NA for missing values
        matrix(..,,b)         # create a matrix with b columns, using L for values
                              # and proceeding down each column, so
                              # matrix(1:4,,2) would yield [[1,3],[2,4]]
colSums(.., na.rm = T)        # sum each column, removing NAs

Answer 4

MATL, 6 bytes

vi3$es

Try it online! Or verify all test cases.

Explanation

Consider input 4, [0,3,7,2,5,1] as an example.

v       % Vertically concatenate stack contents. Gives the empty array, []
        % STACK: []
i       % Input b
        % STACK: [], 4
        % Implicitly input L at the bottom of the stack
        % STACK: [0,3,7,2,5,1], [], 4
3$e     % 3-input reshape. This reshapes L with [] rows and b columns, in
        % column-major order (down, then across). [] here means that the
        % number of rows is chosen as needed to give b columns. Padding
        % with trailing zeros is applied if needed
        % STACK: [0 7 5 0;
                  3 2 1 0]
s       % Sum of each column
        % STACK: [3 9 6 0]
        % Implicitly display

Answer 5

Ruby, 54 53 bytes

Saved a byte thanks to @Kirill L.

->l,b{s=1.0*l.size/b;(1..b).map{l.shift(s.ceil).sum}}

Try it online!

Answer 6

C (gcc), 107 bytes

j,k,t,Q;f(A,l,b)int*A;{for(j=~0;b>++j;printf("%d,",t))for(t=k=0;(Q=!!(l%b)+l/b)>k;t+=Q<l?A[Q]:0)Q=k+++Q*j;}

Try it online!

Answer 7

Haskell, 61 bytes

l#0=[]
l#n|o<-length l`div`n+1=sum(take o l):(drop o l)#(n-1)

Try it online!

Answer 8

Java 10, 96 89 86 bytes

a->b->{int r[]=new int[b],i=0,n=a.length;for(;i<n;)r[i/((n+b-1)/b)]+=a[i++];return r;}

Try it online here.

Found a shorter way to write i/(n/b+(n%b==0?0:1) here: i/((n+b-1)/b)

Thanks to Olivier Grégoire for golfing 3 bytes.

Ungolfed version:

input -> bins -> { // input is int[] (original array), bins is int (number of bins)
    int result[] = new int[bins], // resulting array, initialized with all 0
    i = 0, // for iterating over the original array
    n = a.length; // length of the original array
    for(; i < n ;) // iterate over the original array
        result[i / ((n + bins - 1) / bins)] += input[i++]; // add the element to the right bin; that's bin n/bins if bins divides n, floor(n/bins)+1 otherwise
    return result;
}

Answer 9

Elixir, 98 bytes

fn l,b->Enum.map Enum.chunk(l++List.duplicate(0,b-1),round Float.ceil length(l)/b),&Enum.sum/1 end

Try it online!

The best Elixir has is splitting into parts with a length of n. And it cannot ceil division as integer very well, so we do float division, round it up. Unfortunately the only way to do this results in a float, so we round it again to an integer.

Answer 10

Perl 6,  52 51  50 bytes

52 bytes: Test it

->\L,\b{L.rotor(:partial,ceiling L/b)[^b].map: &sum}

51 bytes: Test it

{@^a.rotor(:partial,ceiling @a/$^b)[^$b].map: &sum}

50 bytes: Try it

{map &sum,@^a.rotor(:partial,ceiling @a/$^b)[^$b]}

---

47 bytes non-competing Test it

{@^a.rotor(:partial,ceiling @a/$^b)[^$b]».sum}

It's non-competing as ».sum is allowed to do the calculations in parallel. So it may or may not be in linear time.

---

Expanded:

{  # bare block with two placeholder parameters ｢@a｣ and ｢$b｣

  map                   # for each sublist

    &sum,               # find the sum


    @^a                 # declare and use first parameter

    .rotor(             # break it into chunks

      :partial,         # include trailing values that would be too few otherwise

      ceiling @a / $^b # the number of elements per chunk

    )[ ^$b ]           # get the correct number of chunks if it would be too few

}

Answer 11

Charcoal, 22 bytes

ＮθＡηＷ﹪Ｌηθ⊞η⁰Ｅ⪪η÷ＬηθＩΣι

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input b.

Ａη

Input L.

Ｗ﹪Ｌηθ⊞η⁰

Push a 0 to L until L's length is divisible by b.

Ｅ⪪η÷ＬηθＩΣι

Divide L's length by b and split L into sections of that length, then sum each section and cast to string for implicit output on separate lines.

Answer 12

JavaScript (Node.js), 71 bytes

L=>b=>Array(b).fill().map((v,i)=>L.slice(s=i*b,s+b).reduce((x,y)=>x+y))

Try it online!

Answer 13

C (clang), 58 bytes

i;f(*L,l,b,*m){b=l/b+!!(l%b);for(i=0;i<l;m[i++/b]+=L[i]);}

Try it online!

f() takes parameters as follows:
L: pointer to input array
l: length of input array
b: number of bins
m: pointer to buffer that receives new array

Following is a re-entrant version @ 60 bytes:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}

Answer 14

PHP, 88 bytes

function($a,$b){return array_map(array_sum,array_chunk($a,~-count($a)/$b+1))+[$b-1=>0];}

anonymous function, takes array and integer, returns array

The only golfing potential this had was replacing ceil(count($a)/$b)) with (count($a)-1)/$b+1 and abbreviating (count($a)-1) with ~-count($a). The resulting float is implicitly cast to integer in the array_chunk call.

Try it online.