Umieść tablicę w pojemnikach

12

W tym prostym wyzwaniu otrzymujesz tablicę wejściową Lnieujemnych liczb całkowitych i liczbę przedziałów bwiększą niż 0, ale nie większą niż długość L. Twój kod musi zwrócić nową tablicę, Mktórej długość jest równa bi która podzieliła tablicę L. Najłatwiej to wyjaśnić przykładami.

L = [1,0,5,1]i b = 2wraca M = [1,6].

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

Do tej pory takie proste. Jednak w tym pytaniu bniekoniecznie trzeba dzielić len(L). W tym przypadku ostatni pojemnik będzie miał po prostu mniej liczb, aby go uzupełnić.

Każdy koszyk, z wyjątkiem ewentualnie ostatniego, musi mieć taką samą liczbę liczb, która przyczynia się do jego sumy. Ostatni pojemnik nie może zawierać więcej numerów niż inne pojemniki. Ostatni pojemnik musi mieć możliwie jak najwięcej liczb, z zastrzeżeniem innych zasad.

L = [0,3,7,2,5,1]i b = 4wraca M = [3,9,6,0]. M = [10,8,0,0]nie jest akceptowalnym wyjściem, ponieważ trzeci przedział nie ma nazwy liczb, które się do niego przyczyniły, jako pojemników 1i 2.

L = [0,3,7,2,5]i b = 2wraca M = [10,7]. M = [3, 14]nie jest akceptowalnym wyjściem, ponieważ ostatni bin będzie miał 3do tego elementy, ale tylko pierwszy 2.

L = [1,1,1,1,1,1,1]i b = 3wraca M = [3,3,1].

Zgodnie z ostatnią zasadą kod musi działać w czasie liniowym.

Możesz użyć dowolnego języka lub bibliotek, które ci się podobają, i możesz założyć, że dane wejściowe zostały podane w dowolny dogodny dla Ciebie sposób.


Okazuje się, że są pewne dane wejściowe, których nie można rozwiązać. Na przykład [1,1,1,1,1]i b=4. Twój kod może wyświetlać, co chce dla tych danych wejściowych.


źródło
6
Myślę, że kilka innych przypadków testowych byłoby fajnych.
Jonathan Frech
5
your code must run in linear time- Znalazłbym każdy algorytm, który nie podąża za tym z natury dość dziwnym
Uriel
2
@Uriel Nie ma ograniczeń co do dziwnych odpowiedzi na gry w golfa :)
4
@Lembik Chociaż w jaki sposób niedopuszczenie takich potencjalnych dziwnych podejść jest korzystne dla wyzwania golfowego?
Jonathan Frech
@JonathanFrech to tylko preferencje OP :)

Odpowiedzi:

5

APL (Dyalog) , 19 bajtów

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

Wypróbuj online!

Dodajemy b zera do tablicy przed przekształcając je na równe części ⌈⍺÷⍨≢⍵( ⌈ długość L ÷ b ⌉ ) i ich sumowanie, jak przedstawiono na ,⍺⍴0to, że każdy ilości plamek (które nie są częścią oryginalnej tablicy) większe niż b - 1 byłby wypełniony co najmniej b - 1 elementami z innych fragmentów, co powoduje, że punkt równowagi ostatniej grupy wynosi maksymalnie b - 1 różnica od reszty. Używamy b> b - 1, ponieważ jest to kod golfowy.

Na przykład L z 15 elementami ib = 3 nie będą grupowane jako

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

ale raczej jako (zwróć uwagę, jak dwie xskrajne po prawej stronie 2 s „wypełniają” skrajne lewe zera)

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

podczas gdy tablica 16 elementów byłaby wypełniona 2 ( 3 - 1 ) pustymi miejscami, np

x x x x x x
x x x x x x
x x x x 0 0
Uriel
źródło
3

Python 2 , 65 bajtów

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

Wypróbuj online!

całkowicie ludzki
źródło
3

R , 75 71 70 63 bajtów

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

Wypróbuj online!

To klocki Lz NAdopóki długość jest wielokrotnością b, a następnie wykonuje się z sumy kolumny Ljako matryca z bkolumny, usuwanie NAwartości.

