Sortowanie stratne (Implement Dropsort)

61

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>

SuperJedi224
źródło
1
Czy czek highest < current? Czy highest <= current?
Morgan Thrapp,
7
Zachowaj bieżący element if highest (so far)<=current.
SuperJedi224,
Czy możemy założyć, że na liście będzie co najmniej jeden element?
lirtosiast
@ThomasKwa: Tak.
SuperJedi224,
19
Zwiększona wydajność Dropsorts może zaoszczędzić firmie dużo pieniędzy, jeśli zostanie wykorzystana w systemie płac.
PyRulez

Odpowiedzi:

42

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.

lirtosiast
źródło
41
Punkty bonusowe, ponieważ wyglądają uroczo.
Sammitch,
22
Code wygląda jak niezadowolony koleś strzelający do klapy kota
slebetman
2
Nie wiem zbyt wiele na temat liczenia bajtów i tego, jakie kodowanie ma być użyte, ale według mothereff.in/byte-counter i meta.codegolf.stackexchange.com/questions/4944/... to 17 bajtów i bajtówizematters. com to 13.
DLeh
3
@DLeh To jest w UTF-8. APL ma własne starsze kodowanie, które wynosi 1 bajt na znak APL, zanim istniał Unicode.
isaacg
3
@DLeh bytesizematters wykorzystuje skompilowany algorytm do zliczania bajtów, który nie odpowiada (i nie może ) faktycznemu kodowaniu.
Dennis
21

J, 10 9 bajtów

#~(=>./\)

Działająca wersja mojego pomysłu CJam (w mniejszej liczbie bajtów). Na przykład:

   f =: #~(=>./\)
   f 10 10 10 9 10
10 10 10 10
   f 1 2 5 4 3 7
1 2 5 7

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:

#~(=>./\)
Martin Ender
źródło
16

Haskell, 28

foldr(\x l->x:filter(x<)l)[] 

Anonimowa funkcja. Nazwij to jak

foldr(\x l->x:filter(x<)l)[] [-7, -8, -5, 0, -1, 1] 
[-7,-5,0,1]

Odpowiednik rekurencji

f[]=[]
f(x:l)=x:filter(x<)(f l)

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<).

xnor
źródło
Dlaczego nie curry lambda? Powinny ocalić kilka znaków ...
MathematicalOrchid
@MathematicalOrchid Jeśli masz na myśli foldr(\x->(x:).filter(>=x))[], okazuje się, że ma taką samą długość.
xnor
Ach Właśnie zobaczyłem filtr na końcu i pomyślałem „hej, możesz to curry!” Nie przyszło mi do głowy, że x:zmusza cię do dodania operatora kropki. No cóż ...
MathematicalOrchid
1
tak jest O(n^2). wiele niepotrzebnych porównań. ;-(
dumny haskeller
Dlaczego nie zmienić (> = x) na (x <)? Zaoszczędzi 1 bajt
Antisthenes
10

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
feersum
źródło
1
To jest niesamowite.
Morgan Thrapp,
1
@ThomasKwa Problem polega na tym, jak zatrzymać rekurencyjne połączenia. Potrzebujesz pustej skrzynki, nawet jeśli dane wejściowe ją wykluczają.
Bakuriu
Problem w tym, że nie jest liniowy z powodumax(a)
njzk2
1
@ njzk2 Wyzwanie nie wymaga, aby implementacje działały w czasie liniowym.
feersum
3
@ njzk2 Ładne kody kończą się na końcu!
feersum
10

JavaScript (ES6), 29

Nadużywanie standardowej konwersji typu w javascript, tablica na liczbę:

  • tablica zawierająca tylko 1 liczbę => ta liczba
  • jakakolwiek inna tablica => NaN

d=l=>l.filter(v=>l>v?0:[l=v])

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
  [[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]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],              
  console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)
<pre id=O></pre>

edc65
źródło
Łał. Myślałem, że 38 bajtów jest w przybliżeniu najlepszym możliwym; najwyraźniej bardzo się myliłem. +1
ETHprodukcje
Testy oparte na stole. Miły!
slebetman
8

