Classificação com perdas (Implementar Dropsort)

61

O Dropsort , projetado por David Morgan-Mar, é um exemplo de um "algoritmo de classificação" de tempo linear que produz uma lista que é, de fato, classificada, mas contém apenas alguns dos elementos originais. Qualquer elemento que não seja pelo menos tão grande quanto o máximo dos elementos anteriores é simplesmente removido da lista e descartado.

Nesta tarefa, você receberá uma lista de números inteiros como entrada (STDIN ou argumento de função, é necessário oferecer suporte a pelo menos o intervalo de números inteiros assinados de 8 bits.) ordem.

Você pode assumir que a lista não está vazia.

Isso é código de golfe, então o programa mais curto vence.

Casos de teste

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

Entre os melhores

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
fonte
11
É o cheque highest < current? Ou highest <= current?
Morgan Thrapp 26/10/2015
7
Mantenha o elemento atual se highest (so far)<=current.
SuperJedi224
Podemos assumir que haverá pelo menos um elemento na lista?
lirtosiast
@ThomasKwa: Sim.
SuperJedi224
19
A eficiência aprimorada do Dropsorts pode economizar muito dinheiro para uma empresa se utilizada no sistema de folha de pagamento.
PyRulez 26/10/2015

Respostas:

42

APL, 9 bytes

⊢(/⍨)⊢=⌈\

Este é um trem de função monádico com diagrama:

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

A versão não-trem é

{⍵/⍨⍵=⌈\⍵}

Isso basicamente verifica se cada elemento é igual ao máximo em execução.

Observe que a solução J de Martin Büttner tem o mesmo comprimento e foi publicada primeiro.

lirtosiast
fonte
41
Pontos de bônus porque parece bonito.
Sammitch 26/10/2015
22
Código se parece com um cara descontente atirando em uma aleta do gato
slebetman
2
Eu não sei muito sobre a contagem de bytes e qual codificação deve ser usada, mas de acordo com mothereff.in/byte-counter e meta.codegolf.stackexchange.com/questions/4944/… são 17 bytes e bytesizematters. com 13.
DLeh 28/10
3
@DLeh Isso está em UTF-8. O APL possui sua própria codificação herdada de 1 by per caracter APL, antes da existência do unicode.
Isaacg #
3
@DLeh bytesizematters usa um algoritmo inventado para contar os bytes, o que não corresponde (e não pode ) a uma codificação real.
Dennis
21

J, 10 9 bytes

#~(=>./\)

Versão de trabalho da minha ideia CJam (em menos bytes). Por exemplo:

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

Explicação

Primeiro, obtemos o máximo de cada prefixo com:

    >./\

(Aqui, >.é o operador máximo, /dobra esse operador em uma lista e \obtém todos os prefixos da entrada.)

Em seguida, comparamos a lista inicial com os máximos de igualdade:

  (=>./\)

E, finalmente, selecionamos todos os elementos em que essa lista de resultados booleanos deu 1:

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

Haskell, 28

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

Uma função anônima. Chame como

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

Equivalente à recursão

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

Traduzido iterativamente, iteramos sobre os elementos e, para cada um que vemos, removemos os menores do restante da lista sobre a qual estamos iterando. Obrigado a Antisthenes por um byte salvo com (x<).