Wyjaśnienie jako języka opartego na stosie:

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
źródło
Bardzo miło i szybko! Powstanie kodera R ...
2
@Lembik Miałem szczęście, że wpadłem do TNB między tobą i powiedziałem: „Zamierzam opublikować to jako wyzwanie”, a ty faktycznie to publikujesz.
Giuseppe
1
Och, spójrz „długość [<-” też powróci tak jak nasz ulubiony kolega „[<-”. Brak zapisanych bajtów dla mniejszej czytelności:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@ Vlo no bytes saved for less readabilityjest prawdopodobnie motto R golfa ... chociaż przypuszczam, że sum(L|1)jest to bajt uratowany length(L)!
Giuseppe
3

MATL , 6 bajtów

vi3$es

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Rozważyć wejście 4, [0,3,7,2,5,1]jako przykład.

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
źródło
1
To najbardziej imponująca odpowiedź według mnie.
3

Rubin , 54 53 bajtów

Zapisano bajt dzięki @Kirill L.

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

Wypróbuj online!

Przywróć Monikę - notmaynard
źródło
Ładny, można również zapisać bajt zastępując [0]*bprzez1..b
Kirill L.
@KirillL. Dzięki. Nawet nie przyszło mi do głowy.
Przywróć Monikę - notmaynard
2

C (gcc) , 107 bajtów

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

Wypróbuj online!

Jonathan Frech
źródło
2

Haskell , 61 bajtów

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

Wypróbuj online!

całkowicie ludzki
źródło
2
Wydaje się, że nie działa [1, 2, 3, 4, 5, 6] # 3.
nwellnhof
2

Java 10, 96 89 86 bajtów

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

Wypróbuj online tutaj .

Znalazłem krótszy sposób na napisanie i/(n/b+(n%b==0?0:1) tutaj: i/((n+b-1)/b)

Dzięki Olivier Grégoire za grę w golfa 3 bajty.

Wersja bez golfa:

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
źródło
86 bajtów
Olivier Grégoire
@ OlivierGrégoire Thanks!
OOBalance
1

Eliksir , 98 bajtów

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

Wypróbuj online!

Najlepszy eliksir ma podział na części o długości n . I nie może dobrze pułapować podziału jako liczby całkowitej, więc dzielenie zmiennoprzecinkowe, zaokrąglanie w górę. Niestety jedynym sposobem na zrobienie tego jest liczba zmiennoprzecinkowa, więc zaokrąglamy to ponownie do liczby całkowitej.

Okx
źródło
Niektóre z twoich wyników mają niewłaściwą długość.
@Lembik naprawił to.
Okx
1

Perl 6 ,  52 51  50 bajtów

52 bajty: przetestuj

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

51 bajtów: przetestuj

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

50 bajtów: spróbuj

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

47 bajtów niekonkurencyjnych Przetestuj

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

Jest niekonkurencyjny, ponieważ ».summożna wykonywać obliczenia równolegle. Więc może, ale nie musi, być w czasie liniowym.


Rozszerzony:

{  # 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
źródło
1

Węgiel , 22 bajty

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Nθ

Wejście b.

Aη

Wejście L.

W﹪Lηθ⊞η⁰

Przekaż 0do Lmomentu L„s długość jest podzielna przez b.

E⪪η÷LηθIΣι

Podziel Ldługość przez bi podziel Lna sekcje o tej długości, a następnie zsumuj każdą sekcję i rzutuj na łańcuch, aby uzyskać niejawne dane wyjściowe w osobnych wierszach.

Neil
źródło
1

C (clang) , 58 bajtów

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

Wypróbuj online!

f()przyjmuje parametry w następujący sposób::
Lwskaźnik do tablicy wejściowej
l: długość tablicy wejściowej
b: liczba pojemników
m: wskaźnik do bufora, który otrzymuje nową tablicę

Poniżej znajduje się wersja dla początkujących @ 60 bajtów:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}
GPS
źródło
1

PHP, 88 bajtów

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

funkcja anonimowa, przyjmuje tablicę i liczbę całkowitą, zwraca tablicę

Jedynym golfa miał potencjał ten został wymianie ceil(count($a)/$b))z (count($a)-1)/$b+1i skracania (count($a)-1)się ~-count($a). Wynikowa liczba zmiennoprzecinkowa jest domyślnie rzutowana na liczbę całkowitą warray_chunk wywołaniu.

Wypróbuj online .

Tytus
źródło