Wyzwanie
Biorąc pod uwagę niepustą tablicę liczb całkowitych, np .:
[5, 2, 7, 6, 4, 1, 3]
Najpierw podziel ją na tablice, w których żaden element nie jest większy niż poprzedni (tj. Tablice nie rosnąco):
[5, 2] [7, 6, 4, 1] [3]
Następnie odwróć każdą tablicę:
[2, 5] [1, 4, 6, 7] [3]
Na koniec połącz je wszystkie razem:
[2, 5, 1, 4, 6, 7, 3]
To powinno być to, co zwraca program / funkcja. Powtórz tę procedurę wystarczająco dużo razy, a tablica zostanie w pełni posortowana.
Zasady
- Dane wejściowe i wyjściowe mogą być podawane dowolnymi standardowymi metodami i mogą mieć dowolny rozsądny format macierzowy.
- Tablica wejściowa nigdy nie będzie pusta, ale może zawierać negatywy i / lub duplikaty.
- Wartość bezwzględna każdej liczby całkowitej będzie zawsze mniejsza niż 2 31 .
Przypadki testowe
Mam nadzieję, że obejmują one wszystkie przypadki krawędzi:
[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]
Punktacja
To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.
code-golf
array-manipulation
sorting
ETHprodukcje
źródło
źródło
O(n^2)
O(n)
. zamień pierwszy i ostatni element, a następnie zamień drugi i drugi ostatni element itp., kiedy dojdziesz do środkowego przystanku.O(n)
, ale cofanie może być wbudowane w algorytm (tak robi moja odpowiedź JS); ponieważ każda iteracja zapętla się raz nad każdym elementem w tablicy, pojedyncza iteracja toO(n)
. (Myślę, że ...)Odpowiedzi:
JavaScript (ES6), 64 bajty
Rekursja FTW! Podstawowym wykorzystywanym tutaj algorytmem jest śledzenie bieżącego nie rosnącego przebiegu w tablicy, „zwracanie” go za każdym razem, gdy zostanie znaleziony element rosnący. Robimy to rekurencyjnie, ciągle łącząc wyniki, dopóki nie zabraknie przedmiotów. Tworząc każdy przebieg w odwrotnej kolejności (
[n,...z]
zamiast[...z,n]
), możemy uniknąć długiego.reverse()
bez żadnych kosztów.Testowy fragment kodu
Pokaż fragment kodu
źródło
[n,...a]
. Co to jestn
? Czy to tylko pierwszy element w twojej tablicy?n
jest pierwszym elementem w tablicy ia
jest resztą tablicy. Więcej informacji znajdziesz tutaj ....a
? Czy to tylko po to, abyś mógł z tego skorzystaćn
? Jeszcze jedna rzecz, kiedy dzwoniszf(a,q)
, czyq
ustawiony jest parametrz
?f=([n])=>...
przechwyciłby tylko pierwszy element if=([n,a])=>...
przechwyciłby tylko pierwszyn
i drugia
. Innym sposobem na zrobienie tego, cof=([n,...a])=>,,,
by byłof=a=>(n=a.unshift(),...
.z
jest to drugi parametr w funkcji, gdyf(a,q)
jest wywoływany,f
widzi go jakoz
. Mam nadzieję że to pomoże!Python 3 , 63 bajty
Wypróbuj online!
źródło
Galaretka , 8 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
JavaScript (ES6), 70 bajtów
Jasne, jest to już pokonane przez odpowiedź ETHproductions , ale to najlepsze, co mogłem wymyślić do tej pory bez korzystania z rekurencji.
Uwaga: Inicjowanie obu
r
io
dokładnie tego samego obiektu za pomocąr = o = []
może wyglądać jak niebezpieczny pomysł. Ale jest to bezpieczne, ponieważr
jest to natychmiast przypisywane do własnej instancji (zawierającej pierwszy elementa
) przy pierwszej iteracji zr = [n, ...r]
.Przypadki testowe
Pokaż fragment kodu
źródło
MATL , 15 bajtów
Dane wejściowe to wektor kolumny o formacie
[5; 2; 7; 6; 4; 1; 3]
(średnik jest separatorem wierszy).Wypróbuj online!
Weź
[5; 2; 7; 6; 4; 1; 3]
przykład jako przykład.Wyjaśnienie
źródło
Mathematica,
3027 bajtów3 bajty zapisane z powodu @Martin Ender .
Funkcja anonimowa. Pobiera listę liczb jako dane wejściowe i zwraca listę liczb jako dane wyjściowe.
źródło
Python 2, 100 bajtów
Naprawdę okropny golf, ale chciałem opublikować moje rozwiązanie (jeden nie jest po prostu lepszy niż Dennis) ...
Testuj na repl.it!
Dane wejściowe należy podać jako literał listy w języku Python, na przykład
[5, 3, 4, 2, 6, 1]
.Podstawową ideą jest częste wykorzystanie składni krojenia Pythona, wycinanie każdej potrzebnej sekcji z tablicy, odwracanie jej i dodawanie do nowej tablicy.
źródło
d,L,x=input(),[],0;d+=...
.Pyke,
118 bajtów ( stara wersja )Wypróbuj tutaj! (działa na najnowszej wersji)
źródło
Siatkówka , 163 bajty
Tak, wiem jakie to okropne. Wspieranie zer i negatywy było bardzo zabawne. Liczba bajtów zakłada kodowanie ISO 8859-1.
Wypróbuj online
Wyjaśnienie:
źródło
05AB1E ,
19181614 bajtówZaoszczędzono 2 bajty, używając sztuczki sortowania Luisa Mendo
Wypróbuj online!
Wyjaśnienie
Przykładowe dane wejściowe
[5, 2, 7, 6, 4, 1, 3]
Poprzednie 16-bajtowe rozwiązanie
źródło
JavaScript (ECMA 6),
121128125119108 bajtówWyrażenie lambda pobiera pojedynczy
Array
parametra
.Dzięki @ETHproductions za pomoc w zobaczeniu mojego pierwszego błędu.
źródło
return(b+","+c).split`,`
aby zaoszczędzić kilka bajtów na końcu.c.unshift
zamiastc.push
usuwać potrzebę cofaniac
. Po zrobieniu tego mam 94 bajty .Rubinowy,
6055 bajtówPrawie o to prosiło wyzwanie. I określonych lambda
s
, które ma szeregx
i Sever (plastry), to na mniejsze kawałki, gdy następny element będzie większy niż. Daje to moduł wyliczający, który możemy nazywać mapą i odwracać kolejność elementów, zanim ostatecznie zbierzemy wszystko razem z spłaszczeniem, które łączy elementy w określonej kolejności w jedną tablicę.Testy
źródło
Brachylog , 10 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
c
, gdy działa w odwrotnej kolejności, koniecznie najpierw próbuje podzielić na mniejszą liczbę list?Dyalog APL ,
715 bajtówWymaga
⎕ML←3
, co jest domyślne w wielu systemach. *∊
zaciągnąć się (spłaszczyć)⌽¨
każdy odwrócony⍵⊂⍨
argument podzielony na partycje * poprzez wycięcie, gdzie każdy odpowiadający element jest większy niż jego poprzednik1+
jeden plus⍵-
argument minus⌊/⍵
najmniejszy element argumentuStare 7-bajtowe rozwiązanie kończy się niepowodzeniem z nieujemnymi liczbami całkowitymi:
Wymaga
⎕ML←3
, co jest domyślne w wielu systemach. *∊
zaciągnij (spłaszcz)⌽¨
każdy odwrócony⊂⍨
dzielony na części ** Partition (
⊂
) jest funkcją, która odcina swój prawy argument, gdy odpowiadający mu lewy argument jest większy niż poprzedni. (Niestety akceptuje tylko nieujemne liczby całkowite, a zero ma specjalne znaczenie.) Od wersji 16 ta funkcja⊂
jest dostępna we wszystkich systemach (nawet tych, gdzie⎕ML≠3
), za pomocą glifu⊆
.źródło
Haskell, 49 bajtów
Przykład użycia:
(%[]) [5,2,7,6,4,1,3]
->[2,5,1,4,6,7,3]
.Podejście rekurencyjne. Funkcja
%
przyjmuje listę wejść jako swój pierwszy parametr i akumulator,l
który śledzi dotychczas nie rosnącą porcję (w odwrotnej kolejności). Przypadek podstawowy jest osiągany, gdy lista wejść jest pusta, a wynikiem jest akumulator. Jeśli lista wejściowa nie jest pusta, a pierwszy elementa
nie mieści się w bieżącej porcji (any(<a)l
), zwróć akumulator i dołącz rekurencyjne wywołanie do reszty listy oraza
jako nowego akumulatora (l++b%[a]
). W przeciwnym razie wykonaj rekurencyjne wywołanie na pozostałej części listy ia
dołącz do tha accumulator (b%(a:l)
). Główna funkcja(%[])
wywołuje%
z pustym akumulatorem.źródło
Siatkówka , 98 bajtów
Liczba bajtów zakłada kodowanie ISO 8859-1.
Wypróbuj online!
źródło
R, 64 bajty
Odczytuje dane wejściowe ze standardowego wejścia. Podzieliliśmy dane wejściowe na listę wektorów,
split()
która wymaga zmiennej czynnikowej grupującej dane wejściowe. Współczynnik jest tworzony przez przyjęcie skumulowanej sumy wektora logicznego, dla którego różnica jest dodatnia.Rozważ wektor:
Teraz wzięcie różnicy i kontynuowanie
F
przez uruchomieniey=c(F,diff(x)>0)
wygenerowałoby następujący logiczny wektor:Biorąc sumę skumulowaną,
cumsum(y)
powstaje wektor, w którym każda grupa jest reprezentowana przez unikalny czynnik, na podstawie którego możemy łączyć się zsplit
funkcją:źródło
diffinv
zamiastcumsum
.Oktawa,
7544 bajtówNa podstawie odpowiedzi MATL @LuisMendo
Wypróbuj online!
Poprzednia odpowiedź
Wypróbuj online!
odwróć tablicę
weź pierwszą różnicę
f
znajdź pozycję, w której następny element jest mniejszy niż poprzedni element
pierwsza różnica pozycji zwraca długość każdej podtablicy
użyj długości każdej podtablicy,
mat2cell
aby podzielić tablicę na zagnieżdżoną listę tablicodwróć listę zagnieżdżoną
spłaszcz listę zagnieżdżoną
źródło
Pyth - 15 bajtów
Wypróbuj online tutaj .
źródło
Perl 6 , 59 bajtów
Rozwiązanie oparte na regeksie.
Ponieważ to jest
SpartaPerl !!m/ /
: Zmodyfikuj tablicę wejściową i dopasuj do niej wyrażenie regularne.(\-? \d+)
: Dopasuj liczbę i przechwyć jako$0
.<?{ [>=] $0 }>
: Asercja o zerowej szerokości, która pasuje tylko wtedy, gdy wszystkie$0
wychwycone do tej pory w bieżącym podpasowaniu są w kolejności rosnącej.([ ] +)+
: Powtarzaj dwa ostatnie kroki tak często, jak to możliwe, w przeciwnym razie rozpocznij nowy mecz podrzędny.map , [0]
: Powtarzaj pod-mecze.|+«*.[0].reverse
: Dla każdego z nich weź listę dopasowanych wartości$0
, odwróć ją, wymuś wartości na liczby (+«
) i wsuń je na zewnętrzną listę (|
).Perl 6 , 63 bajtów
Rozwiązanie do przetwarzania listy rekurencyjnej.
Bardziej pracochłonny, niż się spodziewałem.
Mimo że język ma wiele wygodnych wbudowanych funkcji, wydaje się, że nie ma żadnego partycjonowania list (np. Ruby
slice_when
lub HaskelltakeWhile
).źródło
Skumulowane , niekonkurencyjne, 34 bajty
Ciągle rozwijam ten język.
Argument dotyczy TOS. Wypróbuj tutaj!
chunkby
przejmuje funkcję i zbiera tablice ciągłych danych, które spełniają tę funkcję. Funkcja to:Daje to ściśle malejącą tablicę.
$revmap
jest w zasadzie[rev]map
i odwraca każdy element.flat
w końcu spłaszcza tablicę.Trochę zabawy podczas sortowania tablicy:
Dane wyjściowe (na przykład):
źródło
Python,
151139 bajtówZapisano 12 bajtów dzięki @ Flp.Tkc!
Nigdzie w pobliżu @ Flp.Tkc, a co dopiero ...
źródło
+= data,
końcowego przecinka pośrednio tworzy krotkę, która jest następnie łączona z listą, dodając dane jako ostatni element na liście. W tym kontekście wykonajr+=l[i:j+1][::-1],
Python 2, 74 bajty
Wejście
a
, wyjściec
źródło
Python 3, 191 bajtów
Nie jestem pewien, czy używanie
sorted
funkcji sprawdzania jest tutaj dozwolone, ale nie mogłem wymyślić żadnego dobrego powodu, aby obniżyć moją liczbę bajtów o ~ 30 bajtów.źródło
Clojure, 105 bajtów
Partycji w parach o kolejnych numerach, wkłada
true
lubfalse
między nimi, partycjenot
dotrue
i numery staćfalse
ifalse
true
odwraca partycje i zachowuje wartości liczbowych.źródło