Oktawa, 27 19 bajtów

@(a)a(cummax(a)==a)
alephalpha
źródło
7

Pyth, 12 bajtów

eMfqeTeST._Q

Sprawdź wszystkie przypadki testowe jednocześnie.

Jak to działa

         ._Q  Compute all prefixes of the input.
  f           Filter; for each T in the prefixes:
    eT          Retrieve the last element of T.
      eST       Sort T and retrieve its last element.
   q            Check for equality.
              Keep T if q returned True.
eM            Select the last element of each kept T.
Dennis
źródło
7

Brachylog , 5 bajtów

⊇ᶠ↔ᵒt

Wypróbuj online!

Galaretka , 5 bajtów

ŒPUÞṪ

Wypróbuj online!

Wyjaśnienie

⊇ᶠ↔ᵒt    ŒPUÞṪ
⊇ᶠ       ŒP       On all subsequences of {the input}
   ᵒ        Þ     sort by
  ↔        U      their reverse
    t        Ṫ    then take the last element (i.e. the maximum as given by the sort)

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.

ais523
źródło
6

Mathematica, 26 bajtów

DeleteDuplicates[#,#>#2&]&
celtschk
źródło
2
Nie znam Mathematiki, ale coś, co wywołuje DeleteDuplicates, nie wygląda na to, by zwróciło {10, 10, 10, 10}dane wejściowe{10, 10, 10, 9, 10}
Dennis,
2
@Dennis: Tak, przetestowałem to. Sztuka polega na tym, że zdaję, że „jest większy niż„ jako test „równoważności”. Tak, jest to niewłaściwe użycie tej funkcji, ale działa, a golf golfowy i tak nie dotyczy najlepszych praktyk programistycznych.
celtschk
2
OK, pomimo tego, co sugeruje nazwa, DeleteDuplicatesdwa argumenty wydają się być prostym filtrem.
Dennis
5

R 29 29 26 bajtów

function(x)x[x>=cummax(x)]

Tworzy to obiekt funkcji, który akceptuje wektor xi zwraca xpo usunięciu wszystkich elementów, które nie są tak duże, jak skumulowane maksimum x.

Zaoszczędź 3 bajty dzięki flodel!

Alex A.
źródło
Formularz funkcji byłby krótszy.
flodel
@flodel Masz absolutną rację. Dzięki!
Alex A.,
4

K, 11 bajtów

{x@&~x<|\x}

W akcji:

  f: {x@&~x<|\x}
  f'(1 2 5 4 3 7
     10 -1 12
     -7 -8 -5 0 -1 1
     9 8 7 6 5
     10 13 17 21
     10 10 10 9 10)

(1 2 5 7
 10 12
 -7 -5 0 1
 ,9
 10 13 17 21
 10 10 10 10)