xnor
fonte
Por que não curry o lambda? Você deve salvar alguns caracteres ... #
MathematicsOrchid
@MathematicalOrchid Se você quer dizer foldr(\x->(x:).filter(>=x))[], isso tem o mesmo comprimento.
Xnor
Ah Acabei de ver o filtro no final e pensei "ei, você pode curry isso!" Não me ocorreu que x:você o força a adicionar o operador de ponto. Oh, bem ...
MathematicalOrchid
11
é O(n^2)embora. muitas comparações desnecessárias. ;-(
haskeller orgulhoso
Por que não mudar (> = x) para (x <)? Ele salvará 1 byte
Antisthenes
10

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
feersum
fonte
11
Isso é incrível.
Morgan Thrapp 26/10/2015
11
@ThomasKwa O problema é como você interrompe as chamadas recursivas. Você precisa do caso vazio, mesmo que a entrada exclua esse caso.
Bakuriu 27/10/2015
problema com isso é que não é linear por causa demax(a)
njzk2
11
@ njzk2 O desafio não exige que as implementações sejam executadas em tempo linear.
feersum
3
@ njzk2 Códigos agradáveis ​​terminam por último!
feersum
10

JavaScript (ES6), 29

Abuso da conversão de tipo padrão em javascript, matriz para número:

  • matriz de apenas 1 número => esse número
  • qualquer outra matriz => 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
fonte
Uau. Eu pensei que 38 bytes era aproximadamente o melhor possível; aparentemente eu estava muito errado. +1
ETHproductions
Testes guiados por tabela. Agradável!
Slebetman 27/10/2015
8

Oitava, 27 19 bytes

@(a)a(cummax(a)==a)
alefalpha
fonte
7

Pitão, 12 bytes

eMfqeTeST._Q

Verifique todos os casos de teste de uma só vez.

Como funciona

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

Braquilog , 5 bytes

⊇ᶠ↔ᵒt

Experimente online!

Gelatina , 5 bytes

ŒPUÞṪ

Experimente online!

Explicação

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

Essa é uma situação rara: eu uso um algoritmo que (até onde eu poderia dizer com um toque rápido) que ninguém está usando até agora, e de alguma forma acaba com o mesmo comprimento em duas linguagens de golfe muito diferentes, com sintaxe e sintaxe muito diferentes. conjuntos embutidos, com uma correspondência 1 para 1 entre os programas (os comandos estão na mesma ordem!). Portanto, parecia fazer mais sentido combiná-los - de certa forma, esses são o mesmo programa, e eu o escrevi nos dois idiomas para ver qual era mais curto - do que enviá-los separadamente.

A idéia básica aqui é que o droport de uma lista é sua subsequência com o reverso lexicograficamente máximo. Estranhamente, nem Brachylog nem Jelly têm um builtin para encontrar o máximo de uma função específica (Jelly tem um builtin para retornar todos os máximos de uma função específica, mas isso retornaria uma lista única contendo o resultado e não o resultado em si; e também não é nem mais curto do que fazer dessa maneira). Então, em vez disso, geramos todas as subsequências possíveis, classifique por reverso, pegue a última.

A razão pela qual o "reverso lexicograficamente máximo" funciona é que a saída escolhida deve terminar (portanto, sua reversão deve começar) com o número mais alto na lista de entradas (é fácil ver que a saída do dropsort sempre termina com isso) e, portanto, pode conterá qualquer coisa depois disso (porque as subsequências preservam a ordem). Repita indutivamente e terminamos com a definição de dropsort.

ais523
fonte
6

Mathematica, 26 bytes

DeleteDuplicates[#,#>#2&]&
celtschk
fonte
2
Eu não conheço o Mathematica, mas algo que chama DeleteDuplicatesnão parece que retornaria {10, 10, 10, 10}para entrada{10, 10, 10, 9, 10}
Dennis
2
@ Dennis: Sim, eu testei. O truque é que eu passe "é maior que" como teste de "equivalência". Sim, é um uso indevido dessa função, mas funciona, e o código golf não é exatamente sobre as melhores práticas de programação.
Celtschk 27/10/2015
2
OK, apesar do que o nome sugere, DeleteDuplicatescom dois argumentos parece ser um filtro simples.
Dennis
5

R, 29 26 bytes

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

Isso cria um objeto de função que aceita um vetor xe retorna xapós remover todos os elementos não pelo menos tão grandes quanto o máximo acumulado de x.

Economizou 3 bytes graças ao flodel!

Alex A.
fonte
O formulário da função seria mais curto.
Fl
@flodel Você está absolutamente certo. Obrigado!
Alex A.
4

K, 11 bytes

{x@&~x<|\x}

Em ação:

  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
fonte
{x@&~<':x}é um byte mais curto.
kirbyfan64sos
@ kirbyfan64sos: Usar eachiorior não produz o resultado correto. Considere o caso de entrada 3 4 2 2 5.
Johne
Ah entendo. Uma correção seria {x@&~<':x}/, mas esse é o mesmo comprimento.
Kirbyfan64sos 26/10/2015
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;}}

Aqui está um loop de saída simples. Ele apenas mantém o máximo me compara cada elemento.

Geobits
fonte
11
Você pode reduzi-lo usando um lambda:a->{int m=a[0]...
Daniel M.
Sim, você geralmente pode. Eu não lambo-ize java golfs, no entanto.
Geobits 27/10/2015
3

Perl, 33 bytes

Código de 32 bytes -p

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

Se espaços adicionais forem aceitáveis ​​na saída, poderá ter 31 bytes removendo e ?. Aceita uma sequência de caracteres (ou número de novas linhas separadas) 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
fonte
3

Python 3, 67

Força bruta. Alterei para uma função, porque perdi que era uma resposta válida.

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

Versão não destruída:

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
fonte
62 bytes
movatica
3

Haskell, 38 37 bytes

Economizou 1 byte graças ao JArkinstall .

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s
alefalpha
fonte
11
Você pode substituir um de seus conjuntos de parênteses por um $para reduzir um byte inteiro! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Semi-colon usado porque comentários não permitem novas linhas)
Jake
3

C # - 6864 ou 132127 caracteres

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

Wherenesse caso, está percorrendo a lista e, para cada elemento vno índice ida lista, avalia a expressão booleana. Se a expressão for avaliada como verdadeira, o item será adicionado ao resultado. O único truque real para a expressão booleana é que os curtos-circuitos em C # ou avaliação assim que uma condição é avaliada como verdadeira. Isso evita a IndexOutOfRangeExceptionexceção e mantém o primeiro elemento na lista.

Se a entrada e a saída tiverem que ser strings (não sei ao certo, deixarei o OP e o resto de vocês decidirem).

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

Descomprimir um pouco dá:

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

Nesse caso, a segunda linha da função está usando exatamente a mesma lógica que acima. Ele Selectpega os elementos da lista e os converte em int. A chamada para ToList1 força a seleção a ser avaliada e a transforma varem List<int>em tempo de compilação, para que Whereesteja operando em uma coleção de números inteiros.

Experimente no C # Pad

Agradecemos ao VisualMelon por ajudar a aparar 4 e 5 bytes, respectivamente. :)

1 lista de tutu?

theB
fonte
Se eu contei mal, ou se minha explicação precisar de alguma explicação, entre em contato. :)
theB
11
Bom trabalho - você pode salvar alguns bytes usando alguns truques comuns - não precisa dos espaços depois que as declarações da matriz int[]f(int[]b)estiverem corretas e pode usar, em i<1vez de i==0reduzir um pouco essa verificação. Para a versão string, você também pode soltar os suportes em torno de um único argumento em um lambda (por exemplo, (d)=>int.Parse(d)pode ser d=>int.Parse(d)que eu também só contam 67 bytes, e não 68, na sua orignal;.)
VisualMelon
@VisualMelon - Thanks! Imaginei que qualquer contagem incorreta acabaria aumentando o total. ;)
theB
3

