Verlustsortierung (Implement Dropsort)

61

Dropsort , entworfen von David Morgan-Mar, ist ein Beispiel für einen linearen "Sortieralgorithmus", der eine Liste erzeugt, die zwar sortiert ist, aber nur einige der ursprünglichen Elemente enthält. Jedes Element, das nicht mindestens so groß ist wie das Maximum der vorhergehenden Elemente, wird einfach aus der Liste entfernt und verworfen.

In dieser Aufgabe erhalten Sie eine Liste von Ganzzahlen als Eingabe (STDIN oder Funktionsargument, Sie müssen mindestens den Bereich von 8-Bit-Ganzzahlen mit Vorzeichen unterstützen.) Ihre Aufgabe besteht darin, diese zu sortieren und die verbleibenden Elemente in auszugeben Bestellung.

Sie können davon ausgehen, dass die Liste nicht leer ist.

Dies ist Codegolf, also gewinnt das kürzeste Programm.

Testfälle

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

Bestenliste

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
quelle
1
Ist der Scheck highest < current? Oder highest <= current?
Morgan Thrapp
7
Behalten Sie das aktuelle Element bei, wenn highest (so far)<=current.
SuperJedi224
Können wir davon ausgehen, dass die Liste mindestens ein Element enthält?
Lirtosiast
@ ThomasKwa: Ja.
SuperJedi224
19
Durch die verbesserte Effizienz von Dropsorts kann ein Unternehmen viel Geld sparen, wenn es in das Lohn- und Gehaltsabrechnungssystem einbezogen wird.
PyRulez

Antworten:

42

APL, 9 Bytes

⊢(/⍨)⊢=⌈\

Dies ist ein monadischer Funktionszug mit Diagramm:

┌─┼───┐  
⊢ ⍨ ┌─┼─┐
┌─┘ ⊢ = \
/     ┌─┘
      ⌈  

Die Nicht-Zug-Version ist

{⍵/⍨⍵=⌈\⍵}

Dies prüft grundsätzlich, ob jedes Element dem laufenden Maximum entspricht.

Beachten Sie, dass die J-Lösung von Martin Büttner dieselbe Länge wie diese hat und zuerst veröffentlicht wurde.

Lirtosiast
quelle
41
Bonuspunkte, weil es süß aussieht.
Sammitch
22
Code sieht aus wie ein verärgerter Typ, der auf eine Katzenklappe
schießt
2
Ich weiß nicht viel über das Zählen von Bytes und welche Codierung verwendet werden soll, aber laut mothereff.in/byte-counter und meta.codegolf.stackexchange.com/questions/4944/… sind dies 17 Bytes und Bytesizematters. com es ist 13.
DLeh
3
@DLeh Das ist in UTF-8. APL verfügt über eine eigene Legacy-Codierung, die 1 Byte pro APL-Zeichen entspricht, bevor Unicode vorhanden war.
Isaacg
3
@DLeh bytesizematters verwendet einen zusammengesetzten Algorithmus zum Zählen der Bytes, der einer tatsächlichen Codierung nicht entspricht (und nicht entsprechen kann ).
Dennis
21

J 10 9 Bytes

#~(=>./\)

Arbeitsversion meiner CJam-Idee (in weniger Bytes). Z.B:

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

Erläuterung

Zunächst erhalten wir das Maximum jedes Präfixes mit:

    >./\

(Hier >.ist der maximale Operator, /faltet diesen Operator auf eine Liste und \ruft alle Präfixe der Eingabe ab.)

Dann vergleichen wir die ursprüngliche Liste mit diesen Maxima für die Gleichheit:

  (=>./\)

Und schließlich wählen wir alle Elemente aus, bei denen diese Liste der booleschen Ergebnisse Folgendes ergab 1:

#~(=>./\)
Martin Ender
quelle
16

Haskell, 28

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

Eine anonyme Funktion. Nenne es so

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

Entspricht der Rekursion

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

