Regroupement dans le temps

12

La tâche dans ce défi est de mettre des éléments d'un tableau dans des bacs de temps. L'entrée sera un tableau non décroissant d'entiers positifs représentant l'heure des événements, et un entier qui représente la taille de chaque bac. Commençons par un exemple. Nous appelons le tableau d'entrée Aet le tableau de sortie O.

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

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

Pourquoi ? Avec a bin_size = 2, nous aurons les intervalles suivants:, (0,2], (2,4], (4,6], (6,8], (8,10]où quatre éléments se (1,1,1,2)trouvent dans le premier intervalle (0,2], aucun dans les deuxième et troisième intervalles, un 7dans l'intervalle (6,8]et un 10dans l'intervalle (8,10].

Votre code doit tenir compte de chaque intervalle de longueur à bin_sizepartir de 0et compter le nombre de numéros Aqu'il contient. Vous devez toujours inclure la fin droite d'un intervalle dans un bac de sorte que dans l'exemple ci 2- dessus est inclus dans le nombre de 4. Votre code doit s'exécuter en temps linéaire dans la somme des longueurs de l'entrée et de la sortie.

Plus d'exemples:

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

Vous pouvez supposer que l'entrée et la sortie peuvent être données dans n'importe quel format qui vous convient. Vous pouvez utiliser toutes les langues et bibliothèques de votre choix.

code-golf restricted-complexity
la source
Les sorties avec 0s de fin sont-elles autorisées? Vous revenez donc [2,0,1,1,1,0]au lieu de [2,0,1,1,1]?
Kevin Cruijssen
Pas de zéros à la fin s'il vous plaît.
2
Qu'en est-il des situations où la valeur maximale du tableau n'est pas un multiple de bin_size, devrions-nous vraiment les gérer? Il semble que la plupart des réponses le soient, mais si c'est le cas, il serait bon d'ajouter un cas de test pour ce scénario pour éviter toute confusion.
Kirill L.
@KirillL. Oui, ils devraient également être manipulés.
1
@GPS 0 n'est pas un entier positif. Ce n'est pas un accident :)

Réponses:

9

R , 48 octets

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

Essayez-le en ligne!

Encore une fois, tableet faites cutun factortour pour le binning. Les sorties d' un nommé vectoroù namessont les intervalles, dans la notation des intervalles, par exemple, (0,5].

EDIT: revenir à la version précédente qui fonctionne quand sne se divise pas n.

Giuseppe
la source
Je n'ai vraiment pas R, mais sur TIO cela semble produire un format you [most likely do not] find convenientsans la tablepartie.
mon pronom est monicareinstate
@quelqu'un c'est exactement pourquoi c'est là. cutdivise le vecteur en facteurs avec des niveaux donnés par les intervalles et tablecompte les occurrences de chaque valeur unique dans son entrée.
Giuseppe
1
@ quelqu'un ah, je vois, j'ai mal compris votre commentaire. Non, je pense que ce ne serait pas valable car nous avons besoin du nombre de chaque bac.
Giuseppe
1
Pas entièrement testé, mais je pense que vous pouvez économiser quelques octets reaplacing 0:ceiling(max(n)/s)*savec seq(0,max(n)+s-1,s). Cela fonctionne au moins pour les deux échantillons de la question.
Gregor Thomas
1
@Gregor Hmm si cela fonctionne 1:max(n/s+1)*s-sest une autre amélioration puisque les deux sont équivalents
Giuseppe
6

Octave , 36 octets

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

Essayez-le en ligne!

À la chasse aux œufs de Pâques et à faire un feu de joie. J'ajouterai une explication quand j'aurai le temps.

Stewie Griffin
la source
3

Perl 5 -a -i , 32 28 octets

Donnez le nombre après l'option -i. Donnez chaque élément d'entrée sur une ligne distincte sur STDIN

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

Essayez-le en ligne!

Ton Hospel
la source
2
C'est impressionnant.
3

Python 2 , 62 octets

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

Essayez-le en ligne!

