12

Die Aufgabe bei dieser Herausforderung besteht darin, Elemente eines Arrays in Zeiträume zu verschieben. Die Eingabe besteht aus einem nicht abnehmenden Array positiver Ganzzahlen, die die Zeit der Ereignisse darstellen, und einer Ganzzahl, die die Größe jedes Bins darstellt. Beginnen wir mit einem Beispiel. Wir nennen das Input-Array Aund das Output-Array O.

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

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

Warum ? Mit a bin_size = 2haben wir die folgenden Intervalle: (0,2], (2,4], (4,6], (6,8], (8,10]Wenn sich vier Elemente (1,1,1,2)innerhalb des ersten Intervalls befinden (0,2], keines im zweiten und dritten Intervall, eines 7im Intervall (6,8]und eines 10im Intervall (8,10].

Ihr Code sollte jedes Längenintervall berücksichtigen, bin_sizebeginnend mit 0und zählen, wie viele Zahlen Ain jedem enthalten sind. Sie sollten immer das rechte Ende eines Intervalls in eine Bin einbeziehen, damit im obigen Beispiel 2die Anzahl von berücksichtigt wird 4. Ihr Code sollte in linearer Zeit in der Summe der Längen der Eingabe und Ausgabe ausgeführt werden.

Mehr Beispiele:

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

Sie können davon ausgehen, dass die Ein- und Ausgabe in jedem Format erfolgen kann, das Sie für zweckmäßig halten. Sie können beliebige Sprachen und Bibliotheken verwenden.

code-golf restricted-complexity
quelle

Sind Ausgaben mit nachgestellten 0s erlaubt? Also zurück [2,0,1,1,1,0]statt [2,0,1,1,1]?

Kevin Cruijssen

Bitte keine nachgestellten Nullen.

2

Was ist mit Situationen, in denen der maximale Array-Wert nicht ein Vielfaches von dem bin_sizeist? Sollten wir wirklich damit umgehen? Die meisten Antworten scheinen dies zu tun, aber in diesem Fall wäre es hilfreich, einen Testfall für dieses Szenario hinzuzufügen, um Verwirrung zu vermeiden.

Kirill L.

@KirillL. Ja, sie sollten auch behandelt werden.

1

@GPS 0 ist keine positive ganze Zahl. Dies ist kein Unfall :)

9

R , 48 Bytes

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

Probieren Sie es online!

Noch einmal, tableund cutversuchen Sie es mit factordem Binning. Gibt einen Namen aus, vectorin dem namesdie Intervalle angegeben sind, z. B. in Intervallnotation (0,5].

BEARBEITEN: Zurück zur früheren Version, die funktioniert, wenn snicht geteilt wird n.

Giuseppe
quelle

Ich weiß wirklich nicht R, aber auf TIO scheint dies ein format you [most likely do not] find convenientohne den tableTeil auszugeben .

Mein Pronomen ist monicareinstate

@jemand ist genau deshalb da. cutteilt den Vektor in Faktoren auf, deren Pegel durch die Intervalle vorgegeben sind, und tablezählt die Vorkommen jedes einzelnen Werts in seiner Eingabe.

Giuseppe

1

@ jemand ah, ich verstehe, ich habe deinen Kommentar falsch verstanden. Nein, ich denke, das wäre nicht gültig, da wir die Anzahl der einzelnen Behälter benötigen.

Giuseppe

1

Nicht vollständig getestet, aber ich denke, Sie können ein paar Bytes sparen, 0:ceiling(max(n)/s)*smit denen Sie ersetzen können seq(0,max(n)+s-1,s). Es funktioniert zumindest für die beiden in Frage kommenden Stichproben.

Gregor - Monica

1

@ Gregor Hmm, wenn das funktioniert, 1:max(n/s+1)*s-sist eine weitere Verbesserung, da die beiden gleichwertig sind

Giuseppe

6

Oktave , 36 Bytes

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

Probieren Sie es online!

Ostereier jagen und Lagerfeuer machen. Ich werde eine Erklärung hinzufügen, wenn ich Zeit habe.

Stewie Griffin
quelle

3

Perl 5 `-a` `-i` , 32 28 Bytes

Geben Sie count nach der Option -i an. Geben Sie für jedes Eingabeelement in STDIN eine separate Zeile an

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

Probieren Sie es online!

Tonne Hospel
quelle

2

Das ist beeindruckend.

3

Python 2 , 62 Bytes

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

Probieren Sie es online!

Totes Opossum
quelle

1

Zuallererst: nette Antwort, ich habe es bereits + 1-bearbeitet (und einen Port in Java erstellt, weil er ziemlich viel kürzer ist als der, den ich hatte). Nachgestellte Nullen jedoch nicht erlaubt (nur gefragt OP), so I[-1]/s+1sollte ~-I[-1]/s+1statt.

Kevin Cruijssen

@ KevinCruijssen Danke für den Hinweis!

Totes Opossum

3

05AB1E , 18 Bytes

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

Probieren Sie es online!

Emigna
quelle

Ich kenne 05AB1E nicht so gut, aber dies scheint A.count max (A) zu nennen , so dass die Laufzeit in len (A) + len (O) nicht linear ist . Ist das richtig oder habe ich etwas falsch gemacht?

Dennis

@Dennis count wäre O(max(A)*max(A))... also ist es quadratisch auf dem Maximum von A ... OP angegeben, dass es linear sein muss in Bezug auf ... was genau?

Magic Octopus Urn

2

@MagicOctopusUrn Ihr Code sollte in der Summe der Längen der Eingabe und Ausgabe in linearer Zeit ausgeführt werden. Dies entspricht der neuesten Version.

Dennis

2

@Dennis das scheint eher willkürlich.

Magic Octopus Urn

2

@MagicOctopusUrn Es ist die einzig sinnvolle Definition für lineare Zeit für diese Frage, denke ich.

2

APL + WIN, 23 Bytes

Fordert zur Eingabe von Bins und dann von Ganzzahlen auf:

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

Erläuterung:

⎕ 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
quelle

2

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

Probieren Sie es online!

G. Sliepen
quelle

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

Port of @ DeadPossums Python 2-Antwort , also stimmen Sie seiner Antwort unbedingt zu!

Erläuterung:

Probieren Sie es online aus.

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
quelle

2

Ruby , 60 Bytes

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

Probieren Sie es online!

Setzen Sie Monica wieder ein - notmaynard
quelle

2

JavaScript (ES6), 60 Byte / O (Länge (a) + Maximum (a) / n)

5 Bytes dank @Neil gespart

Übernimmt Eingaben in der Currying-Syntax (a)(n).

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

Probieren Sie es online!

Oder nur 43 Bytes / O (len (a)), wenn leere Elemente zulässig sind.

Arnauld
quelle

[...o].map(n=>n|0)Ruft die erste Ausgabe der zweiten Lösung in weniger Bytes ab.

Neil

@Neil Ich bin mir nicht sicher, warum ich mich für etwas so Verschlungenes entschieden habe. : - /

Arnauld

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

Hoppla, dieser kürzere ist nicht linear, sondern quadratisch.

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

Probieren Sie es online!

Angs
quelle

1

Pyth, 23 22 Bytes

Jm/tdeQhQK*]ZheJhXRK1J

Probieren Sie es hier aus

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

quelle

1

Rubin , 53 50 Bytes

Edit: -3 Bytes von iamnotmaynard.

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

Probieren Sie es online!

Kirill L.
quelle

Dies funktioniert nicht, wenn a.maxnicht ein Vielfaches von b(zB f[[1,1,1,2,7,10],3]=> [4, 0, 1]aber sollte geben [4, 0, 2]) ist. Ich hatte den gleichen Ansatz versucht.

Wiedereinsetzung von Monica - notmaynard

(oder besser gesagt [4, 0, 1, 1])

Wiedereinsetzung von Monica - notmaynard

Nun, dies lässt sich durch Umschalten auf einen Float-Max-Range-Wert beheben, aber ich werde OP auch bitten, dies in der Aufgabenbeschreibung zu klären.

Kirill L.

50 Bytes

Reinstate Monica - Notmaynard

Schön, noch besser, danke.

Kirill L.

1

Dieses Rätsel ist im Wesentlichen eine Zählsorte. Wir kennen die Länge der Ausgabe nicht, ohne zuerst die Eingabe durchzugehen.