CJam, 15 bytes

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

Experimente online no intérprete CJam .

Como funciona

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

PowerShell , 32 bytes

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

Experimente online!

Menos golfe:

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

C: 73 bytes

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

ou

C: 49 bytes

(Se for permitido o cabeçalho aduaneiro criado para competições de codegolf)

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

Ainda não consegue vencer o CJam, mas pelo menos isso permite vencer alguns outros idiomas.

Desenvolvedor de jogos
fonte
4
Desculpe, o cabeçalho personalizado não é permitido. contaria como um idioma diferente.
lirtosiast
4
O principal problema com seus cabeçalhos personalizados é que você os publicou após o início desta competição.
Dennis
Claro que entendi, mas também não posso usá-lo em competições futuras?
GameDeveloper 27/10/2015
@DarioOO Você pode, mas seria necessário incluir a declaração de importação na contagem de bytes.
SuperJedi224
Ou apenas chame-o de um novo idioma.
CalculatorFeline
2

Burlesco, 13 bytes

Solução de 11 bytes que passa nos casos de teste:

-.2CO:so)[~

Experimente online aqui .

Explicação:

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

No entanto, esta versão funciona apenas usando o fato de que não há dois números menores entre dois números. Caso contrário, use a versão abaixo (que é 13B):

Versões mais antigas:

J-]{cm-1.>}LO

Experimente online aqui. Explicação:

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

Se você também soltar números iguais, poderá usar apenas em .>vez de usar cm. Além disso, se as listas contiverem apenas números positivos, você poderá usar 0ou em -1vez de J-].

mroman
fonte
Sim, mas não consigo fazer o link dele :).
mroman
fixo. Vou apenas adicionar uma linha "experimente online aqui".
26515 mroman #
2

Tamanho 0.9 , 18 bytes

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

Experimente aqui.

Explicação

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

Ruby, 41 37 caracteres

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

