Dropsort , conçu par David Morgan-Mar, est un exemple d'un "algorithme de tri" à temps linéaire qui produit une liste qui est en fait triée, mais ne contient que certains des éléments d'origine. Tout élément qui n’est pas au moins aussi grand que le maximum des éléments qui le précèdent est simplement supprimé de la liste et supprimé.

Dans cette tâche, vous recevrez une liste d'entiers en entrée (STDIN ou argument de fonction, vous devez prendre en charge au moins la plage des entiers signés 8 bits.) Votre tâche consiste à les triper, puis à afficher les éléments restants dans ordre.

Vous pouvez supposer que la liste est non vide.

C'est du code golf, donc le programme le plus court gagne.

Cas de test

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

Classement

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>

APL, 9 octets

⊢(/⍨)⊢=⌈\

Il s'agit d'un train de fonctions monadique avec diagramme:

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

La version non-train est

{⍵/⍨⍵=⌈\⍵}

Cela vérifie fondamentalement si chaque élément est égal au maximum courant.

Notez que la solution J de Martin Büttner a la même longueur et a été publiée en premier.

J, 10 9 octets

#~(=>./\)

Version de travail de mon idée CJam (en moins d'octets). Par exemple:

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

Explication

Tout d'abord, nous obtenons le maximum de chaque préfixe, avec:

    >./\

(Ici, >.l’opérateur maximum, le /replie dans une liste et \obtient tous les préfixes de l’entrée.)

Ensuite, nous comparons la liste initiale avec ces maxima d'égalité:

  (=>./\)

Et enfin, nous sélectionnons tous les éléments pour lesquels cette liste de résultats booléens a donné un 1:

#~(=>./\)

Haskell, 28 ans

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

Une fonction anonyme. Appelez ça comme

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

Équivalent à la récursion

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

Traduit itérativement, nous parcourons les éléments et, pour chacun d'entre eux, nous supprimons ceux qui sont plus petits que ceux-ci du reste de la liste sur laquelle nous parcourons. Merci à Antisthenes pour un octet enregistré avec (x<).

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))

JavaScript (ES6), 29

Utilisation abusive de la conversion de type standard en javascript, d'un tableau à un autre:

• tableau d'un seul nombre => ce nombre
• tout autre tableau => 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>

Octave, 27 19 octets

@(a)a(cummax(a)==a)

Pyth, 12 octets

eMfqeTeST._Q

Vérifiez tous les cas de test à la fois.

Comment ça fonctionne

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

Brachylog , 5 octets

⊇ᶠ↔ᵒt

Essayez-le en ligne!

Gelée , 5 octets

ŒPUÞṪ

Essayez-le en ligne!

Explication

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

C’est une situation rare: j’utilise un algorithme que personne n’utilise jusqu’à présent (pour autant que je sache, rapidement) et qui aboutit en quelque sorte à la même longueur dans deux langues de golf très différentes, avec une syntaxe et une syntaxe très différentes. jeux intégrés, avec une correspondance 1 à 1 entre les programmes (les commandes sont même dans le même ordre!). Il semblait donc plus logique de les combiner - en un sens, il s’agit du même programme, et je l’ai écrit dans les deux langues pour voir quelle version était plus courte - que de les soumettre séparément.

L'idée de base ici est que le dropsort d'une liste est sa sous-séquence avec l'inverse lexicographiquement maximum. Bizarrement, ni Brachylog ni Jelly n’ont la capacité de trouver le maximum par une fonction particulière (Jelly a pour fonction de renvoyer tous les maxima d’une fonction particulière, mais cela renverrait une liste de singleton contenant le résultat plutôt que le résultat lui-même, et n’est même pas plus court que de le faire de cette façon). Au lieu de cela, nous générons toutes les sous-séquences possibles, trions par inversion, prenons la dernière.

La raison pour laquelle "inverse lexicographiquement maximum" fonctionne est que la sortie choisie doit se terminer (et donc son inverse doit commencer) par le nombre le plus élevé dans la liste des entrées (il est facile de voir que la sortie du système de dropsort se terminera toujours par cela), et ne contient plus rien après ça (parce que prendre des sous-séquences préserve l’ordre). Répétez inductivement et nous nous retrouvons avec la définition de dropsort.

Mathematica, 26 octets

DeleteDuplicates[#,#>#2&]&

R, 29 26 octets

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

Cela crée un objet fonction qui accepte un vecteur xet revient xaprès la suppression de tous les éléments dont la taille est au moins égale au maximum cumulé x.

3 octets sauvés grâce à flodel!

K, 11 octets

{x@&~x<|\x}

En action:

  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)

Java, 82 octets

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

Voici une boucle de sortie simple. Il maintient juste le maximum met compare chaque élément.

Perl, 33 octets

Code de 32 octets + -p

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

Si des espaces supplémentaires sont acceptables dans la sortie, vous pouvez supprimer 31 octets en supprimant et ?. Accepte une chaîne (ou un nombre de chaînes séparées par une nouvelle ligne) via 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

Python 3, 67

Jolie force brute. Changé en une fonction, parce que j'ai raté que c'était une réponse valide.

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

Version non-golfée:

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)

Haskell, 38 37 octets

Enregistré 1 octet grâce à JArkinstall .

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s

C # - 6864 ou 132127 caractères

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