Possum mort
la source
1
Tout d'abord: belle réponse, je l'ai déjà +1 (et créé un port en Java, car il est un peu plus court que ce que j'avais). Les zéros de fin ne sont pas autorisés cependant (juste demandé OP), I[-1]/s+1devrait donc être à la ~-I[-1]/s+1place.
Kevin Cruijssen
@KevinCruijssen Merci pour l'avis!
Dead Possum
3

05AB1E , 18 octets

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

Essayez-le en ligne!

Emigna
la source
Je ne connais pas bien 05AB1E, mais cela semble appeler A.count max (A) , donc le temps d'exécution n'est pas linéaire en len (A) + len (O) . Est-ce correct ou ai-je eu quelque chose de mal?
Dennis
Le nombre de @Dennis serait O(max(A)*max(A))... donc c'est quadratique sur le maximum de A ... OP a précisé qu'il devait être linéaire en termes de ... quoi exactement?
Urne Magic Octopus
2
@MagicOctopusUrn Votre code doit s'exécuter en temps linéaire dans la somme des longueurs d'entrée et de sortie , selon la dernière révision.
Dennis
2
@Dennis qui semble plutôt arbitraire.
Urne de poulpe magique
2
@MagicOctopusUrn C'est la seule définition sensée du temps linéaire pour cette question je pense.
2

APL + WIN, 23 octets

Invite à saisir à l'écran les cases puis le vecteur d'entiers:

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

Explication:

⎕ 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
la source
2

Java 8, 75 octets

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

Port de @ DeadPossum's Python 2 answer , alors assurez-vous de voter pour sa réponse!

Explication:

Essayez-le en ligne.

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
la source
2

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

5 octets enregistrés grâce à @Neil

Prend des entrées dans la syntaxe de curry (a)(n).

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

Essayez-le en ligne!

Ou seulement 43 octets / O (len (a)) si les éléments vides sont autorisés.

Arnauld
la source
[...o].map(n=>n|0)obtient la première sortie de la deuxième solution en moins d'octets.
Neil
@Neil Je ne sais pas pourquoi je suis allé pour quelque chose d'aussi compliqué. : - /
Arnauld
2

Haskell , 63 75 70 octets

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

Oups, celui-ci n'est pas linéaire mais quadratique; 

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

Essayez-le en ligne!

Angs
la source
1

Pyth, 23 22 octets

Jm/tdeQhQK*]ZheJhXRK1J

Essayez-le ici

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

la source
1

Rubis , 53 50 octets

Edit: -3 octets par iamnotmaynard.

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

Essayez-le en ligne!

Kirill L.
la source
Cela ne fonctionne pas quand a.maxn'est pas un multiple de b(par exemple f[[1,1,1,2,7,10],3]=> [4, 0, 1]mais devrait donner [4, 0, 2]). J'avais essayé la même approche.
Rétablir Monica - notmaynard
(ou plutôt [4, 0, 1, 1])
Reinstate Monica - notmaynard
Eh bien, cela peut être résolu en passant à une valeur de plage maximale flottante, mais je demanderai également à OP de clarifier cela dans la description de la tâche.
Kirill L.
50 octets
Rétablir Monica - notmaynard
Bien, encore mieux, merci.
Kirill L.
1

Ce casse-tête est essentiellement un tri par compte. Nous ne connaissons pas la longueur de la sortie sans passer d'abord par l'entrée.

C (clang) , 53 octets

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

Essayez-le en ligne!

Cette solution prend les paramètres suivants: longueur du
Atableau d'entrée
ld'un stockage
bbin_size
Opour la sortie. Doit être de longueur suffisante
et renvoie la sortie en O.

Cette solution a un handicap: elle ne retourne pas la longueur du tableau de sortie O, et donc l'appelant ne sait pas combien imprimer.

La version suivante surmonte ce handicap:

C (clang) , 79 octets

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

Essayez-le en ligne!

Il prend un paramètre supplémentaire met en renvoie la longueur O. Cela m'a coûté 26 octets.

GPS
la source
1

C (gcc) , 102 90 89 86 octets

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

Essayez-le en ligne!

Merci à Kevin Cruijssen pour avoir réduit de 12 octets et plafondcat pour 4 autres octets!

G. Sliepen
la source
1
90 octets en utilisant for-loops, en supprimant intet en changeant ==1en >0.
Kevin Cruijssen
Je vous en prie. Btw, juste une note, il est actuellement invalide (tout comme ma réponse Java maintenant supprimée). Il est nécessaire de fonctionner à O(n)temps, donc vous ne pouvez pas avoir de boucles for imbriquées .. (Cependant, votre réponse C ++ semble
correcte
C'est toujours O (n). La boucle intérieure imprimera toujours une valeur, et nous n'imprimerons que (valeur maximale + 1) / valeurs de taille totale au total.
G. Sliepen
Hmm, mais ce n'est pas déjà la boucle externe O(n)en bouclant sur les éléments d'entrée. Même si la boucle intérieure ne boucle que 2 fois, c'est déjà au-dessus O(n). Ou suis-je en Otrain de mal comprendre quelque chose .. Je dois admettre que les temps ne sont pas vraiment mon expertise ..
Kevin Cruijssen
1
Mais la boucle interne n'itère pas sur tous les éléments d'entrée, elle ne fait qu'itérer sur le nombre de valeurs de sortie à imprimer pour "rattraper" la position correspondant au dernier élément d'entrée. Si le vecteur d'entrée se compose de nombreux doublons ou valeurs qui diffèrent moins que la taille du bac, la boucle intérieure n'effectuera aucune itération. D'un autre côté, si le vecteur d'entrée est très clairsemé, la boucle interne effectuera plus d'itérations, imprimant des 0. Donc, pour être correct, le code s'exécute en temps O ((nombre d'éléments d'entrée) + (dernière taille d'élément / bac)). C'est toujours linéaire.
G. Sliepen