Mettre un tableau dans des bacs

12

Dans ce défi simple, vous obtenez un tableau d'entrée Ld'entiers non négatifs et un nombre de cases bsupérieur à 0 mais pas plus que la longueur de L. Votre code doit renvoyer un nouveau tableau Mdont la longueur est bet qui a regroupé le tableau L. Ceci est expliqué plus facilement avec des exemples.

L = [1,0,5,1]et b = 2retourne M = [1,6].

L = [0,3,7,2,5,1]et b = 3retourne M = [3,9,6].

Jusqu'à présent, si simple. Cependant, dans cette question bne doit pas nécessairement diviser len(L). Dans ce cas, le dernier bac aura juste moins de numéros à composer.

Chaque bac, sauf éventuellement le dernier, doit avoir le même nombre de chiffres contribuant à son total. Le dernier bac ne doit pas avoir plus de numéros qui y contribuent que les autres bacs. Le dernier bac doit avoir autant de numéros qui y contribuent que possible sous réserve des autres règles.

L = [0,3,7,2,5,1]et b = 4retourne M = [3,9,6,0]. M = [10,8,0,0]n'est pas une sortie acceptable car le troisième bac n'a pas le nombre de nombres qui y contribuent en tant que bacs 1et 2.

L = [0,3,7,2,5]et b = 2retourne M = [10,7]. M = [3, 14]n'est pas une sortie acceptable car le dernier bin aura des 3éléments qui y contribueront mais le premier n'en aura que 2.

L = [1,1,1,1,1,1,1]et b = 3retourne M = [3,3,1].

En règle générale, votre code doit s'exécuter en temps linéaire.

Vous pouvez utiliser n'importe quelle langue ou bibliothèque que vous aimez et pouvez supposer que l'entrée est fournie de la manière qui vous convient.


Il s'avère que certaines entrées ne peuvent pas être résolues. Par exemple [1,1,1,1,1]et b=4. Votre code peut sortir ce qu'il veut pour ces entrées.


la source
6
Je pense que quelques cas de test supplémentaires seraient bien.
Jonathan Frech
5
your code must run in linear time- Je trouverais tout algorithme qui ne suit pas cela naturellement assez bizarre
Uriel
2
@Uriel Il n'y a pas de limite à la façon dont les réponses de code-golf peuvent être
4
@Lembik Bien qu'en quoi le fait de refuser de telles approches étranges potentielles est-il bénéfique pour un défi de code-golf?
Jonathan Frech
@JonathanFrech c'est juste aux préférences de l'OP :)

Réponses:

5

APL (Dyalog) , 19 octets

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

Essayez-le en ligne!