Übersetzt iterativ, iterieren wir über die Elemente und entfernen für jedes Element, das wir sehen, die kleineren aus dem Rest der Liste, über die wir iterieren. Vielen Dank an Antisthenes für ein Byte, das mit gespeichert wurde (x<).

xnor
quelle
Warum nicht das Lambda curry? Sollte ein paar Zeichen speichern ...
MathematicalOrchid
@ MathematicalOrchid Wenn Sie meinen foldr(\x->(x:).filter(>=x))[], stellt sich heraus, dass die Länge gleich ist.
Xnor
Ah. Ich habe gerade den Filter am Ende gesehen und dachte: "Hey, das kannst du curry!" Mir ist nicht eingefallen, dass die x:Sie zwingt, den Punktoperator hinzuzufügen. Na ja ...
MathematicalOrchid
1
es ist O(n^2)aber. viele nicht benötigte Vergleiche. ;-(
stolzer haskeller
Warum nicht (> = x) in (x <) ändern? Es wird 1 Byte sparen
Antisthenes
10

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
Feersum
quelle
1
Das ist großartig.
Morgan Thrapp
1
@ThomasKwa Das Problem ist, wie Sie die rekursiven Aufrufe stoppen. Sie benötigen den leeren Fall, auch wenn die Eingabe diesen Fall ausschließt.
Bakuriu
Das Problem dabei ist, dass es wegenmax(a)
njzk2 28.10.15
1
@ njzk2 Für die Challenge müssen die Implementierungen nicht in linearer Zeit ausgeführt werden.
Feersum
3
@ njzk2 Schöne Codes beenden zuletzt!
Feersum
10

JavaScript (ES6), 29

Missbrauch der Standardtypkonvertierung in Javascript, Array zu Nummer:

  • Array von nur 1 Zahl => diese Zahl
  • irgendein anderes Array => 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
quelle
Beeindruckend. Ich dachte, 38 Bytes wären ungefähr das Beste. anscheinend habe ich mich sehr geirrt. +1
ETHproductions
Tischgesteuerte Tests. Nett!
Slebetman
8

Oktave, 27 bis 19 Bytes

@(a)a(cummax(a)==a)
Alephalpha
quelle
7

Pyth, 12 Bytes

eMfqeTeST._Q

Überprüfen Sie alle Testfälle auf einmal.

Wie es funktioniert

         ._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
quelle
7

Brachylog , 5 Bytes

⊇ᶠ↔ᵒt

Probieren Sie es online!

Gelee , 5 Bytes

ŒPUÞṪ

Probieren Sie es online!

Erläuterung

⊇ᶠ↔ᵒ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)

Dies ist eine seltene Situation: Ich verwende einen Algorithmus, den (soweit ich das mit einem kurzen Blick beurteilen kann) bisher niemand verwendet, und der in zwei sehr unterschiedlichen Golfsprachen mit sehr unterschiedlicher Syntax und Syntax dieselbe Länge hat Eingebaute Sets mit einer 1: 1-Entsprechung zwischen den Programmen (die Befehle sind sogar in derselben Reihenfolge!). Es schien also sinnvoller, sie zu kombinieren - in gewisser Weise handelt es sich um dasselbe Programm, und ich schrieb es in beiden Sprachen, um zu sehen, was kürzer war, als sie getrennt einzureichen.

Die Grundidee dabei ist, dass die Drop-Sortierung einer Liste ihre Subsequenz mit der lexikografisch maximalen Umkehrung ist. Seltsamerweise haben weder Brachylog noch Jelly ein Builtin, um das Maximum einer bestimmten Funktion zu finden (Jelly hat ein Builtin, um alle Maxima einer bestimmten Funktion zurückzugeben, aber das würde eine Singleton-Liste zurückgeben, die das Ergebnis und nicht das Ergebnis selbst enthält, und ist auch nicht kürzer als so). Also generieren wir stattdessen alle möglichen Teilsequenzen, sortieren in umgekehrter Reihenfolge, nehmen die letzten.

