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>
quelle
highest < current
? Oderhighest <= current
?highest (so far)<=current
.Antworten:
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.
quelle
J
109 BytesArbeitsversion meiner CJam-Idee (in weniger Bytes). Z.B:
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
:quelle
Haskell, 28
Eine anonyme Funktion. Nenne es so
Entspricht der Rekursion
Ü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<)
.quelle
foldr(\x->(x:).filter(>=x))[]
, stellt sich heraus, dass die Länge gleich ist.x:
Sie zwingt, den Punktoperator hinzuzufügen. Na ja ...O(n^2)
aber. viele nicht benötigte Vergleiche. ;-(Python 2, 49
quelle
max(a)
JavaScript (ES6), 29
Missbrauch der Standardtypkonvertierung in Javascript, Array zu Nummer:
quelle
Oktave,
27 bis19 Bytesquelle
Pyth, 12 Bytes
Überprüfen Sie alle Testfälle auf einmal.
Wie es funktioniert
quelle
Brachylog , 5 Bytes
Probieren Sie es online!
Gelee , 5 Bytes
Probieren Sie es online!
Erläuterung
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.
quelle
Mathematica, 26 Bytes
quelle
DeleteDuplicates
das nicht so aussieht, als würde es{10, 10, 10, 10}
zur Eingabe zurückkehren{10, 10, 10, 9, 10}
DeleteDuplicates
mit zwei Argumenten scheint ein einfacher Filter zu sein.R
2926 BytesDadurch wird ein Funktionsobjekt erstellt, das einen Vektor akzeptiert
x
undx
nach dem Entfernen aller Elemente zurückgegeben wird, die nicht mindestens so groß sind wie das kumulative Maximum vonx
.3 Bytes gespart dank flodel!
quelle
K, 11 Bytes
In Aktion:
quelle
{x@&~<':x}
ist ein Byte kürzer.3 4 2 2 5
.{x@&~<':x}/
, aber das ist die gleiche Länge.Java, 82 Bytes
Hier ist eine einfache Ausgangsschleife. Es behält nur das Maximum bei
m
und vergleicht jedes Element.quelle
a->{int m=a[0]...
Perl, 33 Bytes
32 Byte Code +
-p
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) überSTDIN
:quelle
Python 3, 67
Ziemlich rohe Gewalt. Es wurde in eine Funktion geändert, da ich die gültige Antwort übersehen habe.
Ungolfed-Version:
quelle
Haskell,
3837 BytesDank JArkinstall 1 Byte gespeichert .
quelle
$
, 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)C # -
6864 oder132127 ZeichenWhere
In diesem Fall wird die Liste durchlaufen und für jedes Elementv
am Indexi
in 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 dieIndexOutOfRangeException
Ausnahme 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.)
Ein bisschen Dekomprimieren ergibt:
In diesem Fall verwendet die zweite Zeile der Funktion genau die gleiche Logik wie oben. Das
Select
packt die Elemente der Liste und konvertiert sie inint
. Der Aufruf vonToList
1 erzwingt die Auswertung der Auswahl und verwandelt sievar
in eineList<int>
at-compile-Zeit, sodassWhere
eine 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?
quelle
int[]f(int[]b)
in Ordnung sind, und Sie können diese Prüfungi<1
eher verwenden, alsi==0
sie 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)
kannd=>int.Parse(d)
ich auch nur 67 Bytes zählen, nicht 68 in Ihrem Original;)CJam, 15 Bytes
Probieren Sie es online im CJam-Interpreter aus .
Wie es funktioniert
quelle
PowerShell , 32 Byte
Probieren Sie es online!
Weniger golfen:
quelle
C: 73 Bytes
oder
C: 49 Bytes
(Wenn Zoll Header für codegolf Wettbewerbe gemacht ist erlaubt)
Kann CJam immer noch nicht schlagen, aber zumindest erlaubt dies, einige andere Sprachen zu schlagen.
quelle
Burlesque, 13 Bytes
11-Byte-Lösung, die Testfälle besteht:
Versuchen Sie es hier online .
Erläuterung:
Diese Version funktioniert jedoch nur, wenn keine zwei kleineren Zahlen zwischen zwei Zahlen liegen. Verwenden Sie andernfalls die folgende Version (13B):
Ältere Versionen:
Versuchen Sie es hier online. Erläuterung:
Wenn Sie auch die gleiche Anzahl fallen lassen, können Sie einfach mit gehen,
.>
anstatt zu verwendencm
. Wenn Listen nur positive Zahlen enthalten, können Sie entweder0
oder-1
anstelle von verwendenJ-]
.quelle
Minkolang 0,9 , 18 Bytes
Probieren Sie es hier aus.
Erläuterung
quelle
Ruby,
4137 ZeichenProbelauf:
quelle
-[p]
ist kürzer als.compact
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.quelle
> <> mit -v flag,
3631 + 2 = 33 bytesGeben 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 :
Bearbeiten: 5 Bytes dank Fongoid gespeichert
quelle
:&\o" "&n:~& <
und Zeile 2 wie~ >l?!;:&:&(?!^
Python,
1029994 +56 nicht abschließende Zeilenumbrüche =107105100 Bytes(Ich habe Tabulatoren zum Einrücken verwendet.)
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 !
quelle
Scala:
232126120 Bytesquelle
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 habendef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 Bytes
Ungolfed:
quelle
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,
a
der das neue Buildin abschatteta
(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 Hilfsfunktionr
), 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:
Hier einige Beispiele zur Verwendung (mit den Testfällen aus der Frage):
(Ja, es
-7
ist kein Integer-Literal, daher müssen wir eine Funktion definieren, um sie darzustellen.)quelle
r
, ich denke ..)ds
? Ich denke, dies könnte getan werden, würde ein weiteres Byte sparen. Ich denke, ich habeds
als Abkürzung für Drop-Sort gewählt.(d ds
das 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. :)Gelee, 5 Bytes
Beachten Sie, dass die Herausforderung vor der Erstellung von Jelly liegt.
Probieren Sie es online!
Wie es funktioniert
quelle
Mathematica, 27 Bytes
quelle