Como se describe en esta pregunta :
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.
Para utilizar una de sus casos de prueba, una entrada de {1, 2, 5, 4, 3, 7}
rendimientos {1, 2, 5, 7}
, como 4
y 3
están ambos cayó por ser más pequeño que el previamente "ordenados" valor, 5
.
No queremos algoritmos de "clasificación", queremos que sean el verdadero negocio. Por lo tanto, quiero que escriba un programa que, dada una lista de números, genere una lista de listas DropSorted (para ser un algoritmo de ordenación completo, necesitaríamos fusionar estas listas, pero antes se había fusionado dos listas ordenadas , y pedirle que lo vuelva a hacer es más o menos dos preguntas, por lo que esta pregunta es específicamente el paso de "división" de nuestro DropSort completo).
Sin embargo, la disposición y el contenido de nuestras listas es crucial. La salida de su programa debe ser equivalente a la salida de un DropSort, seguido de un DropSort de los valores descartados, y así sucesivamente hasta que solo tenga una lista de cadenas ordenadas. Nuevamente, tomando prestado el conjunto de pruebas existente (y agregando dos más):
Input -> Output
{1, 2, 5, 4, 3, 7} -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12} -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5} -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21} -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10} -> {{10, 10, 10, 10}, {9}} //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6} -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7} -> {{0, 2, 5, 7}, {4}, {0}}
Puede suponer que la entrada no está vacía.
Este es el código de golf , por lo que se aplican reglas estándar.
[5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]
?{3,4,5,3,4,5,3,4,5}
resultar en{{3,4,5,5,5},{3,4,4},{3}}
?Respuestas:
MATL ,
15109 bytes5 bytes de descuento utilizando la idea de @beaker del máximo acumulado
La entrada es un vector de fila numérico, en el formato
[1, 2, 5, 4, 3, 7]
(las comas son opcionales). La salida contiene listas separadas por nuevas líneas, con los números en cada lista separados por espacios.Pruébalo en línea! O verificar todos los casos de prueba .
Explicación
Dada una matriz, el código selecciona de cada entrada que iguala el máximo acumulado hasta esa entrada.
Por ejemplo, dado
El código selecciona las entradas primera, segunda, tercera y sexta:
Luego, el proceso se repite en el subconjunto formado por las entradas restantes (en el orden original):
Esto debe hacerse hasta que el subconjunto de entradas restantes esté vacío. Un límite superior en el número requerido de iteraciones es el tamaño de entrada. Las últimas iteraciones pueden no ser necesarias. En ese caso, operan en una matriz vacía, produciendo matrices vacías adicionales.
Al final, la pila contiene las matrices requeridas y posiblemente varias matrices vacías, que no se muestran en absoluto.
fuente
Haskell,
67 5958 bytesExplicación: Dada una lista de listas (que ya están ordenadas) y un valor
x
, el!
operador colocaráx
al final de la primera lista cuyo último elemento es menor o igual quex
. Si no existe dicha lista, la lista[x]
se coloca al final.Pruébalo en línea.
fuente
Casco , 10 bytes
Pruébalo en línea!
Esta es una combinación de mi otra respuesta de Husk y la respuesta de Haskell de xnor . El duplicado se
ü<
siente torpe, pero no sé cómo deshacerme de él ...Explicación
La función se
ü<
traduce ennubBy(>)
en Haskell. Atraviesa una lista de izquierda a derecha, manteniendo aquellos elementos para los cuales ningún elemento previamente guardado es estrictamente mayor. En otras palabras, realiza dropsort. Los elementos sobrantes se obtienen tomando la diferencia de lista de la lista original y el resultado deü<
.fuente
Haskell , 50 bytes
Pruébalo en línea!
fuente
\\
función: (Casco , 16 bytes
Pruébalo en línea!
Explicación
Esta primera línea es la función principal, y la segunda es una función auxiliar de orden superior (toma una función como argumento y devuelve una nueva función). Se accede por el subíndice
₁
. La idea es que₁≤
realiza dropsort y₁>
da los elementos sobrantes.En la función principal, iteramos la función sobrante
₁>
y aplicamos la función dropsort₁≤
a los resultados.fuente
Python 3 ,
131 112 10395 bytesMuchas gracias, señor. ¡Xcoder para un espectacular 19 bytes!
¡Muchas gracias @ovs por los increíbles 17 bytes!
Pruébalo en línea!
Explicación:
fuente
if-else
se puede colapsar en[m,d][i<m[-1]]+=[i]
.[m,d]
cosa, pero no estaba funcionando de alguna manera ....(len(d)>0)
esbool(d)
porque las listas vacías son falsas en Python. +1, ¡Buena solución!i,
es solo una abreviatura de(i,)
, que es una tupla que contienea
.a,*x = x or [0]
es el desempaquetado extendido de python3 . Aquí hay una publicación SO útil sobre este tema con algunos ejemplos.Haskell ,
11310710292 bytesPruébalo en línea!
Esto se siente muy largo.
Explicación
!
realiza la ordenación por caída en una lista, mientras#
recopila los recortes.g
luego se aplica repetidamente#
hasta que la lista esté vacía registrando los resultados en una lista.fuente
head a
cona!!0
guarda un byte.APL, 27 bytes
Explicación:
⍵≡⍬:⍬
: si la entrada está vacía, devuelve la lista vacíaX←⍵≥⌈\⍵
: todos los números mayores o iguales al máximo de ejecución(⊂X/⍵)
: la lista de esos números,∇⍵/⍨~X
: seguido del resultado de ejecutar esta función en los números restantesfuente
{⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}
. Morten está preocupado por la falta de respuesta a sus correos electrónicos. ¿Está todo bien?JavaScript (ES6), 64 bytes
Sin golf:
Mostrar fragmento de código
fuente
?!
era un nuevo operador elegante ...?!
(i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o]
Aparentemente, las grandes mentes piensan (más o menos) igual. Desafortunadamente, parece que no puedo eliminar más bytes ... Solo notando que puedes eliminarf=
tu código, y tal vez mi código podría darte algunas ideas sobre cómo jugar al tuyo aún más.f=
de mi código, porque es recursivo. El suyo es un enfoque interesante, pero no parece funcionar para algunos de los casos de prueba. Por ejemplo, vuelve[[5,8],[4],[3],[7],[6]]
para el penúltimo caso.R , 61 bytes
Pruébalo en línea!
Función recursiva.
sum(x|1)
es la abreviatura delength(x)
, por lo que esta recursión se ejecutará hasta quex
esté vacía.cummax
toma el máximo acumulado dex
, que luego se compara conx
otra vez. Esto produce un vector booleano de longitudx
, donde todas las VERDADERAS corresponden a valores ordenados. Usamos eso para tomar un subconjuntox
yprint
. La función se llama nuevamente en el resto dex
.fuente
Java 8,
182179177 bytes-3 bytes gracias a @Nevay .
-2 bytes usando en
Stack
lugar deVector
.Explicación:
Pruébalo aquí
fuente
try{}catch{}
lugar de verificarl.size()
para guardar algunos?0
y eliminar los corchetes del bucle for externol->{List r=new Vector(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Vector()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}
(-3 bytes).C #,
188203 bytesEl recuento de bytes incluye +18 para:
Pruébalo en línea!
fuente
C ++ 14,
118108bytesUsando el algoritmo de la respuesta de Haskell de w0lf .
Como lambda genérico sin nombre. El primer parámetro es un contenedor de los valores a dropsort (like
vector<int>
) y el segundo parámetro requiere un contenedor de contenedores vacío compatible (likevector<vector<int>>
) para el valor de retorno por referencia.En la primera versión del programa, había una
R.clear;()
primera declaración, por lo que el contenedor de contenedores no necesitaba estar vacío. Peter Cordes pensó que esto podría entrar en la especificación, por lo que soltó 10 bytes para eso.Pruébalo en línea!
Sin golf:
fuente
R.clear()
, y solo requerir que la persona que llama comience con un contenedor vacío.Python 2 , 88 bytes
-4 bytes gracias a Arnold Palmer
Pruébalo en línea!
Solución similar a haskell de @ w0lf [respuesta] [1]
Caso de uso raro para
for-else
construcciónIterar a través de listas ordenadas
for l in r
(vacías al inicio).Si el elemento (de la entrada)
i
es más grande que el último elemento de la listal[-1]
, agregue el elemento a la listal+=[i]
, interrumpa.Si no se aceptó ninguna lista, agregue una nueva lista con este elemento
r+=[[i]]
fuente
R, trabajo en progreso (89, pero falla)
Manteniendo algo de trabajo aquí, porque me arrinconé en una esquina usando
%in%
(falla en entradas duplicadas, en particular el último caso de prueba), y necesito hacer otras cosas ahora, pero esto es aquí si alguien quiere construir sobre él:Sin golf:
fuente
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)
funciona]
yc
es una nueva línea (o punto y coma)"if"
antes, pero soy bastante nuevo en R golf. Deberías publicar como tu propia respuesta, y yo puedo tomar la mía. Me gusta lo que hiciste con eli
índice, para%in%
solucionar el problema.cummax
!JavaScript (ES6),
717068 bytesBastante simple, solo itera la matriz, busca la primera matriz interna cuyo último valor es
<=
el siguiente valor a soltar, si no existe ninguno, agregue una nueva matriz interna con el siguiente valor a la salida, de lo contrario agregue el siguiente valor al primero encontrado matriz interna que coincide con la condición.Actualizaciones
Gracias a Neil, guardan tres bytes convertir
(...,o)
a...&&o
y la reorganización de la devolución de llamada amap()
ser más compacto.fuente
&&o
es un byte más corto que(,o)
.[...b].pop()
, pero creo que(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)
te ahorra un byte o dos.Japt , 29 bytes
¡Pruébelo en línea!
fuente
C (gcc) ,
176175173 bytesPruébalo en línea!
Versión algo legible:
fuente
PHP,
911039685 bytes(Editado para agregar 12 caracteres
print_r($r);
para cumplir con el requisito de salida)(Editado para eliminar 7 bytes cuando se permiten errores de PHP)
(Editado para eliminar 11 bytes cuando se sigue jugando la tarea)
Dada entrada
$a
, produce resultado$r
Bonita:
El bucle externo pseudo-recursivo inicializa las matrices keep
$b
y descarte$d
para vaciarlas, luego realiza un bucle básico de clasificación por caída, finalmente establece los descartes como la nueva entrada y agrega las conservas al resultado$r
fuente
PHP ,
102 bytes, 98 bytesPruébalo en línea!
-4 bytes, gracias a @Umbrella
Explicación
La función toma la lista de entrada como una matriz.
$s
, que se convertirá en la lista de listas finalmente devuelta, se declara estática. Esto amplía su alcance a todas las llamadas de esta función, permitiendo que la función se llame de forma recursiva sin tener que pasar esta lista de resultados como argumento o devolverla.Recorre cada valor de la lista.
¿Es menos que el miembro más grande de la lista actual?
Sí, póngalo en la lista
$f
para su posterior clasificación.No, ponlo en la lista
$l
.Empuje la lista
$l
a la lista de listas.Si hay algo en la lista
$f
, envíelo nuevamente para ordenarlo más.Devuelve la lista de listas.
fuente
<?php function d($a){return$r;}
, me aplastó de todo corazón. Aparte, me acabo de dar cuenta de que ambos olvidamos la salida.$v<max($l)?$f[]=$v:$l[]=$v;
con${$v<max($l)?f:l}[]=$v;
, al menos, funciona en mis pruebas.Sabio, 102 bytes
Muy similar a la respuesta de @Dead Possum .
Agrega a cada miembro
x
dew
la primera lista ena
{lista de listas} conx
mayor que su último elemento.si ninguno, se agrega
[x]
aa
.¡Realmente me gustaría que fuera
exists
devueltoa
si no se encuentra nada! También tratando de aplicar la idea de una línea de @ officialaimm ...Pregunta: Si eliminé mi código de la función, ¿tendría que asignar la
w
entrada correcta? Entonces, ¿ahorraría bytes?fuente
Ocaml ,
6962 bytesExplicación:
fuente
APL,
1008883797857567776 bytes-0 bytes gracias a Kritixi Lithos ...
Pruébalo en línea!
Tiene que haber una mejor manera de hacer esto ( Hay ). Cualquier consejo es muy apreciado y bienvenido.
¿Cómo?
(Tenga en cuenta que parte de esta explicación podría estar equivocada, ya que olvidé cómo funcionaba)
fuente
{⍬≢⍴⍵}
puede convertirse(⍬≢⍴)
{(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}
? Parece estar separado de todo lo demás[[1,2,5,7],[4],3]
, en lugar de lo requerido[[1,2,5,7],[4],[3]]
.(,¨)
Jalea, 26 bytes
Este es el mismo método que la respuesta APL de marinus.
Pruébalo en línea! .
fuente
JavaScript (Node.js) ,
125109106 bytes-
1618 bytes de Zacharý-1 quitando
{
y}
cambiando el incrementador para incluir el "conjunto último al actual"Básicamente, pregunta es el elemento actual mayor que el último elemento, agregar a la primera lista. De lo contrario, agregue a la segunda.
Descubrí durante esto que
NaN
siempre resultará comparar cualquier númerofalse
. ¡Interesante!Explicación:
Pruébalo en línea!
fuente
var
?x
.