JohnE
źródło
{x@&~<':x}jest bajt krótszy.
kirbyfan64sos
@ kirbyfan64sos: Używanie eachprior nie daje poprawnego wyniku. Rozważ przypadek wejściowy 3 4 2 2 5.
JohnE
O, rozumiem. Poprawka byłaby {x@&~<':x}/, ale ta sama długość.
kirbyfan64sos
3

Java, 82 bajty

void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}

Oto prosta pętla wyjściowa. Po prostu utrzymuje maksimum mi porównuje każdy element.

Geobity
źródło
1
Możesz go skrócić za pomocą lambda:a->{int m=a[0]...
Daniel M.
Tak, zwykle możesz. Jednak nie uprawiam golfów Java.
Geobits
3

Perl, 33 bajty

32 bajtowy kod + -p

$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge

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) poprzez STDIN:

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1'
-7 -5 0 1
perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10'
10 10 10 10
Dom Hastings
źródło
3

Python 3, 67

Dość brutalna siła. Zmieniłem to na funkcję, ponieważ brakowało mi, że była to poprawna odpowiedź.

def f(i):
 s=[i[0]]
 for n in i[1:]:
  if s[-1]<=n:s+=[n]
 return s

Wersja bez golfa:

input_numbers = input().split()
sorted_numbers = []
previous_number = int(input_numbers[0])
for number in map(int, input_numbers):
    if previous_number <= number:
        sorted_numbers.append(number)
        previous_number = number
print(sorted_numbers)
Morgan Thrapp
źródło
62 bajty
movatica
3

Haskell, 38 37 bajtów

Zaoszczędzono 1 bajt dzięki JArkinstall .

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s
alephalpha
źródło
1
Możesz zastąpić jeden ze swoich zestawów nawiasów, $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 (
Średnik
3

C # - 6864 lub 132127 znaków

int[]f(int[]b){return b.Where((v,i)=>i<1||b[i-1]<=v).ToArray();}

Wherew tym przypadku iteruje po liście i dla każdego elementu vw indeksie ina 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 to IndexOutOfRangeExceptionwyją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).

string t(string b){var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();return String.Join(" ",c.Where((v,i)=>i<1||c[i-1]<=v));}

Trochę dekompresji daje:

string t(string b) 
{
    var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();
    return String.Join(" ",c.Where((v, i)=>i<1||c[i-1]<=v));
}

W tym przypadku drugi wiersz funkcji używa dokładnie takiej samej logiki jak powyżej. W Selectchwyta elementy listy i konwertuje je do int. Wywołanie ToList1 zmusza selekcję do oceny i zamienia ją varw List<int>czas kompilacji, dzięki czemu Whereoperuje 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?

theB
źródło
Jeśli przeliczyłem się lub jeśli moje wyjaśnienie wymaga wyjaśnienia, daj mi znać. :)
theB
1
Dobra robota - możesz zaoszczędzić kilka bajtów, używając kilku popularnych sztuczek - nie potrzebujesz spacji po zadeklarowaniu tablicy int[]f(int[]b), a i<1zamiast tego możesz nieco i==0skró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 twoim
sygnale
@VisualMelon - Dzięki! Uznałem, że każde błędne zliczanie spowoduje, że suma będzie większa. ;)
theB
3

CJam, 15 bajtów

q~{_2$<{;}&}*]p

Wypróbuj online w interpretatorze CJam .

Jak to działa

q~               Read an evaluate all input.
  {        }*    Reduce; push the first element; or each remaining element:
   _2$           Copy the topmost and second topmost element from the stack.
      <          Check if the topmost is smaller than the second topmost.
       {;}&      If it is, remove it from the stack.
             ]   Wrap the stack i an array.
              p  Print.
Dennis
źródło
3

PowerShell , 32 bajty

$args|?{$e-eq$p-or$_-ge$p;$p=$_}

Wypróbuj online!

Mniej golfa:

$args|?{
    $empty -eq $previous -or $_ -ge $previous
    $previous = $_
}
mazzy
źródło
2

C: 73 bajty

int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;

lub

C: 49 bajtów

(Jeśli nagłówek celny przeznaczony na zawody codegolf jest dozwolone)

I z,y;z=y=INT_MIN;w(s(D,&y)!=E)i(y>z)p(D,y),z=y;}

Nadal nie mogę pokonać CJam, ale przynajmniej pozwala to pokonać kilka innych języków.

Twórca gier
źródło
4
Przepraszamy, niestandardowy nagłówek jest niedozwolony; liczyłby się jako inny język.
lirtosiast
4
Podstawowym problemem związanym z niestandardowymi nagłówkami jest to, że opublikowałeś je po rozpoczęciu tego konkursu.
Dennis
Jasne, że rozumiem, ale wtedy nie mogę użyć go w przyszłych konkursach?
GameDeveloper
@DarioOO Możesz, ale konieczne będzie dołączenie instrukcji importu do liczby bajtów.
SuperJedi224,
Lub po prostu nazwij to nowym językiem.
CalculatorFeline
2

Burleska, 13 bajtów

11 bajtowe rozwiązanie, które przechodzi przypadki testowe:

-.2CO:so)[~

Spróbuj online tutaj .

Wyjaśnienie:

-. -- prepend head of list to list
2CO -- n-grams (sliding window) of size 2
:so -- filter sorted lists
)[~ -- map last

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:

J-]{cm-1.>}LO

