12
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ I think a few more test cases would be nice. \$\endgroup\$ – Jonathan Frech Mar 27 '18 at 20:08
  • 5
    \$\begingroup\$ your code must run in linear time - I would find any algorithm who doesn't follow this naturally quite weird \$\endgroup\$ – Uriel Mar 27 '18 at 20:18
  • 2
    \$\begingroup\$ @Uriel There is no limit to how weird code-golf answers can be :) \$\endgroup\$ – user9206 Mar 27 '18 at 21:19
  • 4
    \$\begingroup\$ @Lembik Though in what way is disallowing such potential weird approaches beneficial to a code-golf challenge? \$\endgroup\$ – Jonathan Frech Mar 27 '18 at 23:07
  • \$\begingroup\$ @JonathanFrech it’s just down to the preferences of the OP :) \$\endgroup\$ – user9206 Mar 28 '18 at 7:00

14 Answers 14

5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Very nice and quick! The rise of the R coder... \$\endgroup\$ – user9206 Mar 27 '18 at 19:44
  • 2
    \$\begingroup\$ @Lembik I was lucky enough to have popped into TNB right in between you saying "I'm going to post this as a challenge" and you actually posting it. \$\endgroup\$ – Giuseppe Mar 27 '18 at 19:55
  • 1
    \$\begingroup\$ Oh look "length[<-" will return too just like our favorite buddy "[<-". No bytes saved for less readability: function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T) \$\endgroup\$ – Vlo Mar 27 '18 at 20:46
  • 1
    \$\begingroup\$ @Vlo no bytes saved for less readability is probably the motto of R golfing...although I suppose that sum(L|1) is a byte saved from length(L)! \$\endgroup\$ – Giuseppe Mar 27 '18 at 20:48
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ This is the most impressive answer in my view. \$\endgroup\$ – user9206 Mar 30 '18 at 11:18
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Nice, you can also save a byte by replacing [0]*b by 1..b \$\endgroup\$ – Kirill L. Mar 29 '18 at 14:50
  • \$\begingroup\$ @KirillL. Thanks. Hadn't even occurred to me. \$\endgroup\$ – iamnotmaynard Mar 29 '18 at 22:06
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ Doesn't seem to work for [1, 2, 3, 4, 5, 6] # 3. \$\endgroup\$ – nwellnhof Mar 28 '18 at 11:55
2
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Some of your outputs have the wrong length. \$\endgroup\$ – user9206 Mar 27 '18 at 21:32
  • \$\begingroup\$ @Lembik fixed it. \$\endgroup\$ – Okx Mar 27 '18 at 21:51
1
\$\begingroup\$

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

}
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 22 bytes

NθAηW﹪Lηθ⊞η⁰E⪪η÷LηθIΣι

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

Nθ

Input b.

Aη

Input L.

W﹪Lηθ⊞η⁰

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

E⪪η÷LηθIΣι

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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]);}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy