Legen Sie ein Array in Behälter

12

In dieser einfachen Herausforderung erhalten Sie ein Eingabearray Lmit nicht negativen ganzen Zahlen und einer Anzahl von Bins, die bgrößer als 0, aber nicht länger als 1 sind L. Ihr Code muss ein neues Array zurückgeben, Mdessen Länge bder Block des Arrays ist L. Dies wird am einfachsten anhand von Beispielen erklärt.

L = [1,0,5,1]und b = 2kehrt zurück M = [1,6].

L = [0,3,7,2,5,1]und b = 3kehrt zurück M = [3,9,6].

So weit, so einfach. In dieser Frage bmuss man sich jedoch nicht unbedingt teilen len(L). In diesem Fall enthält der letzte Behälter nur weniger Zahlen, um ihn zu bilden.

Jeder Behälter, außer möglicherweise der letzte, muss die gleiche Anzahl von Zahlen aufweisen, die zur Gesamtsumme beitragen. Das letzte Fach darf nicht mehr Nummern enthalten als die anderen Fächer. Der letzte Behälter muss so viele Zahlen wie möglich enthalten, abhängig von den anderen Regeln.

L = [0,3,7,2,5,1]und b = 4kehrt zurück M = [3,9,6,0]. M = [10,8,0,0]ist keine akzeptable Ausgabe, da der Name der dritten Bin nicht die Anzahl der als Bins 1und beitragenden Nummern enthält 2.

L = [0,3,7,2,5]und b = 2kehrt zurück M = [10,7]. M = [3, 14]ist keine akzeptable Ausgabe, da der letzte Bin 3Elemente enthält, die dazu beitragen, der erste jedoch nur 2.

L = [1,1,1,1,1,1,1]und b = 3kehrt zurück M = [3,3,1].

Als letzte Regel muss Ihr Code in linearer Zeit ausgeführt werden.

Sie können eine beliebige Sprache oder Bibliothek verwenden und davon ausgehen, dass die Eingabe auf eine von Ihnen gewünschte Weise erfolgt.


Es stellt sich heraus, dass es einige Eingaben gibt, die nicht gelöst werden können. Zum Beispiel [1,1,1,1,1]und b=4. Ihr Code kann für diese Eingaben alles ausgeben, was er möchte.


quelle
6
Ich denke, noch ein paar Testfälle wären schön.
Jonathan Frech
5
your code must run in linear time- Ich würde jeden Algorithmus finden, der diesem natürlich nicht ganz komisch folgt
Uriel
2
@Uriel Es gibt keine Begrenzung, wie seltsam Code-Golf-Antworten sein können :)
4
@Lembik Doch inwiefern ist es für eine Code-Golf-Herausforderung von Vorteil , solche potenziellen seltsamen Ansätze nicht zuzulassen ?
Jonathan Frech
@ JonathanFrech es liegt nur an den Vorlieben des OP :)

Antworten:

5

APL (Dyalog) , 19 Bytes

{+/⍺(⌈⍺÷⍨≢⍵)⍴⍵,⍺⍴0}

Probieren Sie es online!

Wir hängen b Nullen an das Array an, bevor wir es in gleiche Teile von ⌈⍺÷⍨≢⍵( ⌈ Länge von L ÷ b ⌉ ) umformen und sie summieren, wie in gezeigt ,⍺⍴0, da jede Menge von leeren Punkten (die nicht Teil des ursprünglichen Arrays sind) größer als b ist - 1 würde mit mindestens b - 1 Elementen aus anderen Chunks gefüllt , was den Gleichgewichtspunkt der letzten Gruppe auf maximal b - 1 vom Rest unterscheidet. Wir gebrauchen b> b - 1, weil es Codegolf ist.

Zum Beispiel würde L mit 15 Elementen und b = 3 nicht als gruppiert werden

x x x x x x
x x x x x x
x x x 0 0 0

sondern als (beachten Sie, wie die am weitesten rechts stehenden 2 xs die am weitesten links stehenden Nullen "ausfüllt")

x x x x x
x x x x x
x x x x x

während ein 16- Elemente-Array mit 2 ( 3 - 1 ) leeren Stellen wie gefüllt wäre

x x x x x x
x x x x x x
x x x x 0 0
Uriel
quelle
3

R , 75 71 70 63 Bytes

function(L,b)colSums(matrix(L[1:(ceiling(sum(L|1)/b)*b)],,b),T)

Probieren Sie es online!

Diese Pads Lmit NAbis die Länge ein Vielfaches von ist b, nehmen dann die Spaltensummen Lals Matrix mitb Spalten und entfernen NAWerte.

Erklärung als stapelbasierte Sprache:

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

Giuseppe
quelle
Sehr schön und schnell! Der Aufstieg des R-Codierers ...
2
@Lembik Ich hatte das Glück, dass ich zwischen Ihnen bei TNB vorbeischaute und sagte: "Ich werde dies als Herausforderung posten", und Sie haben es tatsächlich gepostet.
Giuseppe
1
Oh schau, "length [<-" wird genauso zurückkehren wie unser Lieblingsfreund "[<-". Keine Bytes für weniger Lesbarkeit gespeichert:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@Vlo no bytes saved for less readabilityist wahrscheinlich das Motto von R Golfing ... obwohl ich nehme an, dass sum(L|1)ein Byte davon gespeichert ist length(L)!
Giuseppe
3

MATL , 6 Bytes

vi3$es

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Betrachten Sie Eingabe 4, [0,3,7,2,5,1]als Beispiel.

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
Luis Mendo
quelle
1
Dies ist aus meiner Sicht die beeindruckendste Antwort.
3

Ruby , 54 53 Bytes

Ein Byte dank @Kirill L. gespeichert

->l,b{s=1.0*l.size/b;(1..b).map{l.shift(s.ceil).sum}}

Probieren Sie es online!

Setzen Sie Monica wieder ein - notmaynard
quelle
Nizza, Sie können auch ein Byte speichern, indem Sie [0]*bdurch1..b
Kirill L.
@KirillL. Vielen Dank. War mir noch nicht einmal eingefallen.
Wiedereinsetzung von Monica - notmaynard
2

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

Probieren Sie es online!

Jonathan Frech
quelle
2

Haskell , 61 Bytes

l#0=[]
l#n|o<-length l`div`n+1=sum(take o l):(drop o l)#(n-1)

Probieren Sie es online!

total menschlich
quelle
2
Scheint nicht zu funktionieren [1, 2, 3, 4, 5, 6] # 3.
Nwellnhof
2

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

Probieren Sie es hier online aus .

Einen kürzeren Weg zum Schreiben i/(n/b+(n%b==0?0:1) hier gefunden: i/((n+b-1)/b)

Dank an Olivier Grégoire für das Golfen mit 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;
}
OOBalance
quelle
86 Bytes
Olivier Grégoire
@ OlivierGrégoire Danke!
Bilanz
1

Elixier , 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

Probieren Sie es online!

Das beste Elixier ist das Teilen in Teile mit einer Länge von n . Und es kann keine Ceil Division als Integer geben, also runden wir die Division auf. Leider führt die einzige Möglichkeit, dies zu tun, zu einem Float, sodass wir es erneut auf eine Ganzzahl runden.

Okx
quelle
Einige Ihrer Ausgaben haben die falsche Länge.
@Lembik hat es behoben.
Okx
1

Perl 6 ,  52 51  50 Bytes

52 Bytes: Testen Sie es

->\L,\b{L.rotor(:partial,ceiling L/b)[^b].map: &sum}

51 Bytes: Testen Sie es

{@^a.rotor(:partial,ceiling @a/$^b)[^$b].map: &sum}

50 Bytes: Probieren Sie es aus

{map &sum,@^a.rotor(:partial,ceiling @a/$^b)[^$b]}

47 Bytes nicht konkurrierend Testen Sie es

{@^a.rotor(:partial,ceiling @a/$^b)[^$b]».sum}

Es ist nicht konkurrierend, da ».sumes erlaubt ist, die Berechnungen parallel durchzuführen. Es kann also in linearer Zeit sein oder nicht.


Erweitert:

{  # 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

}
Brad Gilbert b2gills
quelle
1

Holzkohle , 22 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

Nθ

Eingabe b.

Aη

Eingabe L.

W﹪Lηθ⊞η⁰

Drücken Sie a 0bis, Lbis Ldie Länge durch teilbar ist b.

E⪪η÷LηθIΣι

Teilen Sie Ldie Länge durch bund teilen Sie sie Lin Abschnitte dieser Länge auf, addieren Sie dann die einzelnen Abschnitte und setzen Sie sie für die implizite Ausgabe in separaten Zeilen in einen String um.

Neil
quelle
1

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

Probieren Sie es online!

f()Nimmt folgende Parameter an::
LZeiger auf Eingabearray
l: Länge des Eingabearrays
b: Anzahl der Bins
m : Zeiger auf Puffer, der ein neues Array empfängt

Es folgt eine wiedereintretende Version mit 60 Bytes:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}
Geographisches Positionierungs System
quelle
1

PHP, 88 Bytes

function($a,$b){return array_map(array_sum,array_chunk($a,~-count($a)/$b+1))+[$b-1=>0];}

anonyme Funktion, nimmt Array und Integer, gibt Array zurück

Das einzige Golf Potenzial dies hatte ersetzt ceil(count($a)/$b))mit (count($a)-1)/$b+1und Abkürzen (count($a)-1)mit ~-count($a). Der resultierende Gleitkommawert wird im array_chunkAufruf implizit in eine Ganzzahl umgewandelt .

Probieren Sie es online aus .

Titus
quelle