C (clang) , 53 Bytes

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

Probieren Sie es online!

Diese Lösung akzeptiert die folgenden Parameter: Länge des
AEingabearrays
lvon A
bbin_size
Ostorage for Output. Muss ausreichend lang sein
und gibt die Ausgabe in O zurück.

Diese Lösung hat ein Handicap: Sie gibt nicht die Länge des Ausgabearrays O zurück, sodass der Anrufer nicht weiß, wie viel gedruckt werden soll.

Folgende Version überwindet dieses 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;}

Probieren Sie es online!

Es benötigt einen zusätzlichen Parameter mund gibt die Länge von Odarin zurück. Es hat mich 26 Bytes gekostet.

Geographisches Positionierungs System
quelle

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

Probieren Sie es online!

Vielen Dank an Kevin Cruijssen für die Kürzung von 12 Bytes und Ceilingcat für weitere 4 Bytes!

G. Sliepen
quelle

1

90 Bytes unter Verwendung von for-Schleifen, das Entfernen der intund Ändern ==1zu >0.

Kevin Cruijssen

Bitte. Übrigens, nur eine Anmerkung, es ist derzeit ungültig (genau wie meine jetzt gelöschte Java-Antwort war). Es muss O(n)rechtzeitig ausgeführt werden, damit Sie keine verschachtelten for-Schleifen haben können. (Ihre C ++ - Antwort scheint jedoch in Ordnung zu sein. Ich habe diese also +1 gegeben. :))

Kevin Cruijssen

Es ist immer noch O (n). Die innere Schleife gibt immer einen Wert aus, und wir geben nur Werte (maximaler Wert + 1) / Binsize-Werte insgesamt aus.

G. Sliepen

Hmm, but isn't the outer loop already O(n) by looping over the input items. Even if the inner loop would only loop 2 times it's already above O(n). Or am I misunderstanding something.. I must admit O-times aren't really my expertise..

Kevin Cruijssen

1

Die innere Schleife iteriert jedoch nicht über alle Eingabeelemente, sondern nur über die Anzahl der Ausgabewerte, die gedruckt werden müssen, um die Position des letzten Eingabeelements "einzuholen". Wenn der Eingabevektor aus vielen Duplikaten oder Werten besteht, die sich weniger als die Bin-Größe unterscheiden, führt die innere Schleife überhaupt keine Iterationen durch. Wenn der Eingabevektor dagegen sehr dünn ist, führt die innere Schleife mehr Iterationen durch und druckt Nullen. Um korrekt zu sein, wird der Code in der Zeit O ((Anzahl der Eingabeelemente) + (letztes Element / Bin-Größe)) ausgeführt. Dies ist immer noch linear.

G. Sliepen

Binning in der Zeit

Antworten:

R , 48 Bytes

Oktave , 36 Bytes

Perl 5 `-a` `-i` , 32 28 Bytes

Python 2 , 62 Bytes

05AB1E , 18 Bytes

APL + WIN, 23 Bytes

C ++ (GCC) , 90 83 Bytes

Java 8, 75 Bytes

Ruby , 60 Bytes

JavaScript (ES6), 60 Byte / O (Länge (a) + Maximum (a) / n)

Haskell , 63 75 70 Bytes

Pyth, 23 22 Bytes

Rubin , 53 50 Bytes

C (clang) , 53 Bytes

C (clang) , 79 Bytes

C (gcc) , 102 90 89 86 Bytes

Binning in der Zeit

Antworten:

R , 48 Bytes

Oktave , 36 Bytes

Perl 5 -a -i , 32 28 Bytes

Python 2 , 62 Bytes

05AB1E , 18 Bytes

APL + WIN, 23 Bytes

C ++ (GCC) , 90 83 Bytes

Java 8, 75 Bytes

Ruby , 60 Bytes

JavaScript (ES6), 60 Byte / O (Länge (a) + Maximum (a) / n)

Haskell , 63 75 70 Bytes

Pyth, 23 22 Bytes

Rubin , 53 50 Bytes

C (clang) , 53 Bytes

C (clang) , 79 Bytes

C (gcc) , 102 90 89 86 Bytes

Perl 5 `-a` `-i` , 32 28 Bytes