Dropsort , diseñado por David Morgan-Mar, es un ejemplo de un "algoritmo de clasificación" de tiempo lineal que produce una lista que, de hecho, está ordenada, pero contiene solo algunos de los elementos originales. Cualquier elemento que no sea al menos tan grande como el máximo de los elementos que lo preceden simplemente se elimina de la lista y se descarta.
En esta tarea, se le dará una lista de enteros como entrada (STDIN o argumento de función, debe admitir al menos el rango de enteros con signo de 8 bits). Su tarea es clasificarlos y luego generar los elementos restantes en orden.
Puede suponer que la lista no está vacía.
Este es el código de golf, por lo que gana el programa más corto.
Casos de prueba
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
Tabla de clasificación
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
fuente
fuente
highest < current
? Ohighest <= current
?highest (so far)<=current
.Respuestas:
APL, 9 bytes
Este es un tren de funciones monádicas con diagrama:
La versión sin tren es
Básicamente, esto verifica si cada elemento es igual al máximo de ejecución.
Tenga en cuenta que la solución J de Martin Büttner tiene la misma longitud que esta y se publicó primero.
fuente
J,
109 bytesVersión de trabajo de mi idea de CJam (en menos bytes). P.ej:
Explicación
Primero, obtenemos el máximo de cada prefijo, con:
(Aquí,
>.
es el operador máximo,/
dobla ese operador en una lista y\
obtiene todos los prefijos de la entrada).Luego comparamos la lista inicial con esos máximos para la igualdad:
Y finalmente, seleccionamos todos los elementos donde esta lista de resultados booleanos dio un
1
:fuente
Haskell, 28
Una función anónima. Llámalo como
Equivalente a la recursividad.
Traducido iterativamente, iteramos sobre los elementos, y para cada uno que vemos, eliminamos los más pequeños del resto de la lista sobre la que estamos iterando. Gracias a Antisthenes por un byte guardado con
(x<)
.fuente
foldr(\x->(x:).filter(>=x))[]
, resulta ser de la misma longitud.x:
te obliga a agregar el operador de punto. Oh, bueno ...O(n^2)
sin embargo. muchas comparaciones innecesarias. ;-(Pitón 2, 49
fuente
max(a)
JavaScript (ES6), 29
Abuso de la conversión de tipo estándar en javascript, matriz a número:
fuente
Octava,
2719 bytesfuente
Pyth, 12 bytes
Verifique todos los casos de prueba a la vez.
Cómo funciona
fuente
Brachylog , 5 bytes
Pruébalo en línea!
Jalea , 5 bytes
Pruébalo en línea!
Explicación
Esta es una situación rara: puedo usar un algoritmo que (por lo que pude ver con un descremado rápido) que nadie está usando hasta ahora, y de alguna manera termina la misma longitud en dos idiomas de golf muy diferentes con una sintaxis muy diferente y conjuntos integrados, con una correspondencia 1 a 1 entre los programas (¡los comandos están incluso en el mismo orden!). Así que parecía tener más sentido combinarlos, en cierto modo, son el mismo programa, y lo escribí en ambos idiomas para ver cuál era más corto, que enviarlos por separado.
La idea básica aquí es que el dropsort de una lista es su subsecuencia con el reverso lexicográfico máximo. Curiosamente, ni Brachylog ni Jelly tienen una función integrada para encontrar el máximo por una función en particular (Jelly tiene una función integrada para devolver todos los máximos por una función en particular, pero eso devolvería una lista única que contiene el resultado en lugar del resultado mismo, y tampoco es más corto que hacerlo de esta manera). Entonces, en cambio, generamos todas las subsecuencias posibles, ordenamos por reversa, tomamos la última.
La razón por la que funciona el "reverso máximo lexicográficamente" es que la salida elegida debe terminar (por lo tanto, su reversa debe comenzar) con el número más alto en la lista de entrada (es fácil ver que la salida de dropsort siempre terminará con eso), y así puede No contiene nada después de eso (porque tomar subsecuencias preserva el orden). Repita inductivamente y terminamos con la definición de dropsort.
fuente
Mathematica, 26 Bytes
fuente
DeleteDuplicates
no parece que regrese{10, 10, 10, 10}
como entrada{10, 10, 10, 9, 10}
DeleteDuplicates
con dos argumentos parece ser un filtro simple.R,
2926 bytesEsto crea un objeto de función que acepta un vector
x
y regresax
después de eliminar todos los elementos que no sean al menos tan grandes como el máximo acumulado dex
.¡Guardado 3 bytes gracias a flodel!
fuente
K, 11 bytes
En acción:
fuente
{x@&~<':x}
Es un byte más corto.3 4 2 2 5
.{x@&~<':x}/
, pero esa es la misma longitud.Java, 82 bytes
Aquí hay un bucle de salida simple. Simplemente mantiene el máximo
m
y compara cada elemento.fuente
a->{int m=a[0]...
Perl, 33 bytes
Código de 32 bytes +
-p
Si los espacios adicionales son aceptables en la salida, pueden ser 31 bytes al eliminar
y
?
. Acepta una cadena (o número de cadenas separadas por nueva línea) a través deSTDIN
:fuente
Pitón 3, 67
Bastante fuerza bruta. Lo cambié a una función, porque omití que era una respuesta válida.
Versión sin golf:
fuente
Haskell,
3837 bytesGuardado 1 byte gracias a JArkinstall .
fuente
$
recorte por un byte completo!f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s
(Se utiliza punto y coma porque los comentarios no permiten nuevas líneas)C# -
6864 o132127 caracteresWhere
en este caso está iterando por la lista, y para cada elementov
en el índicei
de la lista, evalúa la expresión booleana. Si la expresión se evalúa como verdadera, entonces el elemento se agrega al resultado. El único truco real para la expresión booleana es que C # cortocircuitos o evaluación tan pronto como una condición se evalúa como verdadera. Esto evita laIndexOutOfRangeException
excepción y mantiene el primer elemento en la lista.Si la entrada y la salida tienen que ser cadenas (no podría asegurarlo, así que lo dejaré al OP y al resto de ustedes para que decidan).
Descomprimir eso da un poco:
En este caso, la segunda línea de la función está utilizando exactamente la misma lógica que la anterior. Los
Select
agarra los elementos de la lista y convierte aint
. La llamada aToList
1 obliga a la selección a ser evaluada, y la conviertevar
en unaList<int>
en tiempo de compilación, de modo queWhere
está operando en una colección de enteros.Pruébalo en C # Pad
Gracias a VisualMelon por ayudar a recortar 4 bytes y 5 bytes respectivamente. :)
1 lista de tutú?
fuente
int[]f(int[]b)
bien, y puede usar eni<1
lugar dei==0
acortar un poco esa verificación. Para la versión de cadena, también puede colocar los corchetes alrededor de un argumento único en un lambda (por ejemplo,(d)=>int.Parse(d)
puede serd=>int.Parse(d)
. También solo cuento 67 bytes, no 68, en su original;)CJam, 15 bytes
Pruébelo en línea en el intérprete de CJam .
Cómo funciona
fuente
PowerShell , 32 bytes
Pruébalo en línea!
Menos golfizado:
fuente
C: 73 bytes
o
C: 49 bytes
(Si se permite el encabezado de aduanas para competiciones de codegolf)
Todavía no puede vencer a CJam, pero al menos esto permite vencer a algunos otros idiomas.
fuente
Burlesque, 13 bytes
Solución de 11 bytes que pasa los casos de prueba:
Prueba en línea aquí .
Explicación:
Sin embargo, esta versión solo funciona utilizando el hecho de que no hay dos números más pequeños entre dos números. De lo contrario, use la versión a continuación (que es 13B):
Versiones mas antiguas:
Prueba en línea aquí. Explicación:
Si también elimina números iguales, podría
.>
usar solo en lugar de usarcm
. Además, si las listas solo contienen números positivos, puede usar cualquiera0
o en-1
lugar deJ-]
.fuente
Minkolang 0.9 , 18 bytes
Pruébalo aquí
Explicación
fuente
Ruby,
4137 caracteresEjecución de muestra:
fuente
-[p]
es más corto que.compact
NARS2000 APL, 13 bytes
NARS2000 es un intérprete APL gratuito para Windows; incluye funciones de múltiples conjuntos a las que se accede con el
⍦
operador.Esta es una bifurcación monádica que toma la intersección de múltiples conjuntos (
⍦∩
) de la entrada (+
) * y la lista de máximos de ejecución (⌈\
).Como
⍦
no es un carácter APL estándar en las codificaciones heredadas de APL de un byte, debemos usar UTF-8, lo que hace que los⍦∩⌈
caracteres sean de tres bytes cada uno. Elegí en+
lugar de⊢
guardar dos bytes.NARS2000 admite horquillas, que pueden integrarse en trenes sin paréntesis, pero a diferencia de Dyalog, no permite la asignación de una función sin incluir la función entre paréntesis.
*
+
es un conjugado técnicamente complejo, pero la entrada es real.fuente
> <> con la bandera -v,
3631 + 2 = 33 bytesIngrese la lista en la pila con -v para que el primer elemento de la lista esté en la parte superior de la pila. Imprimirá la lista ordenada con un espacio final.
Prueba de funcionamiento :
Editar: guardado 5 bytes gracias a Fongoid
fuente
:&\o" "&n:~& <
y la línea 2 como~ >l?!;:&:&(?!^
Python,
1029994 +56 líneas nuevas no finales de archivo =107105100 bytes(Usé pestañas para sangrar)
No es el mejor que existe, pero esta es mi primera oportunidad de jugar golf en código. No se pudo encontrar una manera de ordenar la lista en línea sin encontrarse con errores relacionados con la eliminación, por lo que moví los elementos ordenados a una lista temporal.
EDITAR: list.append () es más corto que hacerlo de la manera fea
r + = [i] era más corto que list.append (); gracias njzk2 !
fuente
Scala:
232126120 bytesfuente
List[Int]
no cumple con los requisitos, debe obtener la entrada a través de STDIN o como argumento. Además, hincha tu respuesta ... ¿Por qué no simplemente tenerdef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 bytes
Sin golf:
fuente
Tiny Lisp, 107 bytes
( Este lenguaje solo se publicó después de esta pregunta, por lo que esta respuesta se queda sin competencia. No es que tuviera ninguna oportunidad de ganar. El lenguaje más tarde evolucionó aún más para tener más buildins que los que usé aquí, pero me quedo con el versión que implementé originalmente en 2015. Esta respuesta aún funciona con el nuevo intérprete oficial , aunque da algunas advertencias porque defino un parámetro
a
que sombrea el nuevo buildina
(para agregar). Gracias a DLosc por el enlace 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)))()))))
Esto define una función
ds
(y su función auxiliar recursivar
) que clasifica su argumento, que debe ser una lista de enteros.r
no es una función recursiva de cola, por lo que para listas muy largas esto podría generar un desbordamiento de pila.Sin golf:
Aquí hay algunos ejemplos de cómo usar esto (con los casos de prueba de la pregunta):
(Sí,
-7
no es un literal entero, por lo que tenemos que definir una función para representarlos). Salida:fuente
r
, supongo ...)ds
? Supongo que esto podría hacerse, ahorraría otro byte. Supongo que seleccionéds
como abreviatura para ordenar por caída.(d ds
la coincidencia)
al final. Son posibles otros campos de golf si desea utilizar mi intérprete actual , pero si desea cumplir con las especificaciones de la pregunta original, también está bien. :)Jalea, 5 bytes
Tenga en cuenta que el desafío es anterior a la creación de Jelly.
Pruébalo en línea!
Cómo funciona
fuente
Mathematica, 27 bytes
fuente