Tri avec perte (Implement Dropsort)

61

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>

SuperJedi224
la source
1
Est le chèque highest < current? Ou highest <= current?
Morgan Thrapp
7
Conservez l'élément actuel si highest (so far)<=current.
SuperJedi224
Pouvons-nous supposer qu’il y aura au moins un élément dans la liste?
lirtosiast
@ThomasKwa: Oui.
SuperJedi224
19
L’efficacité accrue de Dropsorts pourrait permettre à une entreprise d’économiser beaucoup d’argent si elle était utilisée dans le système de paie.
PyRulez

Réponses:

42

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.

lirtosiast
la source
41
Des points bonus parce que ça a l'air mignon.
Sammitch
22
Code ressemble à un mec mécontent qui tire sur une chatière
bière
2
Je ne sais pas grand chose au sujet du comptage d'octets et du codage à utiliser, mais selon mothereff.in/byte-counter et meta.codegolf.stackexchange.com/questions/4944/…, il s'agit de 17 octets, et bytesizematters. com il est 13.
DLeh
3
@DLeh C'est en UTF-8. APL a son propre codage hérité qui consiste en un octet par caractère APL, à partir de la date où l'unicode n'existait pas.
isaacg
3
@DLeh bytesizematters utilise un algorithme constitué pour compter les octets, ce qui ne correspond pas (et ne peut pas ) correspondre à un codage réel.
Dennis
21

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:

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

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

Xnor
la source
Pourquoi ne pas curry le lambda? Devrait sauver quelques caractères ...
MathematicalOrchid
@ MathematicalOrchid Si vous voulez dire foldr(\x->(x:).filter(>=x))[], cela s'avère être de la même longueur.
xnor
Ah Je viens de voir le filtre à la fin et je me suis dit: "Hé, tu peux le curry!" Je ne me suis pas rendu compte que cela x:vous oblige à ajouter l'opérateur de points. Oh bien ...
MathematicalOrchid
1
c'est O(n^2)bien. beaucoup de comparaisons inutiles. ;-(
fier haskeller
Pourquoi ne pas changer (> = x) en (x <)? Il va économiser 1 octet
Antisthenes
10

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
feersum
la source
1
Ceci est incroyable.
Morgan Thrapp
1
@ThomasKwa Le problème est de savoir comment arrêter les appels récursifs. Vous avez besoin du cas vide même si l'entrée exclut ce cas.
Bakuriu
Le problème, c'est que ce n'est pas linéaire à cause demax(a)
njzk2
1
@ njzk2 Le défi ne nécessite pas que les implémentations s'exécutent en temps linéaire.
Feersum
3
@ njzk2 Les codes de Nice finissent en dernier!
Feersum
10

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>

edc65
la source
Sensationnel. Je pensais que 38 octets était à peu près le meilleur possible; apparemment j'avais très tort. +1
ETHproductions
Tests pilotés par table. Agréable!
Slebetman
8

Octave, 27 19 octets

@(a)a(cummax(a)==a)
Alephalpha
la source
7

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.
Dennis
la source
7

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.

ais523
la source
6

Mathematica, 26 octets

DeleteDuplicates[#,#>#2&]&
celtschk
la source
2
Je ne sais pas Mathematica, mais quelque chose qui appelle DeleteDuplicatesne ressemble pas à elle retournerait {10, 10, 10, 10}pour l' entrée{10, 10, 10, 9, 10}
Dennis
2
@ Dennis: Oui, je l'ai testé. Le truc, c'est que je réussisse le test "est supérieur à" en tant que test "d'équivalence". Oui, c'est une mauvaise utilisation de cette fonction, mais cela fonctionne, et le code de golf ne correspond pas exactement aux meilleures pratiques de programmation.
celtschk
2
OK, malgré ce que suggère le nom, DeleteDuplicatesavec deux arguments semble être un simple filtre.
Dennis
5

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!

Alex A.
la source
La forme de la fonction serait plus courte.
Flodel
@flodel Vous avez absolument raison. Merci!
Alex A.
4

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)
JohnE
la source
{x@&~<':x}est un octet plus court.
Kirbyfan64sos
@ kirbyfan64sos: L'utilisation de chaque priorité ne donne pas le résultat correct. Considérons le cas d'entrée 3 4 2 2 5.
JohnE
Ah, je vois. Un correctif serait {x@&~<':x}/, mais c'est la même longueur.
Kirbyfan64sos
3

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.

Géobits
la source
1
Vous pouvez le raccourcir en utilisant un lambda:a->{int m=a[0]...
Daniel M.
Oui, vous pouvez généralement. Je ne lambda-ize pas java golfs, cependant.
Geobits
3

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
Dom Hastings
la source
3

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)
Morgan Thrapp
la source
62 octets
movatica
3

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
Alephalpha
la source
1
Vous pouvez remplacer l’un de vos jeux de parenthèses par un $à un octet entier! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Point-virgule utilisé parce que les commentaires n'autorisent pas les retours à la ligne)
Jake
3

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 à ToList1 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?

theB
la source
Si je compte mal, ou si mon explication nécessite des explications, faites-le moi savoir. :)
theB
1
Beau travail - vous pouvez économiser quelques octets en utilisant quelques astuces courantes - vous n'avez pas besoin d'espaces après les déclarations de tableaux int[]f(int[]b), et vous pouvez utiliser i<1plutôt que i==0de raccourcir un peu cette vérification. Pour la version chaîne, vous pouvez également supprimer les crochets autour d'un seul argument dans un lambda (par exemple, (d)=>int.Parse(d)peut être d=>int.Parse(d). Je ne compte également que 67 octets, et non 68 dans votre original;)
VisualMelon
@VisualMelon - Merci! Je pensais que toute erreur de calcul augmenterait le total. ;)
theB
3

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.
Dennis
la source
3

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 = $_
}
mazzy
la source
2

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.

