Binning in time

Question

The task in this challenge is to put elements of an array into time bins. The input will be a non-decreasing array of positive integers representing the time of events, and an integer which represents the size of each bin. Let us start with an example. We call the input array A and the output array O.

`A = [1,1,1,2,7,10]` and `bin_size = 2`.

`O = [4,0,0,1,1]`.

Why? With a bin_size = 2, we'll have the following intervals: (0,2], (2,4], (4,6], (6,8], (8,10], where four items (1,1,1,2) are within the first interval (0,2], none in the second and third intervals, one 7 in the interval (6,8], and one 10 in the interval (8,10].

Your code should consider every interval of length bin_size starting from 0 and count how many numbers in A there are in each. You should always include the right hand end of an interval in a bin so in the example above 2 is included in the count of 4. Your code should run in linear time in the sum of the lengths of the input and output.

More examples:

`A = [1,2,7,12,15]`  and `bin_size = 5`.

`O = [2, 1, 2]`.

`A = [1,2,7,12,15]`  and `bin_size = 3`.

`O = [2,0,1,1,1]`.

You can assume that input and output can be given in any format you find convenient. You can use any languages and libraries you like.

Answer 1

R, 48 bytes

function(n,s)table(cut(n,0:ceiling(max(n)/s)*s))

Try it online!

Once again, table and cutting to a factor do the trick for the binning. Outputs a named vector where the names are the intervals, in interval notation, for instance, (0,5].

EDIT: Revert back to earlier version that works when s doesn't divide n.

Answer 2

Octave, 36 bytes

@(A,b)histc(A,1:b:A(end)+b)(1:end-1)

Try it online!

Out hunting Easter eggs and making a bonfire. I'll add an explanation when I have the time.

Answer 3

Python 2, 62 bytes

I,s=input()
B=[0]*(~-I[-1]/s+1)
for i in I:B[~-i/s]+=1
print B

Try it online!

Answer 4

Perl 5 -a -i, 32 28 bytes

Give count after the -i option. Give each input element on a separate line on STDIN

$G[~-$_/$^I]--}{say-$_ for@G

Try it online!

Answer 5

05AB1E, 18 bytes

θs/Å0¹vDyI/î<©è>®ǝ

Try it online!

Answer 6

APL+WIN, 23 bytes

Prompts for screen input of bins then vector of integers:

+⌿<\v∘.≤b×⍳⌈⌈/(v←⎕)÷b←⎕    

Explanation:

⎕ Prompt for input

⌈⌈/(v←⎕)÷b←⎕ divide the integers by bin size, take maximum and round up for number of bins

b×⍳ take number of bins from previous step and create a vector of bin upper boundaries

v∘.≤ apply outer product to generate boolean matrix where elements of vector ≤ boundaries

<\ switch off all 1's after first 1 in each row to filter multiple bin allocations

+⌿ sum columns for the result

Answer 7

Java 8, 75 bytes

a->b->{var r=new int[~-a[a.length-1]/b+1];for(int i:a)r[~-i/b]++;return r;}

Port of @DeadPossum's Python 2 answer, so make sure to upvote his answer!

Explanation:

Try it online.

a->b->{          // Method with integer-array and integer parameters and no return-type
  var r=new int[~-a[a.length-1]/b+1];
                 //  Result integer-array of size `((last_item-1)/bin_length)+1`
  for(int i:a)   //  Loop over the input-array
    r[~-i/b]++;  //   Increase the value at index `(i+1)/bin_length` by 1
  return r;}     //  Return the result-array

Answer 8

C++ (gcc), 90 83 bytes

auto f(auto i,int s){typeof i j;for(auto v:i)--v/=s,j.resize(v+1),j[v]++;return j;}

Try it online!

Answer 9

JavaScript (ES6), 60 bytes / O(len(a)+max(a)/n)

Saved 5 bytes thanks to @Neil

Takes input in currying syntax (a)(n).

a=>n=>[...a.map(x=>o[x=~-x/n|0]=-~o[x],o=[])&&o].map(n=>~~n)

Try it online!

Or just 43 bytes / O(len(a)) if empty elements are allowed.

Answer 10

Ruby, 60 bytes

->a,b{(b...a[-1]+b).step(b).map{|i|a.count{|n|n<=i&&n>i-b}}}

Try it online!

Answer 11

Haskell, 63 75 70 bytes

l!n=l#[n,2*n..]
[]#_=[]
l#(b:i)|h<-length$takeWhile(<=b)l=h:drop h l#i

Whoops, this shorter one isn't linear but quadratic;

l!n=l#[n,2*n..]
[]#_=[]
l#(b:i)=sum[1|a<-l,a<=b]:[a|a<-l,a>b]#i

Try it online!

Answer 12

C (gcc), 102 90 89 86 bytes

#define P!printf("%d ",k)
i,j,k;f(s){for(i=s;~scanf("%d",&j);k++)for(;j>i;i+=s)k=P;P;}

Try it online!

Thanks to Kevin Cruijssen for slashing off 12 bytes, and ceilingcat for another 4 bytes!

Answer 13

Pyth, 23 22 bytes

Jm/tdeQhQK*]ZheJhXRK1J

Try it here

Jm/tdeQhQK*]ZheJhXRK1J
Jm/tdeQhQ                 Find the bin for each time and save them as J.
         K*]ZheJ          Create empty bins.
                 XRK1J    Increment the bins for each time within them.
                h         Take the first (because mapping returned copies).

Answer 14

Ruby, 53 50 bytes

Edit: -3 bytes by iamnotmaynard.

->a,b{(0..~-a.max/b).map{|i|a.count{|x|~-x/b==i}}}

Try it online!

Answer 15

This puzzle is essentially a Count-sort. We don't know the length of output without going through input first.

C (clang), 53 bytes

i,j;f(*A,l,b,*O){for(j=0;j<l;O[(A[j++]+b-1)/b-1]++);}

Try it online!

This solution takes following parameters:
A input array
l length of A
b bin_size
O storage for Output. Must be sufficient length
and returns output in O.

This solution has a handicap: it doesn't return the length of output array O, and so caller doesn't know how much to print.

Following version overcomes that handicap:

C (clang), 79 bytes

i,j,k;f(*A,l,b,*O,*m){for(k=j=0;j<l;O[i=(A[j++]+b-1)/b-1]++,k=k>i?k:i);*m=++k;}

Try it online!

It takes an additional parameter m and returns length of O in it. It cost me 26 bytes.