Der Grund, warum "lexikographisch maximale Umkehrung" funktioniert, ist, dass die gewählte Ausgabe mit der höchsten Nummer in der Eingabeliste enden muss (daher muss ihre Umkehrung beginnen) (es ist leicht zu erkennen, dass die Drop-Sort-Ausgabe immer damit endet) und dies auch kann Enthält danach nichts mehr (weil die Reihenfolge erhalten bleibt, wenn Unterfolgen ausgeführt werden). Wiederholen Sie induktiv und wir erhalten die Definition von Dropsort.

ais523
quelle
6

Mathematica, 26 Bytes

DeleteDuplicates[#,#>#2&]&
Celtschk
quelle
2
Ich kenne Mathematica nicht, aber etwas, DeleteDuplicatesdas nicht so aussieht, als würde es {10, 10, 10, 10}zur Eingabe zurückkehren{10, 10, 10, 9, 10}
Dennis
2
@Dennis: Ja, ich habe es getestet. Der Trick ist, dass ich "größer als" als "Äquivalenz" teste. Ja, es ist ein Missbrauch dieser Funktion, aber es funktioniert, und beim Code-Golf geht es sowieso nicht gerade um die besten Programmierpraktiken.
Celtschk
2
OK, trotz dem, was der Name andeutet, DeleteDuplicatesmit zwei Argumenten scheint ein einfacher Filter zu sein.
Dennis
5

R 29 26 Bytes

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

Dadurch wird ein Funktionsobjekt erstellt, das einen Vektor akzeptiert xund xnach dem Entfernen aller Elemente zurückgegeben wird, die nicht mindestens so groß sind wie das kumulative Maximum von x.

3 Bytes gespart dank flodel!

Alex A.
quelle
Die Funktionsform wäre kürzer.
Flodel
@flodel Du hast absolut recht. Vielen Dank!
Alex A.
4

K, 11 Bytes

{x@&~x<|\x}

In Aktion:

  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
quelle
{x@&~<':x}ist ein Byte kürzer.
kirbyfan64sos
@ kirbyfan64sos: Die Verwendung von eachprior führt nicht zum richtigen Ergebnis. Betrachten Sie den Eingabefall 3 4 2 2 5.
JohnE
Ah ich sehe. Ein Update wäre {x@&~<':x}/, aber das ist die gleiche Länge.
kirbyfan64sos
3

Java, 82 Bytes

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

Hier ist eine einfache Ausgangsschleife. Es behält nur das Maximum bei mund vergleicht jedes Element.

Geobits
quelle
1
Sie können es mit einem Lambda kürzen:a->{int m=a[0]...
Daniel M.
Ja, das kannst du normalerweise. Ich spiele allerdings keine Lambda-Ize-Java-Golf.
Geobits
3

Perl, 33 Bytes

32 Byte Code + -p

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

Wenn zusätzliche Leerzeichen in der Ausgabe zulässig sind, können durch Entfernen von und 31 Byte angegeben werden ?. Akzeptiert eine Zeichenfolge (oder die Anzahl der durch Zeilenumbrüche getrennten Zeichenfolgen) über 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
quelle
3

Python 3, 67

Ziemlich rohe Gewalt. Es wurde in eine Funktion geändert, da ich die gültige Antwort übersehen habe.

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

Ungolfed-Version:

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
quelle
62 Bytes
Movatica
3

Haskell, 38 37 Bytes

Dank JArkinstall 1 Byte gespeichert .

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s
Alephalpha
quelle
1
Sie können einen Ihrer Klammersätze durch ein ersetzen $, um ein ganzes Byte zu verkürzen! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Semikolon wird verwendet, weil Kommentare keine Zeilenumbrüche zulassen)
JArkinstall
3

C # - 6864 oder 132127 Zeichen

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

WhereIn diesem Fall wird die Liste durchlaufen und für jedes Element vam Index iin der Liste der boolesche Ausdruck ausgewertet. Wenn der Ausdruck true ergibt, wird das Element zum Ergebnis hinzugefügt. Der einzige echte Trick für den Booleschen Ausdruck ist, dass C # kurzgeschlossen oder ausgewertet wird, sobald eine Bedingung als wahr ausgewertet wird. Dadurch wird die IndexOutOfRangeExceptionAusnahme verhindert und das erste Element in der Liste beibehalten.

Wenn die Eingabe und Ausgabe Zeichenfolgen sein müssen (ich konnte nicht sicher sagen, also überlasse ich es dem OP und dem Rest von Ihnen, um zu entscheiden.)

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

Ein bisschen Dekomprimieren ergibt:

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

In diesem Fall verwendet die zweite Zeile der Funktion genau die gleiche Logik wie oben. Das Selectpackt die Elemente der Liste und konvertiert sie in int. Der Aufruf von ToList1 erzwingt die Auswertung der Auswahl und verwandelt sie varin eine List<int>at-compile-Zeit, sodass Whereeine Auflistung von ganzen Zahlen verarbeitet wird.

Probieren Sie es auf C # Pad

Vielen Dank an VisualMelon für die Unterstützung beim Trimmen von 4 Bytes bzw. 5 Bytes. :)

1 Tutu Liste?

theB
quelle
Wenn ich falsch gezählt habe oder wenn meine Erklärung eine Erklärung benötigt, lassen Sie es mich bitte wissen. :)
theB
1
Gute Arbeit - Sie können ein paar Bytes einsparen, indem Sie einige allgemeine Tricks anwenden - Sie brauchen keine Leerzeichen, nachdem die Array-Deklarationen int[]f(int[]b)in Ordnung sind, und Sie können diese Prüfung i<1eher verwenden, als i==0sie ein wenig zu verkürzen. Für die String-Version können Sie auch die Klammern um ein einzelnes Argument in einem Lambda setzen (z . B. (d)=>int.Parse(d)kann d=>int.Parse(d)ich auch nur 67 Bytes zählen, nicht 68 in Ihrem Original;)
VisualMelon
@VisualMelon - Danke! Ich nahm an, dass jede Fehlzählung die Gesamtsumme vergrößern würde. ;)
theB
3

