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>
code-golf
array-manipulation
sorting
SuperJedi224
fonte
fonte
highest < current
? Ouhighest <= current
?highest (so far)<=current
.Respostas:
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.
fonte
J,
109 bytesVersão de trabalho da minha ideia CJam (em menos bytes). Por exemplo:
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
:fonte
Haskell, 28
Uma função anônima. Chame como
Equivalente à recursão
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<)
.fonte
foldr(\x->(x:).filter(>=x))[]
, isso tem o mesmo comprimento.x:
você o força a adicionar o operador de ponto. Oh, bem ...O(n^2)
embora. muitas comparações desnecessárias. ;-(Python 2, 49
fonte
max(a)
JavaScript (ES6), 29
Abuso da conversão de tipo padrão em javascript, matriz para número:
fonte
Oitava,
2719 bytesfonte
Pitão, 12 bytes
Verifique todos os casos de teste de uma só vez.
Como funciona
fonte
Braquilog , 5 bytes
Experimente online!
Gelatina , 5 bytes
Experimente online!
Explicação
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.
fonte
Mathematica, 26 bytes
fonte
DeleteDuplicates
não parece que retornaria{10, 10, 10, 10}
para entrada{10, 10, 10, 9, 10}
DeleteDuplicates
com dois argumentos parece ser um filtro simples.R,
2926 bytesIsso cria um objeto de função que aceita um vetor
x
e retornax
após remover todos os elementos não pelo menos tão grandes quanto o máximo acumulado dex
.Economizou 3 bytes graças ao flodel!
fonte
K, 11 bytes
Em ação:
fonte
{x@&~<':x}
é um byte mais curto.3 4 2 2 5
.{x@&~<':x}/
, mas esse é o mesmo comprimento.Java, 82 bytes
Aqui está um loop de saída simples. Ele apenas mantém o máximo
m
e compara cada elemento.fonte
a->{int m=a[0]...
Perl, 33 bytes
Código de 32 bytes
-p
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) viaSTDIN
:fonte
Python 3, 67
Força bruta. Alterei para uma função, porque perdi que era uma resposta válida.
Versão não destruída:
fonte
Haskell,
3837 bytesEconomizou 1 byte graças ao JArkinstall .
fonte
$
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)C # -
6864 ou132127 caracteresWhere
nesse caso, está percorrendo a lista e, para cada elementov
no índicei
da 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 aIndexOutOfRangeException
exceçã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).
Descomprimir um pouco dá:
Nesse caso, a segunda linha da função está usando exatamente a mesma lógica que acima. Ele
Select
pega os elementos da lista e os converte emint
. A chamada paraToList
1 força a seleção a ser avaliada e a transformavar
emList<int>
em tempo de compilação, para queWhere
esteja 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?
fonte
int[]f(int[]b)
estiverem corretas e pode usar, emi<1
vez dei==0
reduzir 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 serd=>int.Parse(d)
que eu também só contam 67 bytes, e não 68, na sua orignal;.)CJam, 15 bytes
Experimente online no intérprete CJam .
Como funciona
fonte
PowerShell , 32 bytes
Experimente online!
Menos golfe:
fonte
C: 73 bytes
ou
C: 49 bytes
(Se for permitido o cabeçalho aduaneiro criado para competições de codegolf)
Ainda não consegue vencer o CJam, mas pelo menos isso permite vencer alguns outros idiomas.
fonte
Burlesco, 13 bytes
Solução de 11 bytes que passa nos casos de teste:
Experimente online aqui .
Explicação:
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:
Experimente online aqui. Explicação:
Se você também soltar números iguais, poderá usar apenas em
.>
vez de usarcm
. Além disso, se as listas contiverem apenas números positivos, você poderá usar0
ou em-1
vez deJ-]
.fonte
Tamanho 0.9 , 18 bytes
Experimente aqui.
Explicação
fonte
Ruby,
4137 caracteresExemplo de execução:
fonte
-[p]
é mais curto que.compact
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.fonte
> <> com sinalizador -v,
3631 + 2 = 33 bytesInsira 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:
Edit: salvou 5 bytes graças ao Fongoid
fonte
:&\o" "&n:~& <
e a linha 2 como~ >l?!;:&:&(?!^
Python,
1029994 +56 novas linhas sem final de arquivo =107105100 bytes(Eu usei guias para recuo)
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 !
fonte
Nota:
232126120 bytesfonte
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 simplesmentedef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 bytes
Ungolfed:
fonte
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
a
que obscurece o novo buildina
(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 recursivar
) 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:
Aqui estão alguns exemplos de como usar isso (com os casos de teste da pergunta):
(Sim,
-7
não é um literal inteiro, portanto, temos que definir uma função para representá-los.)fonte
r
, eu acho ..)ds
? Eu acho que isso poderia ser feito, salvaria outro byte. Acho que selecioneids
como uma abreviação de gota.(d ds
e 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. :)Gelatina, 5 bytes
Observe que o desafio antecede a criação do Jelly.
Experimente online!
Como funciona
fonte
Mathematica, 27 bytes
fonte