Binning no tempo

12

A tarefa neste desafio é colocar elementos de uma matriz em intervalos de tempo. A entrada será uma matriz não decrescente de números inteiros positivos que representam a hora dos eventos e um número inteiro que representa o tamanho de cada posição. Vamos começar com um exemplo. Chamamos a matriz de entrada Ae a matriz de saída O.

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

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

Por que ? Com a bin_size = 2, teremos os seguintes intervalos:, (0,2], (2,4], (4,6], (6,8], (8,10]onde quatro itens (1,1,1,2)estão dentro do primeiro intervalo (0,2], nenhum no segundo e terceiro intervalos, um 7no intervalo (6,8]e outro 10no intervalo (8,10].

Seu código deve considerar cada intervalo de comprimento a bin_sizepartir de 0e contar quantos números Aexistem em cada um. Você sempre deve incluir a extremidade direita de um intervalo em uma posição para que o exemplo acima 2seja incluído na contagem de 4. Seu código deve ser executado em tempo linear na soma dos comprimentos da entrada e da saída.

Mais exemplos:

`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]`.

Você pode assumir que entrada e saída podem ser fornecidas em qualquer formato que achar conveniente. Você pode usar qualquer idioma e biblioteca que desejar.

code-golf restricted-complexity
fonte
São 0permitidas saídas com s à direita ? Então, retornando em [2,0,1,1,1,0]vez de [2,0,1,1,1]?
Kevin Cruijssen 30/03
Sem zeros à direita, por favor.
2
E as situações em que o valor máximo da matriz não é um múltiplo de bin_size, devemos realmente lidar com isso? Parece que a maioria das respostas sim, mas se sim, seria bom adicionar um caso de teste para esse cenário para evitar confusão.
31418 Kirill L.
@KirillL. Sim, eles devem ser manuseados também.
1
@GPS 0 não é um número inteiro positivo. Este não é um acidente :)

Respostas:

9

R , 48 bytes

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

Experimente online!

Mais uma vez, tablee cuttentando factorfazer o truque para o armazenamento. Emite um nome vectoronde namesestão os intervalos, em notação de intervalo, por exemplo (0,5],.

EDIT: reverta para a versão anterior que funciona quando snão é dividida n.

Giuseppe
fonte
Realmente não R, mas no TIO isso parece gerar um format you [most likely do not] find convenientsem a tableparte.
meu pronome é monicareinstate 30/03
@ alguém que é exatamente por que está lá. cutdivide o vetor em fatores com níveis dados pelos intervalos e tableconta as ocorrências de cada valor único em sua entrada.
Giuseppe
1
@ alguém ah, entendi, eu não entendi o seu comentário. Não, acho que isso não seria válido, pois precisamos das contagens de cada caixa.
Giuseppe
1
Não totalmente testados, mas eu acho que você pode salvar um casal bytes reaplacing 0:ceiling(max(n)/s)*scom seq(0,max(n)+s-1,s). Funciona pelo menos para as duas amostras da pergunta.
Gregor Thomas
1
@Gregor Hmm se isso funciona 1:max(n/s+1)*s-sé outra melhoria desde os dois são equivalentes
Giuseppe
6

Oitava , 36 bytes

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

Experimente online!

Caçando ovos de Páscoa e fazendo uma fogueira. Vou adicionar uma explicação quando tiver tempo.

Stewie Griffin
fonte
3

Perl 5 -a -i , 32 28 bytes

Dê contagem após a opção -i. Dê a cada elemento de entrada em uma linha separada em STDIN

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

Experimente online!

Ton Hospel
fonte
2
Isso é impressionante.
3

Python 2 , 62 bytes

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

Experimente online!

Gambá morto
fonte
1
Primeiro de tudo: resposta legal, eu já a adicionei com +1 (e criei uma porta em Java, porque é um pouco menor do que o que eu tinha). No entanto, zeros à direita não são permitidos (apenas OP solicitado); portanto, I[-1]/s+1deve ser ~-I[-1]/s+1.
Kevin Cruijssen 30/03
@KevinCruijssen Obrigado pelo aviso!
99905Preço
3

05AB1E , 18 bytes

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

Experimente online!

Emigna
fonte
Eu não conheço 05AB1E tão bem, mas isso parece chamar A.count max (A) , portanto, o tempo de execução não é linear em len (A) + len (O) . Isso está correto ou eu entendi algo errado?
Dennis
A contagem de @Dennis seria O(max(A)*max(A))... então é quadrática no máximo de A ... OP especificado que tinha que ser linear em termos de ... o que exatamente?
Magic Octopus Urn
2
@MagicOctopusUrn Seu código deve ser executado em tempo linear na soma dos comprimentos de entrada e saída , de acordo com a revisão mais recente.
Dennis
2
@ Dennis que parece bastante arbitrário.
Magic Octopus Urn
2
@MagicOctopusUrn É a única definição sensata para tempo linear para esta pergunta, eu acho.
2