Développeur de jeu
la source
4
Désolé, l'en-tête personnalisé n'est pas autorisé. cela compterait comme une langue différente.
lirtosiast
4
Le principal problème de vos en-têtes personnalisés est que vous les avez publiés après le début du concours.
Dennis
Bien sûr, je comprends, mais je ne peux pas l'utiliser non plus lors de compétitions futures?
GameDeveloper
@DarioOO Vous pouvez le faire, mais vous seriez obligé d'inclure la déclaration d'importation dans votre nombre d'octets.
SuperJedi224
Ou appelez-le simplement une nouvelle langue.
CalculatriceFeline
2

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

Mroman
la source
Oui, mais dans ce cas, je ne peux pas créer de lien hypertexte :).
dimanche
fixé. Je vais simplement ajouter une ligne "essayer en ligne ici".
dimanche
2

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.
El'endia Starman
la source
2

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]
homme au travail
la source
1
-[p]est plus court que.compact
Pas que Charles
Oops. Bien sûr. Je vous remercie. (Note à moi-même: il ne suffit pas de remonter le [lien codegolf.stackexchange.com/questions/363/… pour le golf en Ruby [/ link], je devrais aussi les mémoriser.)
Manatwork
2

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.

lirtosiast
la source
Alors, pourquoi codegolf.stackexchange.com/questions/61808/… ne s'applique- t-il pas ici non plus?
Chat
NARS2000 ne peut pas utiliser les codages APL hérités - et même avant la règle voulant que les encodages soient ceux réellement utilisés par les interprètes, il ne pouvait pas s'agir de 7 octets, car psi ne fait partie d'aucun codage APL hérité.
lirtosiast
2

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

Aaron
la source
Vous pouvez économiser 5 octets en refacturant la ligne 1 en tant :&\o" "&n:~& <que ligne 2 en tant que~ >l?!;:&:&(?!^
Fongoid
@Fongoid Merci, mis à jour!
Aaron
2

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 !

James Murphy
la source
r + = [i] est plus court que r.append
njzk2
J'ai déjà essayé de le faire, mais j'ai eu une erreur parce que je n'avais pas réalisé que vous deviez le faire avec des crochets. Merci!
James Murphy
2

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
Martin Seeler
la source
2
L'ajout d'une "méthode d'extension" pour List[Int]ne répond pas aux exigences, vous devez obtenir l'entrée via STDIN ou sous forme d'argument. De plus, cela gonfle votre réponse ... Pourquoi ne pas simplement l'avoir def dropSort(s:Seq[Int]):Seq[Int]?
Jacob
Je pensais que ce serait fantastique, mais vous avez raison, beaucoup trop d'octets ...
Martin Seeler
1
Très belle amélioration en utilisant fold! Vous pouvez toujours raser certains espaces et vous pouvez également utiliser y> = plutôt que _ <= y, ce qui génère un avertissement de compilation sans importation appropriée, mais montre également à quel point Scala est génial (oh, et supprime un autre personnage).
Jacob
Thx pour le bout!
Martin Seeler
2

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)
  }
Knutwalker
la source
2

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)
Paŭlo Ebermann
la source
"-7 n'est pas un littéral entier" Je ris encore, +1
Cat
Avez-vous vraiment utilisé chaque caractère pour les commandes intégrées? (Sauf r, je suppose ..)
CalculatriceFeline
@CatsAreFluffy désolé, j'ai du mal à comprendre votre commentaire. Tiny Lisp a 7 fonctions intégrées et trois macros intégrées, toutes portant un nom de caractère unique (pour rendre le langage plus facile à utiliser pour le golf), les parenthèses et l’espace constituant une syntaxe spéciale. Notez que Tiny Lisp n'est pas mon invention.
Paŭlo Ebermann
Ah, je pense que je comprends maintenant ... vous proposez d'utiliser un nom à caractère unique au lieu de ds? Je suppose que cela pourrait être fait, permettrait d'économiser un autre octet. Je suppose que j'ai choisi dscomme abréviation de drop sort.
Paŭlo Ebermann
Hey, je viens de remarquer ça. Bon travail! Selon le méta-consensus, les fonctions lambda non nommées sont une forme de soumission valide. Vous pouvez ainsi économiser 6 octets en supprimant (d dsles éléments correspondants )à la fin. D'autres golfs sont possibles si vous souhaitez utiliser mon interprète actuel , mais si vous souhaitez vous en tenir aux spécifications de la question initiale, c'est très bien aussi. :)
DLosc
2

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.
Dennis
la source
1

Mathematica, 27 octets

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