Dropsort , zaprojektowany przez Davida Morgana-Mar, jest przykładem „algorytmu sortowania” w czasie liniowym, który tworzy listę, która jest faktycznie posortowana, ale zawiera tylko niektóre oryginalne elementy. Każdy element, który nie jest co najmniej tak duży, jak maksymalna liczba elementów poprzedzających, jest po prostu usuwany z listy i odrzucany.
W tym zadaniu otrzymasz listę liczb całkowitych jako danych wejściowych (argument STDIN lub funkcja, musisz obsługiwać co najmniej zakres liczb całkowitych ze znakiem 8-bitowym). Twoim zadaniem jest ich posortowanie, a następnie wyprowadzenie pozostałych elementów w zamówienie.
Możesz założyć, że lista nie jest pusta.
To jest golf golfowy, więc wygrywa najkrótszy program.
Przypadki testowe
Input Output
1 2 5 4 3 7 1 2 5 7
10 -1 12 10 12
-7 -8 -5 0 -1 1 -7 -5 0 1
9 8 7 6 5 9
10 13 17 21 10 13 17 21
10 10 10 9 10 10 10 10 10
Tabela liderów
var QUESTION_ID=61808,OVERRIDE_USER=39022;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
źródło
highest < current
? Czyhighest <= current
?highest (so far)<=current
.Odpowiedzi:
APL, 9 bajtów
Jest to monadyczny ciąg funkcji z diagramem:
Wersja nie-pociągowa to
Zasadniczo sprawdza, czy każdy element jest równy bieżącemu maksimum.
Zauważ, że rozwiązanie J Martina Büttnera jest tej samej długości i zostało opublikowane jako pierwsze.
źródło
J,
109 bajtówDziałająca wersja mojego pomysłu CJam (w mniejszej liczbie bajtów). Na przykład:
Wyjaśnienie
Najpierw otrzymujemy maksimum każdego prefiksu z:
(Tutaj
>.
jest operator maksymalny,/
składa ten operator na listę i\
pobiera wszystkie prefiksy danych wejściowych.)Następnie porównujemy początkową listę z tymi maksymami równości:
Na koniec wybieramy wszystkie elementy, dla których ta lista wyników boolowskich dała
1
:źródło
Haskell, 28
Anonimowa funkcja. Nazwij to jak
Odpowiednik rekurencji
Przetłumaczone iteracyjnie, iterujemy elementy i dla każdego z nich widzimy te mniejsze od reszty listy, nad którą iterujemy. Dzięki Antisthenes za bajt zapisany za pomocą
(x<)
.źródło
foldr(\x->(x:).filter(>=x))[]
, okazuje się, że ma taką samą długość.x:
zmusza cię do dodania operatora kropki. No cóż ...O(n^2)
. wiele niepotrzebnych porównań. ;-(Python 2, 49
źródło
max(a)
JavaScript (ES6), 29
Nadużywanie standardowej konwersji typu w javascript, tablica na liczbę:
źródło
Oktawa,
2719 bajtówźródło
Pyth, 12 bajtów
Sprawdź wszystkie przypadki testowe jednocześnie.
Jak to działa
źródło
Brachylog , 5 bajtów
Wypróbuj online!
Galaretka , 5 bajtów
Wypróbuj online!
Wyjaśnienie
Jest to rzadka sytuacja: mogę użyć algorytmu, którego (o ile mogłem stwierdzić za pomocą szybkiego przeglądu) nikt nie używa do tej pory, i jakoś kończy się na tej samej długości w dwóch bardzo różnych językach golfowych o bardzo różnej składni i wbudowane zestawy, z korespondencją 1 do 1 między programami (polecenia są nawet w tej samej kolejności!). Wydaje się więc, że bardziej sensowne jest łączenie ich - w pewnym sensie są to ten sam program i napisałem je w obu językach, aby zobaczyć, który był krótszy - niż osobne przesłanie ich.
Podstawową ideą jest to, że lista rozwijana listy jest jej podsekwencją z leksykograficznie maksymalnym rewersem. Co dziwne, ani Brachylog, ani Jelly nie mają wbudowanej funkcji pozwalającej znaleźć maksimum według konkretnej funkcji (Jelly ma wbudowaną funkcję, która zwraca wszystkie maksima przez określoną funkcję, ale to zwróciłoby listę singletonów zawierającą wynik, a nie sam wynik, i nie jest nawet krótszy niż robienie tego w ten sposób). Zamiast tego generujemy wszystkie możliwe podciągi, sortuj odwrotnie, bierz ostatnie.
Powodem, dla którego działa „maksymalne leksykograficzne odwrócenie” jest to, że wybrane wyjście musi się kończyć (a więc jego odwrócenie musi się zaczynać) od największej liczby na liście danych wejściowych (łatwo zauważyć, że wyjście droport zawsze się z tym kończy), a zatem może po tym nie zawierają niczego (ponieważ pobieranie podsekwencji zachowuje porządek). Powtórz indukcyjnie, a skończymy z definicją droportu.
źródło
Mathematica, 26 bajtów
źródło
DeleteDuplicates
, nie wygląda na to, by zwróciło{10, 10, 10, 10}
dane wejściowe{10, 10, 10, 9, 10}
DeleteDuplicates
dwa argumenty wydają się być prostym filtrem.R
29 2926 bajtówTworzy to obiekt funkcji, który akceptuje wektor
x
i zwracax
po usunięciu wszystkich elementów, które nie są tak duże, jak skumulowane maksimumx
.Zaoszczędź 3 bajty dzięki flodel!
źródło
K, 11 bajtów
W akcji:
źródło
{x@&~<':x}
jest bajt krótszy.3 4 2 2 5
.{x@&~<':x}/
, ale ta sama długość.Java, 82 bajty
Oto prosta pętla wyjściowa. Po prostu utrzymuje maksimum
m
i porównuje każdy element.źródło
a->{int m=a[0]...
Perl, 33 bajty
32 bajtowy kod +
-p
Jeśli na wyjściu dopuszczalne są dodatkowe spacje, można usunąć 31 bajtów, usuwając
i
?
. Akceptuje ciąg (lub liczbę oddzielonych znaków nowej linii) poprzezSTDIN
:źródło
Python 3, 67
Dość brutalna siła. Zmieniłem to na funkcję, ponieważ brakowało mi, że była to poprawna odpowiedź.
Wersja bez golfa:
źródło
Haskell,
3837 bajtówZaoszczędzono 1 bajt dzięki JArkinstall .
źródło
$
aby zmniejszyć o jeden cały bajt!f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s
(C # -
6864 lub132127 znakówWhere
w tym przypadku iteruje po liście i dla każdego elementuv
w indeksiei
na liście ocenia wyrażenie boolowskie. Jeśli wyrażenie ma wartość true, element jest dodawany do wyniku. Jedyną prawdziwą sztuczką dla wyrażenia boolowskiego jest to, że zwarcia C # lub ocena, gdy tylko warunek zostanie spełniony. Zapobiega toIndexOutOfRangeException
wyjątkowi i utrzymuje pierwszy element na liście.Jeśli dane wejściowe i wyjściowe muszą być łańcuchami (nie mogłem tego stwierdzić na pewno, więc zostawię to OP i reszcie z was do podjęcia decyzji).
Trochę dekompresji daje:
W tym przypadku drugi wiersz funkcji używa dokładnie takiej samej logiki jak powyżej. W
Select
chwyta elementy listy i konwertuje je doint
. WywołanieToList
1 zmusza selekcję do oceny i zamienia jąvar
wList<int>
czas kompilacji, dzięki czemuWhere
operuje ona na zbiorze liczb całkowitych.Wypróbuj na C # Pad
Dzięki VisualMelon za pomoc w przycięciu odpowiednio 4 bajtów i 5 bajtów. :)
1 lista tutu?
źródło
int[]f(int[]b)
, ai<1
zamiast tego możesz niecoi==0
skrócić tę kontrolę. W przypadku wersji łańcuchowej możesz również upuścić nawiasy wokół pojedynczego argumentu w lambda (np.(d)=>int.Parse(d)
Może byćd=>int.Parse(d)
. Liczę również tylko 67 bajtów, a nie 68, w twoimCJam, 15 bajtów
Wypróbuj online w interpretatorze CJam .
Jak to działa
źródło
PowerShell , 32 bajty
Wypróbuj online!
Mniej golfa:
źródło
C: 73 bajty
lub
C: 49 bajtów
(Jeśli nagłówek celny przeznaczony na zawody codegolf jest dozwolone)
Nadal nie mogę pokonać CJam, ale przynajmniej pozwala to pokonać kilka innych języków.
źródło
Burleska, 13 bajtów
11 bajtowe rozwiązanie, które przechodzi przypadki testowe:
Spróbuj online tutaj .
Wyjaśnienie:
Jednak ta wersja działa tylko przy użyciu faktu, że nie ma dwóch mniejszych liczb między dwiema liczbami. W przeciwnym razie użyj poniższej wersji (13B):
Starsza wersja:
Spróbuj online tutaj. Wyjaśnienie:
Jeśli upuścisz równe liczby, możesz
.>
użyć zamiast zamiastcm
. Ponadto, jeśli listy zawierają tylko liczby dodatnie, możesz użyć jednego z nich0
lub-1
zamiast nichJ-]
.źródło
Minkolang 0,9 , 18 bajtów
Wypróbuj tutaj.
Wyjaśnienie
źródło
Ruby,
4137 znakówPrzykładowy przebieg:
źródło
-[p]
jest krótszy niż.compact
NARS2000 APL, 13 bajtów
NARS2000 to darmowy interpreter APL dla Windows; zawiera funkcje wielosektowe dostępne dla
⍦
operatora.Jest to monadyczny rozwidlenie, które przyjmuje przecięcie wielosetowe (
⍦∩
) z input (+
) * i listę działających maksimów (⌈\
).Ponieważ
⍦
nie jest standardowym znakiem APL w jednobajtowym starszym kodowaniu APL, musimy użyć UTF-8, dzięki czemu⍦∩⌈
znaki będą miały po trzy bajty. Wybrałem+
zamiast⊢
zapisać dwa bajty.NARS2000 obsługuje widelce, które mogą być wbudowane w pociągi bez nawiasów, ale w przeciwieństwie do Dyaloga nie pozwala na przypisanie funkcji bez zawijania funkcji w nawiasach.
*
+
jest technicznie skomplikowanym sprzężonym, ale dane wejściowe są prawdziwe.źródło
> <> z flagą -v,
3631 + 2 = 33 bajtyWpisz listę na stos za pomocą opcji -v, tak aby pierwszy element listy znalazł się na górze stosu. Spowoduje to wydrukowanie listy porzuconej ze spacją końcową.
Testowe uruchomienie :
Edycja: zapisano 5 bajtów dzięki Fongoid
źródło
:&\o" "&n:~& <
i wiersz 2 jako~ >l?!;:&:&(?!^
Python,
1029994 +56 nowych wierszy nieobjętych plikiem =107105100 bajtów(Użyłem tabulatorów do wcięcia)
Nie najlepsze tam, ale to moja pierwsza szansa na kod golfa. Nie udało mi się znaleźć sposobu na posortowanie listy bez wprowadzania błędów związanych z usuwaniem, więc przeniosłem uporządkowane elementy na listę tymczasową.
EDYCJA: list.append () jest krótszy niż robienie tego w brzydki sposób
r + = [i] był krótszy niż list.append (); dzięki njzk2 !
źródło
Scala:
232126120 bajtówźródło
List[Int]
nie spełnia wymagań, powinieneś otrzymać dane wejściowe przez STDIN lub jako argument. Dodatkowo przesadza z odpowiedzią ... Dlaczego po prostu nie maszdef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 bajty
Nie golfowany:
źródło
Tiny Lisp, 107 bajtów
( Język ten został opublikowany dopiero po tym pytaniu, więc ta odpowiedź zabraknie konkurencji. Nie żeby to miało jakiekolwiek szanse na wygraną. Język później ewoluowała dalej mieć więcej buildins niż te, które użyłem tutaj, ale ja zostaję z wersja, którą pierwotnie zaimplementowałem w 2015 roku. Ta odpowiedź nadal działa z nowszym oficjalnym tłumaczem , choć daje pewne ostrzeżenia, ponieważ definiuję parametr, który przesłania cień nowej wersji (do dodania). Dzięki DLosc dla łącza TIO. )
a
a
(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))
Definiuje to funkcję
ds
(i jej rekurencyjną funkcję pomocnicząr
), która sortuje argument, który musi być listą liczb całkowitych.r
nie jest funkcją rekurencyjną, więc w przypadku bardzo długich list może to spowodować przepełnienie stosu.Nie golfowany:
Oto kilka przykładów, jak tego użyć (z przypadkami testowymi z pytania):
(Tak,
-7
nie jest literałem całkowitoliczbowym, więc musimy zdefiniować funkcję do ich reprezentowania.) Wynik:źródło
r
, jak sądzę ..)ds
? Myślę, że można to zrobić, zaoszczędziłby kolejny bajt. Wydaje mi się, że wybrałemds
jako skrót do sortowania upuszczonego.(d ds
i dopasowując)
na końcu. Inne pola golfowe są możliwe, jeśli chcesz skorzystać z mojego obecnego tłumacza , ale jeśli chcesz trzymać się specyfikacji w pierwotnym pytaniu, to też jest w porządku. :)Galaretka, 5 bajtów
Pamiętaj, że wyzwanie poprzedza stworzenie Galaretki.
Wypróbuj online!
Jak to działa
źródło
Mathematica, 27 bajtów
źródło