Spróbuj online tutaj. Wyjaśnienie:

J -- duplicate
-] -- head
{
  cm -- compare (returning -1,0 or 1)
  -1.> -- greater than -1
}LO -- Loop

Jeśli upuścisz równe liczby, możesz .>użyć zamiast zamiast cm. Ponadto, jeśli listy zawierają tylko liczby dodatnie, możesz użyć jednego z nich 0lub -1zamiast nich J-].

mroman
źródło
Tak, ale wtedy nie mogę hiperłącza :).
mroman
naprawiony. Dodam tylko wiersz „spróbuj online tutaj”.
mroman
2

Minkolang 0,9 , 18 bajtów

ndN(nd1R`2&dN$I$).

Wypróbuj tutaj.

Wyjaśnienie

ndN                Take first integer from input
(         $I$).    Repeat until the input is empty and then stop.
 nd1R`             Is the next integer less than the previous one?
      2&dN         If not (i.e., it's greater than or equal to), print it.
El'endia Starman
źródło
2

Ruby, 41 37 znaków

->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}

Przykładowy przebieg:

2.1.5 :001 > [
2.1.5 :002 >     [1, 2, 5, 4, 3, 7],
2.1.5 :003 >     [10, -1, 12],
2.1.5 :004 >     [-7, -8, -5, 0, -1, 1],
2.1.5 :005 >     [9, 8, 7, 6, 5],
2.1.5 :006 >     [10, 13, 17, 21],
2.1.5 :007 >     [10, 10, 10, 9, 10],
2.1.5 :008 > ].each{ |test| p ->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}[test] }
[1, 2, 5, 7]
[10, 12]
[-7, -5, 0, 1]
[9]
[10, 13, 17, 21]
[10, 10, 10, 10]
człowiek w pracy
źródło
1
-[p]jest krótszy niż.compact
Nie, że Charles
Ups Oczywiście. Dziękuję Ci. (Uwaga dla siebie: nie wystarczy tylko głosować na [link codegolf.stackexchange.com/questions/363/... do gry w golfa w Ruby [/ link], też powinienem je zapamiętać.)
manatwork
2

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.

lirtosiast
źródło
Dlaczego więc codegolf.stackexchange.com/questions/61808/... nie ma tu zastosowania?
kot
NARS2000 nie może używać starszych kodowań APL - i nawet przed regułą, że kodowania muszą być tymi faktycznie używanymi przez tłumaczy, nie może to być 7 bajtów, ponieważ psi nie jest częścią żadnego starszego kodowania APL.
lirtosiast
2

> <> z flagą -v, 36 31 + 2 = 33 bajty

:&\o " "&n:~& <
~ >l?!;:&:&(?!^

Wpisz 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 :

$ for input in "1 2 5 4 3 7" "10 -1 12" "-7 -8 -5 0 -1 1" "9 8 7 6 5" "10 13 17 21" "10 10 10 9 10"; do echo $input '-> ' $(python fish.py dropsort.fsh -v $(echo $input | tac -s ' ')); done

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

Edycja: zapisano 5 bajtów dzięki Fongoid

Aaron
źródło
Możesz zapisać 5 bajtów, refaktoryzując wiersz 1 jako :&\o" "&n:~& <i wiersz 2 jako~ >l?!;:&:&(?!^
Fongoid
@ Dziękuję, zaktualizowane!
Aaron
2

Python, 102 99 94 + 5 6 nowych wierszy nieobjętych plikiem = 107 105 100 bajtów

(Użyłem tabulatorów do wcięcia)

def d(l):
    j=b=0;m=l[j];r=[]
    for i in l:
        (m,b)=[(m,0),(i,1)][i>=m]
        if b>0:r+=[i]
        j+=1
    l[:]=r

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 !

James Murphy
źródło
r + = [i] jest zwarte niż r.append
njzk2
Próbowałem to zrobić wcześniej, ale wystąpił błąd, ponieważ nie zdawałem sobie sprawy, że musisz to zrobić za pomocą nawiasów. Dzięki!
James Murphy
2

Scala: 232 126 120 bajtów

def f(x:Int*)=(Seq[Int]()/:x)((r,y)=>r.headOption.filter(y>=).map(_=>y+:r).getOrElse(if(r.isEmpty) y+:r else r)).reverse
Martin Seeler
źródło
2
Dodanie „metody rozszerzenia” dla List[Int]nie spełnia wymagań, powinieneś otrzymać dane wejściowe przez STDIN lub jako argument. Dodatkowo przesadza z odpowiedzią ... Dlaczego po prostu nie masz def dropSort(s:Seq[Int]):Seq[Int]?
Jacob
Myślałem, że to będzie wymyślne, ale masz rację, o wiele za dużo bajtów ...
Martin Seeler,
1
Bardzo dobra poprawa za pomocą fold! Nadal możesz golić niektóre spacje, a także możesz użyć y> = zamiast _ <= y, co daje ostrzeżenie o kompilacji bez odpowiedniego importu, ale także pokazuje, jak niesamowita jest Scala (och, i goli inną postać).
Jacob
Dzięki za napiwek!
Martin Seeler
2

Scala, 54 bajty

def f(x:Int*)=(x:\Seq[Int]())((y,r)=>y+:r.filter(y<=))

Nie golfowany:

def dropSort(xs: Seq[Int]): Seq[Int] =
  xs.foldRight(Seq.empty[Int]) { (x, result) =>
    x +: result.filter(r => r >= x)
  }
knutwalker
źródło
2

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. )aa

(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:

(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))
         )
        ()
       )
   ) )
 )