Wheredans ce cas, effectue une itération dans la liste et évalue l'expression booléenne pour chaque élément và l'index ide la liste. Si l'expression est évaluée à true, l'élément est ajouté au résultat. Le seul véritable truc pour l'expression booléenne est que C # court-circuite ou évalue dès qu'une condition est vraie. Cela empêche l' IndexOutOfRangeExceptionexception et conserve le premier élément de la liste.

Si les entrées et les sorties doivent être des chaînes (je ne saurais le dire, je laisserai donc à l'OP le soin de décider.)

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

Décompresser un peu donne:

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

Dans ce cas, la deuxième ligne de la fonction utilise exactement la même logique que ci-dessus. Le Selectsaisit les éléments de la liste et les convertit en int. L'appel à ToList¹ force l'évaluation de la sélection et la transforme varen a List<int>au moment de la compilation, de sorte qu'elle Wherefonctionne sur un ensemble d'entiers.

Essayez-le sur C # Pad

Merci à VisualMelon pour avoir aidé à couper 4 octets et 5 octets respectivement. :)

_{1 liste de tutu?}

CJam, 15 octets

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

Essayez-le en ligne dans l' interprète CJam .

Comment ça fonctionne

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.

PowerShell , 32 octets

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

Essayez-le en ligne!

Moins joué au golf:

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

C: 73 octets

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

ou

C: 49 octets

(Si l'en- tête de douane créé pour les compétitions codegolf est autorisé)

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

Je ne peux toujours pas battre CJam, mais au moins, cela permet de battre quelques autres langues.

Burlesque, 13 octets

Solution de 11 octets qui réussit les tests:

-.2CO:so)[~

Essayez en ligne ici .

Explication:

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

Cependant, cette version ne fonctionne qu'en utilisant le fait qu'il n'y a pas deux plus petits nombres entre deux nombres. Sinon, utilisez la version ci-dessous (qui est 13B):

Versions plus anciennes:

J-]{cm-1.>}LO

Essayez en ligne ici. Explication:

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

Si vous laissiez tomber également des nombres égaux, vous pourriez utiliser avec juste .>au lieu d'utiliser cm. En outre, si les listes ne contiennent que des nombres positifs que vous pouvez utiliser 0ou au -1lieu de J-].

Minkolang 0.9 , 18 octets

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

Essayez-le ici.

Explication

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.

Ruby, 41 37 caractères

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

Échantillon échantillon:

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]

NARS2000 APL, 13 octets

NARS2000 est un interpréteur APL gratuit pour Windows. il comprend des fonctionnalités multiset accessibles avec l' ⍦opérateur.

(+⍦∩⌈\)

C'est un fork monadique qui prend l'intersection multiset ( ⍦∩) de l'entrée ( +) * et la liste des maximums en cours d'exécution ( ⌈\).

Comme il ⍦ne s'agit pas d'un caractère APL standard dans les codages APL hérités d'un octet, nous devons utiliser UTF-8, les ⍦∩⌈caractères étant alors de trois octets. J'ai choisi +au lieu de ⊢sauvegarder deux octets.

NARS2000 prend en charge les fourches, qui peuvent être intégrées à des trains sans parenthèses, mais contrairement à Dyalog, elles ne permettent pas l'affectation d'une fonction sans placer la fonction entre parenthèses.

* +est conjugué techniquement complexe, mais l'entrée est réelle.

> <> avec l'option -v, 36 31 + 2 = 33 octets

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

Entrez la liste sur la pile avec -v afin que le premier élément de la liste se trouve en haut de la pile. Il imprimera la liste des objets avec un espace de fin.

Essai :

$ 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

Edit: 5 octets sauvegardés grâce à Fongoid

Python, 102 99 94 + 5 6 nouvelles lignes sans fichier = 107 105 100 octets

(J'ai utilisé des tabulations pour l'indentation)

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

Pas le meilleur sur le marché, mais c'est mon premier coup au code de golf. Impossible de trouver un moyen de trier la liste en ligne sans se heurter à des bogues liés à la suppression, j'ai donc déplacé les éléments commandés vers une liste temporaire.

EDIT: list.append () est plus court que la façon laide

r + = [i] était plus court que list.append (); merci njzk2 !

Scala: 232 126 120 octets

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

Scala, 54 octets

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

Lisp minuscule, 107 octets

( Cette langue n’a été publiée qu’après cette question. Cette réponse est donc hors compétition. Elle n’a eu aucune chance de gagner. La langue a ensuite évolué pour avoir plus de versions que celles que j’avais utilisées ici, mais je reste avec le la version que j’avais initialement mise en oeuvre en 2015. Cette réponse fonctionne toujours avec le plus récent interpréteur officiel , bien qu’elle donne quelques avertissements car je définis un paramètre aqui masque la nouvelle construction a(pour l’ajout). _{Merci à DLosc pour le lien TIO.} )

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

Ceci définit une fonction ds(et sa fonction d'assistance récursive r) qui trie son argument, qui doit être une liste d'entiers.

r n’est pas une fonction récursive, donc pour les très longues listes, cela peut entraîner un débordement de pile.

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

Voici quelques exemples d'utilisation (avec les cas de test de la question):

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

(Ouais, ce -7n'est pas un littéral entier, nous devons donc définir une fonction pour les représenter.) Résultat:

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)

Gelée, 5 octets

=»\Tị

Notez que le défi est antérieur à la création de Jelly.

Essayez-le en ligne!

Comment ça fonctionne

=»\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.

Mathematica, 27 octets

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