CJam, 15 Bytes

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

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

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
quelle
3

PowerShell , 32 Byte

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

Probieren Sie es online!

Weniger golfen:

$args|?{
    $empty -eq $previous -or $_ -ge $previous
    $previous = $_
}
mazzy
quelle
2

C: 73 Bytes

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

oder

C: 49 Bytes

(Wenn Zoll Header für codegolf Wettbewerbe gemacht ist erlaubt)

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

Kann CJam immer noch nicht schlagen, aber zumindest erlaubt dies, einige andere Sprachen zu schlagen.

Spielentwickler
quelle
4
Der benutzerdefinierte Header ist leider nicht zulässig. es würde als eine andere Sprache gelten.
Lirtosiast
4
Das Hauptproblem bei Ihren benutzerdefinierten Kopfzeilen besteht darin, dass Sie sie nach dem Start dieses Wettbewerbs veröffentlicht haben.
Dennis
Klar verstehe ich, aber dann kann ich es auch nicht in zukünftigen Wettbewerben verwenden?
GameDeveloper
@DarioOO Sie können, aber Sie müssen die Importanweisung in Ihre Byteanzahl einbeziehen.
SuperJedi224
Oder nenne es einfach eine neue Sprache.
CalculatorFeline
2

Burlesque, 13 Bytes

11-Byte-Lösung, die Testfälle besteht:

-.2CO:so)[~

Versuchen Sie es hier online .

Erläuterung:

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

Diese Version funktioniert jedoch nur, wenn keine zwei kleineren Zahlen zwischen zwei Zahlen liegen. Verwenden Sie andernfalls die folgende Version (13B):

Ältere Versionen:

J-]{cm-1.>}LO

Versuchen Sie es hier online. Erläuterung:

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

Wenn Sie auch die gleiche Anzahl fallen lassen, können Sie einfach mit gehen, .>anstatt zu verwenden cm. Wenn Listen nur positive Zahlen enthalten, können Sie entweder 0oder -1anstelle von verwenden J-].

