W tym prostym wyzwaniu otrzymujesz tablicę wejściową L
nieujemnych liczb całkowitych i liczbę przedziałów b
większą niż 0, ale nie większą niż długość L
. Twój kod musi zwrócić nową tablicę, M
której długość jest równa b
i która podzieliła tablicę L
. Najłatwiej to wyjaśnić przykładami.
L = [1,0,5,1]
i b = 2
wraca M = [1,6]
.
L = [0,3,7,2,5,1]
i b = 3
wraca M = [3,9,6]
.
Do tej pory takie proste. Jednak w tym pytaniu b
niekoniecznie 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 = 4
wraca 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 1
i 2
.
L = [0,3,7,2,5]
i b = 2
wraca M = [10,7]
. M = [3, 14]
nie jest akceptowalnym wyjściem, ponieważ ostatni bin będzie miał 3
do tego elementy, ale tylko pierwszy 2
.
L = [1,1,1,1,1,1,1]
i b = 3
wraca 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.
your code must run in linear time
- Znalazłbym każdy algorytm, który nie podąża za tym z natury dość dziwnymOdpowiedzi:
APL (Dyalog) , 19 bajtów
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,⍺⍴0
to, ż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
ale raczej jako (zwróć uwagę, jak dwie
x
skrajne po prawej stronie 2 s „wypełniają” skrajne lewe zera)podczas gdy tablica 16 elementów byłaby wypełniona 2 ( 3 - 1 ) pustymi miejscami, np
źródło
Python 2 , 65 bajtów
Wypróbuj online!
źródło
R ,
75717063 bajtówWypróbuj online!
To klocki
L
zNA
dopóki długość jest wielokrotnościąb
, a następnie wykonuje się z sumy kolumnyL
jako matryca zb
kolumny, usuwanieNA
wartości.Wyjaśnienie jako języka opartego na stosie:
źródło
function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
no bytes saved for less readability
jest prawdopodobnie motto R golfa ... chociaż przypuszczam, żesum(L|1)
jest to bajt uratowanylength(L)
!MATL , 6 bajtów
Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
Rozważyć wejście
4
,[0,3,7,2,5,1]
jako przykład.źródło
Rubin ,
5453 bajtówZapisano bajt dzięki @Kirill L.
Wypróbuj online!
źródło
[0]*b
przez1..b
C (gcc) , 107 bajtów
Wypróbuj online!
źródło
Haskell , 61 bajtów
Wypróbuj online!
źródło
[1, 2, 3, 4, 5, 6] # 3
.Java 10,
968986 bajtówWypró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:
źródło
Eliksir , 98 bajtów
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.
źródło
Perl 6 ,
52 5150 bajtów52 bajty: przetestuj
51 bajtów: przetestuj
50 bajtów: spróbuj
47 bajtów niekonkurencyjnych Przetestuj
Jest niekonkurencyjny, ponieważ
».sum
można wykonywać obliczenia równolegle. Więc może, ale nie musi, być w czasie liniowym.Rozszerzony:
źródło
Węgiel , 22 bajty
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Wejście
b
.Wejście
L
.Przekaż
0
doL
momentuL
„s długość jest podzielna przezb
.Podziel
L
długość przezb
i podzielL
na 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.źródło
JavaScript (Node.js) , 71 bajtów
Wypróbuj online!
źródło
C (clang) , 58 bajtów
Wypróbuj online!
f()
przyjmuje parametry w następujący sposób::L
wskaźnik do tablicy wejściowejl
: długość tablicy wejściowejb
: liczba pojemnikówm
: wskaźnik do bufora, który otrzymuje nową tablicęPoniżej znajduje się wersja dla początkujących @ 60 bajtów:
źródło
PHP, 88 bajtów
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+1
i 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 .
źródło