Exemplo de execução:

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]
homem a trabalhar
fonte
11
-[p]é mais curto que.compact
Não que Charles
Opa Claro. Obrigado. (Nota para mim mesma: não é suficiente para apenas upvote o [link codegolf.stackexchange.com/questions/363/... para jogar golfe em Ruby [/ link], eu também deve memorizá-los.)
manatwork
2

NARS2000 APL, 13 bytes

O NARS2000 é um intérprete de APL gratuito para Windows; inclui recursos de vários conjuntos acessados ​​com o operador.

(+⍦∩⌈\)

Este é um fork monádico que utiliza a interseção multiset ( ⍦∩) da entrada ( +) * e a lista dos máximos em execução ( ⌈\).

Como não é um caractere APL padrão nas codificações herdadas de APL de um byte, devemos usar UTF-8, tornando os ⍦∩⌈caracteres com três bytes cada. Eu escolhi em +vez de salvar dois bytes.

O NARS2000 suporta garfos, que podem ser construídos em trens sem parênteses, mas, diferentemente do Dyalog, ele não permite a atribuição de uma função sem colocar a função entre parênteses.

* +é conjugado tecnicamente complexo, mas a entrada é real.

lirtosiast
fonte
O NARS2000 não pode usar as codificações de APL herdadas - e mesmo antes da regra de que as codificações devem ser realmente usadas pelos intérpretes, isso não pode ter 7 bytes porque psi não faz parte de nenhuma codificação de APL herdada.
lirtosiast
2

> <> com sinalizador -v, 36 31 + 2 = 33 bytes

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

Insira a lista na pilha com -v para que o primeiro elemento da lista fique no topo da pilha. Ele imprimirá a lista com variações de espaço com um espaço à direita.

Execução de teste:

$ 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: salvou 5 bytes graças ao Fongoid

Aaron
fonte
Você pode salvar 5 bytes refatorando a linha 1 como :&\o" "&n:~& <e a linha 2 como~ >l?!;:&:&(?!^
Fongoid 27/10/15
@ Obrigado Fongoid, atualizado!
Aaron
2

Python, 102 99 94 + 5 6 novas linhas sem final de arquivo = 107 105 100 bytes

(Eu usei guias para recuo)

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

Não é o melhor lá fora, mas esta é a minha primeira chance no código de golfe. Não foi possível descobrir uma maneira de classificar a lista em linha sem encontrar erros relacionados à remoção, então mudei os elementos ordenados para uma lista temporária.

EDIT: list.append () é mais curto do que fazê-lo da maneira feia

r + = [i] era menor que list.append (); obrigado njzk2 !

James Murphy
fonte
r + = [i] está em curto que r.append
njzk2
Eu tentei fazer isso antes, mas recebi um erro porque não sabia que era preciso usar colchetes. Obrigado!
James Murphy
2

Nota: 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
fonte
2
A adição de um "método de extensão" para List[Int]não atende aos requisitos, você deve obter a entrada via STDIN ou como argumento. Além disso, incha sua resposta ... Por que não simplesmente def dropSort(s:Seq[Int]):Seq[Int]?
Jacob
Eu pensei que seria extravagante, mas você está certo, de forma demasiada bytes ...
Martin Seeler
11
Melhoria muito boa usando fold! Você ainda pode raspar alguns espaços e também pode usar y> = em vez de _ <= y, que gera um aviso de compilação sem uma importação adequada, mas também demonstra o quão impressionante é Scala (oh, e raspa outro personagem).
Jacob
Obrigado pela gorjeta!
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
fonte
2

Lisp minúsculo, 107 bytes

( Esse idioma foi publicado apenas após esta pergunta, portanto, esta resposta fica fora de competição. Não que tivesse chance de vencer. Mais tarde, o idioma evoluiu ainda mais para ter mais buildins do que os que usei aqui, mas continuarei com o versão que eu implementei originalmente em 2015. Essa resposta ainda funciona com o intérprete oficial mais recente , mas fornece alguns avisos porque eu defino um parâmetro aque obscurece o novo buildin a(para adição). Obrigado ao DLosc pelo link 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)))()))))

Isso define uma função ds(e sua função auxiliar recursiva r) que classifica seu argumento, que deve ser uma lista de números inteiros.

r não é uma função recursiva de cauda; portanto, para listas muito longas, isso pode ocorrer em um estouro de pilha.

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

Aqui estão alguns exemplos de como usar isso (com os casos de teste da pergunta):

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

(Sim, -7não é um literal inteiro, portanto, temos que definir uma função para representá-los.)

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)
Paŭlo Ebermann
fonte
"-7 não é um literal inteiro" Eu ainda estou rindo, +1
cat
Você realmente usou todos os personagens dos buildins? (Exceto r, eu acho ..)
CalculatorFeline22 /
@CatsAreFluffy Desculpe, estou com problemas para entender seu comentário. O Tiny Lisp possui 7 funções internas e três macros internas, todas com nomes de caracteres únicos (acho que para facilitar o uso do idioma no golfe), com parênteses e espaço sendo uma sintaxe especial. Note que Tiny Lisp não é minha invenção.
Pa Elo Ebermann 02/04
Ah, acho que entendi agora ... você está propondo usar um nome de caractere único em vez de ds? Eu acho que isso poderia ser feito, salvaria outro byte. Acho que selecionei dscomo uma abreviação de gota.
Pa Elo Ebermann 02/04
Ei, acabei de perceber isso. Bom trabalho! De acordo com o meta consenso, as funções lambda sem nome são uma forma válida de envio, para que você possa salvar 6 bytes se livrando (d dse correspondendo )no final. Outros campos de golfe são possíveis se você quiser usar o meu intérprete atual , mas se quiser manter as especificações na pergunta original, tudo bem também. :)
DLosc 02/02
2

Gelatina, 5 bytes

=»\Tị

Observe que o desafio antecede a criação do Jelly.

Experimente online!

Como funciona

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

Mathematica, 27 bytes

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