mroman
quelle
Ja, aber dann kann ich es nicht verlinken :).
Mroman
Fest. Ich werde einfach eine Zeile "hier online testen" hinzufügen.
Mroman
2

Minkolang 0,9 , 18 Bytes

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

Probieren Sie es hier aus.

Erläuterung

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
quelle
2

Ruby, 41 37 Zeichen

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

Probelauf:

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]
Mann bei der Arbeit
quelle
1
-[p]ist kürzer als.compact
Nicht dass Charles
Hoppla. Na sicher. Danke. (Anmerkung für mich selbst: reicht nicht aus, um den [link codegolf.stackexchange.com/questions/363/… zum Golfen in Ruby [/ link] zu verbessern , ich sollte sie mir auch merken.)
manatwork
2

NARS2000 APL, 13 Byte

NARS2000 ist ein kostenloser APL-Interpreter für Windows. Es enthält Multiset-Funktionen, auf die der Bediener zugreift .

(+⍦∩⌈\)

Dies ist eine monadische Verzweigung, die den Multiset-Schnittpunkt ( ⍦∩) der Eingabe ( +) * und die Liste der laufenden Maxima ( ⌈\) verwendet.

Da es sich bei den Ein-Byte-APL-Legacy-Codierungen nicht um ein Standard-APL-Zeichen handelt, müssen Sie UTF-8 verwenden, sodass die ⍦∩⌈Zeichen jeweils drei Byte lang sind. Ich entschied mich, +statt zwei Bytes zu speichern.

NARS2000 unterstützt Gabeln, die in Züge ohne Klammern eingebaut werden können, aber im Gegensatz zu Dyalog können sie keiner Funktion zugewiesen werden, ohne die Funktion in Klammern zu setzen.

* +ist technisch komplex konjugiert, aber die Eingabe ist real.

Lirtosiast
quelle
Warum gilt codegolf.stackexchange.com/questions/61808/… auch hier nicht?
Katze
NARS2000 kann keine älteren APL-Codierungen verwenden - und selbst vor der Regel, dass Codierungen tatsächlich von Interpreten verwendet werden müssen, dürfen dies keine 7 Byte sein, da psi nicht Teil einer älteren APL-Codierung ist.
Lirtosiast
2

> <> mit -v flag, 36 31 + 2 = 33 bytes

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

Geben Sie die Liste auf dem Stapel mit -v ein, so dass sich das erste Element der Liste oben auf dem Stapel befindet. Die Drop-Sorted-Liste wird mit einem Leerzeichen am Ende gedruckt.

Testlauf :

$ 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

Bearbeiten: 5 Bytes dank Fongoid gespeichert

Aaron
quelle
Sie können 5 Bytes einsparen, indem Sie Zeile 1 wie :&\o" "&n:~& <und Zeile 2 wie~ >l?!;:&:&(?!^
Fongoid 27.10.15
@ Fongoid danke, aktualisiert!
Aaron
2

Python, 102 99 94 + 5 6 nicht abschließende Zeilenumbrüche = 107 105 100 Bytes

(Ich habe Tabulatoren zum Einrücken verwendet.)

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

Nicht das beste da draußen, aber dies ist mein erster Versuch mit Codegolf. Konnte keinen Weg finden, die Liste inline zu sortieren, ohne auf entfernungsbedingte Fehler zu stoßen, also habe ich die sortierten Elemente in eine temporäre Liste verschoben.

EDIT: list.append () ist kürzer als hässlich

r + = [i] war kürzer als list.append (); danke njzk2 !

James Murphy
quelle
r + = [i] ist kurzgeschlossen als r.append
njzk2
Ich habe das schon versucht, habe aber einen Fehler bekommen, weil mir nicht klar war, dass du es mit Klammern machen musst. Vielen Dank!
James Murphy
2

Scala: 232 126 120 Bytes

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
quelle
2
Wenn Sie eine "Erweiterungsmethode" für List[Int]hinzufügen, die nicht den Anforderungen entspricht, sollten Sie die Eingabe über STDIN oder als Argument erhalten. Plus, es bläht Ihre Antwort auf ... Warum nicht einfach haben def dropSort(s:Seq[Int]):Seq[Int]?
Jacob
Ich dachte, es wäre schick, aber Sie haben Recht, viel zu viel Bytes ...
Martin Seeler
1
Sehr schöne Verbesserung mit Falz! Sie können immer noch einige Leerzeichen entfernen und auch y> = anstelle von _ <= y verwenden, was zu einer Kompilierungswarnung ohne ordnungsgemäßen Import führt, aber auch demonstriert, wie großartig Scala ist (oh, und ein anderes Zeichen entfernt).
Jacob
Danke für den Tipp!
Martin Seeler
2

Scala, 54 Bytes

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

Ungolfed:

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

Kleine Lisp, 107 Bytes

( Diese Sprache wurde erst nach dieser Frage veröffentlicht, sodass diese Antwort außer Konkurrenz gerät . Nicht, dass sie eine Gewinnchance gehabt hätte. Die Sprache hat sich später weiterentwickelt und enthält mehr Buildins als die, die ich hier verwendet habe, aber ich bleibe bei der Version, die ich ursprünglich im Jahr 2015 implementiert habe. Diese Antwort funktioniert immer noch mit dem neueren offiziellen Interpreter , obwohl sie einige Warnungen enthält, da ich einen Parameter definiere, ader das neue Buildin abschattet a(zum Hinzufügen). Danke an DLosc für den TIO-Link. )

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

Dies definiert eine Funktion ds(und ihre rekursive Hilfsfunktion r), die ihr Argument sortiert, das eine Liste von ganzen Zahlen sein muss.

r ist keine schwanzrekursive Funktion, daher kann es bei sehr langen Listen zu einem Stapelüberlauf kommen.

Ungolfed:

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

Hier einige Beispiele zur Verwendung (mit den Testfällen aus der Frage):

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

(Ja, es -7ist kein Integer-Literal, daher müssen wir eine Funktion definieren, um sie darzustellen.)

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)
Paŭlo Ebermann
quelle
"-7 ist kein Integer-Literal" Ich lache immer noch, +1
Katze
Hast du wirklich jedes einzelne Zeichen für Buildins verbraucht? (Außer r, ich denke ..)
CalculatorFeline
@CatsAreFluffy Entschuldigung, ich habe Probleme, Ihren Kommentar zu verstehen. Tiny Lisp verfügt über 7 eingebaute Funktionen und drei eingebaute Makros, die alle einzelne Zeichennamen haben (ich denke, um die Sprache für das Golfen einfacher zu machen), wobei Klammern und Leerzeichen eine spezielle Syntax sind. Beachten Sie, dass Tiny Lisp nicht meine Erfindung ist.
Paŭlo Ebermann
Ah, ich glaube, ich verstehe es jetzt ... Sie schlagen vor, statt eines einzelnen Zeichens einen Namen zu verwenden ds? Ich denke, dies könnte getan werden, würde ein weiteres Byte sparen. Ich denke, ich habe dsals Abkürzung für Drop-Sort gewählt.
Paŭlo Ebermann
Hey, das ist mir gerade aufgefallen. Gute Arbeit! Laut Metakonsens sind unbenannte Lambda-Funktionen eine gültige Form der Übermittlung. Sie können also 6 Bytes einsparen, indem Sie (d dsdas Matching )am Ende entfernen . Andere Golfarten sind möglich, wenn Sie meinen aktuellen Interpreter verwenden möchten, aber wenn Sie sich an die Spezifikation in der ursprünglichen Frage halten möchten, ist das auch in Ordnung. :)
DLosc
2

Gelee, 5 Bytes

=»\Tị

Beachten Sie, dass die Herausforderung vor der Erstellung von Jelly liegt.

Probieren Sie es online!

Wie es funktioniert

=»\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
quelle
1

Mathematica, 27 Bytes

Pick[#,#-Max~FoldList~#,0]&
Alephalpha
quelle