Oto kilka przykładów, jak tego użyć (z przypadkami testowymi z pytania):

(d list (q (args args)))
(d -
   (q( (n)
       (s 0 n)
    ) )
 ) 

(ds (list 1 2 5 4 3 7))
(ds (list 10 (- 1) 12))
(ds (list (- 7) (- 8) (- 5) 0 (- 1) 1))
(ds (list 9 8 7 6 5))
(ds (list 10 13 17 21))
(ds (list 10 10 10 9 10))

(Tak, -7nie jest literałem całkowitoliczbowym, więc musimy zdefiniować funkcję do ich reprezentowania.) Wynik:

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)
Paŭlo Ebermann
źródło
„-7 nie jest liczbą całkowitą” Wciąż się śmieję, +1
kot
Czy naprawdę wykorzystałeś każdą postać do wbudowania? (Z wyjątkiem r, jak sądzę ..)
CalculatorFeline
@CatsAreFluffy przepraszam, mam problem ze zrozumieniem Twojego komentarza. Tiny Lisp ma 7 wbudowanych funkcji i trzy wbudowane makra, wszystkie z pojedynczymi nazwami znaków (myślę, że ten język jest łatwiejszy w golfie), a nawiasy i przestrzeń są specjalną składnią. Zauważ, że Tiny Lisp nie jest moim wynalazkiem.
Paŭlo Ebermann
Ach, myślę, że teraz to rozumiem ... proponujesz użyć nazwy jednoznakowej zamiast ds? Myślę, że można to zrobić, zaoszczędziłby kolejny bajt. Wydaje mi się, że wybrałem dsjako skrót do sortowania upuszczonego.
Paŭlo Ebermann
Hej, właśnie to zauważyłem. Dobra robota! Według meta konsensusu, nienazwane funkcje lambda są prawidłową formą przesyłania, dzięki czemu można zaoszczędzić 6 bajtów, pozbywając się (d dsi 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. :)
DLosc
2

Galaretka, 5 bajtów

=»\Tị

Pamiętaj, że wyzwanie poprzedza stworzenie Galaretki.

Wypróbuj online!

Jak to działa

=»\Tị  Main link. Argument: A (list)

 »\    Yield the cumulative maxima of A.
=      Perform element-by-element comparison.
       Yields 1 iff A[n] = max(A[1], ..., A[n]).
   T   Get all indices of truthy elements.
    ị  Retrieve the items of A at those indices.
Dennis
źródło
1

Mathematica, 27 bajtów

Pick[#,#-Max~FoldList~#,0]&
alephalpha
źródło