APL + WIN, 23 bytes

Solicita a entrada na tela de caixas e o vetor de números inteiros:

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

Explicação:

⎕ 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
Graham
fonte
2

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;}

Porto da resposta Python 2 do @ DeadPossum , portanto, certifique-se de aprovar a resposta dele!

Explicação:

Experimente 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
Kevin Cruijssen
fonte
2

JavaScript (ES6), 60 bytes / O (len (a) + máximo (a) / n)

Guardado 5 bytes graças a @Neil

Recebe entrada na sintaxe de currying (a)(n).

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

Experimente online!

Ou apenas 43 bytes / O (len (a)) se elementos vazios forem permitidos.

Arnauld
fonte
[...o].map(n=>n|0)obtém a primeira saída da segunda solução em menos bytes.
Neil
@ Neil Não sei por que eu fui para algo tão complicado. : - /
Arnauld 30/03
2

Haskell , 63 75 70 bytes

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

Opa, esse menor não é linear, mas quadrático; 

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

Experimente online!

Angs
fonte
1

Pitão, 23 22 bytes

Jm/tdeQhQK*]ZheJhXRK1J

Experimente aqui

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).

fonte
1

Ruby , 53 50 bytes

Edit: -3 bytes por iamnotmaynard.

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

Experimente online!

Kirill L.
fonte
Isso não funciona quando a.maxnão é múltiplo de b(por exemplo, f[[1,1,1,2,7,10],3]=> [4, 0, 1]mas deve fornecer [4, 0, 2]). Eu tentei a mesma abordagem.
Reintegrar Monica - notmaynard
(ou melhor [4, 0, 1, 1])
Restabelece Monica - notmaynard 30/03
Bem, isso é corrigível alternando para um valor de intervalo máximo flutuante, mas também solicitarei ao OP que esclareça isso na descrição da tarefa.
31418 Kirill L.
50 bytes
Restabelecer Monica - notmaynard 31/03
Bom, melhor ainda, obrigado.
31418 Kirill L.
1

Este quebra-cabeça é essencialmente um tipo de contagem. Não sabemos o tamanho da saída sem passar pela entrada primeiro.

C (clang) , 53 bytes

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

Experimente online!

Esta solução utiliza os seguintes parâmetros: comprimento da
Amatriz de entrada
lde Um armazenamento
bbin_size
Opara Saída. Deve ter comprimento suficiente
e retornar a saída em O.

Esta solução tem uma desvantagem: ela não retorna o comprimento da matriz de saída O e, portanto, o chamador não sabe quanto imprimir.

A versão seguinte supera essa desvantagem:

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;}

Experimente online!

Ele pega um parâmetro adicional me retorna o comprimento Odele. Custou-me 26 bytes.

GPS
fonte
1

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;}

Experimente online!

Agradecemos a Kevin Cruijssen por cortar 12 bytes, e o tetocat por mais 4 bytes!

G. Sliepen
fonte
1
90 bytes usando loops de for, removendo inte mudando ==1para >0.
Kevin Cruijssen 30/03
De nada. Btw, apenas uma observação, é atualmente inválido (assim como minha resposta Java agora excluída foi). É necessário para executar em O(n)tempo, então você não pode ter qualquer aninhados para loops .. (Seu C ++ resposta parece bem, embora Então eu + 1-ed que um :)..)
Kevin Cruijssen
Ainda é O (n). O loop interno sempre imprimirá um valor, e nós apenas imprimimos (valor máximo + 1) / valores de tamanho bins no total.
G. Sliepen 30/03/19
Hmm, mas o loop externo já não está O(n)passando pelos itens de entrada. Mesmo que o loop interno faça loop apenas duas vezes, ele já está acima O(n). Ou eu estou mal-entendido alguma coisa .. Eu devo admitir O-times não são realmente minha experiência ..
Kevin Cruijssen
1
Mas o loop interno não repete todos os elementos de entrada, apenas repete quantos valores de saída ele precisar imprimir para "alcançar" a posição correspondente ao elemento de entrada mais recente. Se o vetor de entrada consistir em muitas duplicatas ou valores que diferem menos que o tamanho da bandeja, o loop interno não executará nenhuma iteração. Por outro lado, se o vetor de entrada for muito esparso, o loop interno executará mais iterações, imprimindo zeros. Portanto, para estar correto, o código é executado no tempo O ((número de elementos de entrada) + (último elemento / tamanho da lixeira)). Isso ainda é linear.
G. Sliepen 30/03/19