Nous ajoutons b zéros au tableau avant de le remodeler en parties égales de ⌈⍺÷⍨≢⍵( ⌈ longueur de L ÷ b ⌉ ) et de les additionner, comme illustré dans ,⍺⍴0, car toute quantité de taches vides (qui ne font pas partie du tableau d'origine) plus grande que b - 1 serait rempli d'au moins b - 1 éléments d'autres morceaux, ce qui fait que le point d'équilibrage du dernier groupe à b - 1 maximum diffère du reste. Nous utilisons b> b - 1 car il s'agit du code golf.

Par exemple, L avec 15 éléments et b = 3 ne serait pas groupé comme

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

mais plutôt comme (notez comment les 2 xs les plus à droite "remplissent" les zéros les plus à gauche)

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

tandis qu'un tableau de 16 éléments serait rempli de 2 ( 3 - 1 ) espaces vides, comme

x x x x x x
x x x x x x
x x x x 0 0
Uriel
la source
3

Python 2 , 65 octets

f=lambda l,n:n and[sum(l[:len(l)/n+1])]+f(l[len(l)/n+1:],n-1)or[]

Essayez-le en ligne!

totalement humain
la source
3

R , 75 71 70 63 octets

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

Essayez-le en ligne!

Ce tampon Lavec NAjusqu'à ce que la longueur soit un multiple de b, puis prend les sommes des colonnes Lcomme une matrice avec des bcolonnes, supprimant les NAvaleurs.

Expliquant comme un langage basé sur la pile:

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
la source
Très agréable et rapide! La montée du codeur R ...
2
@Lembik J'ai eu la chance d'être apparu sur TNB entre vous en disant "je vais poster ceci comme un défi" et vous l'avez affiché.
Giuseppe
1
Oh regardez "la longueur [<-" reviendra aussi comme notre copain préféré "[<-". Aucun octet enregistré pour moins de lisibilité:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@Vlo no bytes saved for less readabilityest probablement la devise du golf R ... bien que je suppose que sum(L|1)c'est un octet sauvé length(L)!
Giuseppe
3

MATL , 6 octets

vi3$es

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Pensez à l' entrée 4, à [0,3,7,2,5,1]titre d'exemple.

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
la source
1
C'est la réponse la plus impressionnante à mon avis.
3

Rubis , 54 53 octets

Un octet enregistré grâce à @Kirill L.

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

Essayez-le en ligne!

Réintégrer Monica - notmaynard
la source
Bien, vous pouvez également enregistrer un octet en le remplaçant [0]*bpar1..b
Kirill L.
@KirillL. Merci. Cela ne m'était même pas venu à l'esprit.
Rétablir Monica - notmaynard
2

C (gcc) , 107 octets

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

Essayez-le en ligne!

Jonathan Frech
la source
2

Haskell , 61 octets

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

Essayez-le en ligne!

totalement humain
la source
2
Ne semble pas fonctionner [1, 2, 3, 4, 5, 6] # 3.
nwellnhof
2

Java 10, 96 89 86 octets

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

Essayez-le en ligne ici .

J'ai trouvé un moyen plus court d'écrire i/(n/b+(n%b==0?0:1) ici: i/((n+b-1)/b)

Merci à Olivier Grégoire pour avoir joué au golf 3 octets.

Version non golfée:

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
la source
86 octets
Olivier Grégoire
@ OlivierGrégoire Merci!
OOBalance
1

Elixir , 98 octets

fn l,b->Enum.map Enum.chunk(l++List.duplicate(0,b-1),round Float.ceil length(l)/b),&Enum.sum/1 end

Essayez-le en ligne!

Le meilleur Elixir est de se diviser en parties d'une longueur de n . Et il ne peut pas très bien plafonner la division comme entier, donc nous faisons la division flottante, arrondissons-la. Malheureusement, la seule façon de le faire se traduit par un flottant, donc nous l'arrondissons à nouveau à un entier.

Okx
la source
Certaines de vos sorties ont une longueur incorrecte.
@Lembik l'a corrigé.
Okx
1

Perl 6 ,  52 51  50 octets

52 octets: testez-le

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

51 octets: testez-le

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

50 octets: essayez-le

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

47 octets non concurrents Testez-le

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

C'est non concurrentiel car il ».sumest permis de faire les calculs en parallèle. Il peut donc ou non être en temps linéaire.


Étendu:

{  # 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
la source
1

Fusain , 22 octets

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

Essayez-le en ligne!Le lien est vers la version détaillée du code. Explication:

Nθ

Contribution b .

Aη

Contribution L .

W﹪Lηθ⊞η⁰

Appuyez 0sur Ljusqu'à ce que Lla longueur de soit divisible parb .

E⪪η÷LηθIΣι

Divisez Lla longueur de bet divisez-la Len sections de cette longueur, puis additionnez chaque section et transformez-la en chaîne pour une sortie implicite sur des lignes distinctes.

Neil
la source
1

C (clang) , 58 octets

i;f(*L,l,b,*m){b=l/b+!!(l%b);for(i=0;i<l;m[i++/b]+=L[i]);}

Essayez-le en ligne!

f()prend les paramètres comme suit::
Lpointeur vers le tableau d'entrée
l: longueur du tableau d'entrée
b: nombre de cases
m: pointeur sur le tampon qui reçoit le nouveau tableau

Voici une version rentrante @ 60 octets:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}
GPS
la source
1

PHP, 88 octets

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

fonction anonyme, prend un tableau et un entier, retourne un tableau

Le potentiel de golf que cela avait été de remplacer ceil(count($a)/$b))avec (count($a)-1)/$b+1et abrégeant (count($a)-1)avec ~-count($a). Le flottant résultant est implicitement converti en entier dans l' array_chunkappel.

Essayez-le en ligne .

Titus
la source