Realizar ordenamiento por gravedad

29

Reto

Dada una lista de enteros, muestre cómo se haría la clasificación por gravedad.

Ordenar por gravedad

En gravedad, imagine los números como filas de asteriscos. Entonces, todo cae, y las nuevas filas obviamente se ordenarán. Veamos un ejemplo:

[2, 7, 4, 6]:

**
*******
****
******
-------
**
****
*******
******
-------
**      | 2
****    | 4
******  | 6
******* | 7

Tenga en cuenta que esto es más o menos una clasificación de burbujas paralela.

Especificaciones exactas

En cada iteración, comenzando desde la fila superior, tome cada asterisco de la fila que no tenga un asterisco debajo y muévalo hacia abajo una fila. Sigue haciendo eso hasta que la lista esté ordenada.

Entrada

La entrada será una lista de enteros estrictamente positivos.

Salida

Para la salida, debe generar cada paso. Puede elegir dos caracteres ASCII imprimibles que no sean espacios en blanco, uno para ser los "asteriscos" y otro para ser los "guiones" de separación. Las filas de asteriscos se deben separar con una nueva línea estándar de algún tipo (p . Ej. \nO \r\f). La fila de guiones debe ser al menos del ancho de la fila más ancha (de lo contrario, ¡los asteriscos caerán demasiado!). Una fila de guiones en la parte inferior es opcional. Se permite una nueva línea al final. Se permiten espacios finales en cada línea.

Casos de prueba

la entrada se representará como una lista, luego la salida se enumerará inmediatamente debajo. Los casos de prueba están separados por una doble línea nueva.

[4, 3, 2, 1]
****
***
**
*
----
***
** *
* *
**
----
**
* *
** *
***
----
*
**
***
****

[6, 4, 2, 5, 3, 1]
******
****
**
*****
***
*
------
****
**  **
****
***
*  **
***
------
**
****
*** **
*  *
***
*****
------
**
***
*  *
*** **
****
*****
------
**
*
***
****
******
*****
------
*
**
***
****
*****
******

[8, 4, 2, 1]
********
****
**
*
--------
****
**  ****
* **
**
--------
**
* **
**  ****
****
--------
*
**
****
********

No dude en corregir mis casos de prueba si están equivocados, los hice a mano :)

Nota: No envíe la lista ordenada al final. :)

Tanteo

Todos sus programas se escribirán uno encima del otro. No querrás que se caigan partes de tu programa, ¡así que asegúrate de tener el código más corto!

Hiperneutrino
fuente
1
¿Podemos evitar imprimir guiones? y en lugar de imprimir asteriscos, ¿podemos imprimir una matriz de 0s y 1s? Creo que el formato de impresión no agrega nada al desafío.
rahnema1
@ rahnema1 1. Puede reemplazar los guiones con algún otro carácter que no sea un espacio en blanco 2. No.
HyperNeutrino
Creo que te falta un asterisco en la segunda iteración de tu último caso de prueba
MildlyMilquetoast
1
Si no queremos que se caigan partes del programa, ¿significa esto que no podemos tener líneas de código más largas además de nuestras líneas de código más cortas? : o
Value Ink
1
¡Hola, así es como clasifico mis libros!
Robert Fraser

Respuestas:

4

Perl 5 , 118 bytes

115 bytes de código + -plabanderas.

\@X[$_]for@F;s%\d+ ?%Y x$&.$"x($#X-$&).$/%ge;while(/Y.{$#X} /s){print$_,_ x$#X;1while s/Y(.{$#X}) /X$1b/s;y/bX/Y /}

Pruébalo en línea!

Parece un poco largo. Pero, de nuevo, lidiar con cadenas multilínea con expresiones regulares generalmente no es fácil.

Estoy usando en Ylugar de *y en _lugar de -.

Dada
fuente
3

Octava, 104 bytes

b=(1:max(L=input("")))<=L;do;disp(" *-"([b;max(b)+1]+1))until b==(b=imerode(b,k=[1;1])|imdilate(b,k)~=b)

* Requiere paquete de imágenes.

Pruébalo en línea!

Explicación:

input = [8 ;4 ;2 ;1]

L = input('');                    %input list
b=(1:max(L))<=L;                  % generate matrix of 0s and 1s as indexes of asterisks 

b =

  1  1  1  1  1  1  1  1
  1  1  1  1  0  0  0  0
  1  1  0  0  0  0  0  0
  1  0  0  0  0  0  0  0
do;
    disp(' *-'([b;max(b)+1]+1))  %display asterisks and dashes

    E = imerode(b,k=[1;1]);      %morphological erosion
    E =

      1  1  1  1  0  0  0  0
      1  1  0  0  0  0  0  0
      1  0  0  0  0  0  0  0
      1  0  0  0  0  0  0  0

    D = imdilate(b,k);           %morphological dilation
    D =

      1  1  1  1  1  1  1  1
      1  1  1  1  1  1  1  1
      1  1  1  1  0  0  0  0
      1  1  0  0  0  0  0  0

    b_temp = E | (D~=b)          %intermediate result
    b_temp =

      1  1  1  1  0  0  0  0
      1  1  0  0  1  1  1  1
      1  0  1  1  0  0  0  0
      1  1  0  0  0  0  0  0

until b==(b=b_temp)              %loop until no change
rahnema1
fuente
lamentablemente, probablemente no haya puntos de bonificación para la animación cuadro por cuadro: |
quetzalcoatl
tengo ahora - mis disculpas, comentario retraído
TessellatingHeckler
3

Python, 203 199 bytes

def k(x):
 m,j=max(x),''.join;d=[*map(lambda i:('*'*i).ljust(m),x)];f=sorted(d);print(*d,sep='\n')
 while d!=f:d=[*map(j,zip(*[x.replace('* ',' *')for x in map(j,zip(*d))]))];print('-'*m,*d,sep='\n')
Uriel
fuente
1
¿Dónde están los guiones?
Leaky Nun
@LeakyNun arreglado
Uriel
Considere usar Python 2 en lugar de su Python 3 actual, donde mapdevuelve una matriz de inmediato para que no necesite salpicarla. Sin embargo, querrá asignar una variable para '\n'.joinayudarlo a compensar la falta sep='\n', pero probablemente aún sea más corto de esa manera.
Value Ink
@ValueInk, ¿cómo harías con las cremalleras? la falta de desembalaje podría costar muchos bytes
Uriel
Python 2 te permite descomprimir en una función muy bien; Solo escuché que desempacar en una matriz a veces tiene problemas. Con solo mis cambios sugeridos, el código de Python 2 es de 194 bytes, pruébelo en línea
Value Ink
2

Japt , 69 62 bytes

-7 bytes gracias a @Shaggy


®ç'x +SpZnUrwÃpQpUrw¹·
V
l o ®V=z d" x""x " z3ÃuW
X¯XbXgJ)Ä ·

Aprendí Japt y quise probar un desafío más complicado. Salidas con xsy "s en lugar de asteriscos y guiones; toma la entrada como una matriz de números. Asume que la clasificación se completará en input.lengthpasos; corrígeme si ese no es el caso.

Pruébalo en línea!

Explicación

                              // implicit: U = input array
 ®   ç'x +SpZnUrwà pQpUrw¹ ·  // implicit: V = this line
UmZ{Zç'x +SpZnUrw} pQpUrw) qR // ungolfed
UmZ{             }            // U mapped by the function:
    Zç'x                      //   "x" times this item
         +SpZnUrw             //   plus " " times the max of the input array (Urw) minus this value (Z)
                   pQpUrw)    // push " (Q) times the max
                           qR // join with newlines

V                             // implicit: W = this line

 l o ®   V=z d" x""x " z3Ã uW // implicit: X = this line
Ul o mZ{ZV=z d" x""x " z3} uW // ungolfed
Ul o                          // the array of the range [0, U.length)
     mZ{Z                }    // mapped by the no-arg function:
         V=z                  //   set V to itself rotated 90deg
             d" x""x "        //   replace all " x" with "x " to "fall"
                       z3     // rotate back to normal
                           uW // add  W(the original) to the start

X¯XbXgJ)Ä ·                   // implicit: return this line
Xs0,XbXgJ)+1 qR               // ungolfed
Xs0,                          // get the substring of X from 0 to...
    XbXgJ)+1                  // the first index of the last item, plus one
             qR               // join with newlines
Justin Mariner
fuente
1
Unos ahorros rápidos para ti . Estoy seguro de que hay más, pero estoy bastante cansado.
Shaggy
@ Shaggy Muchas gracias! Ese es un muy buen ejemplo de establecer variables de acuerdo con la línea en la que se encuentra la declaración. Si eso no está en la publicación de consejos de Japt, debería estarlo.
Justin Mariner
Hecho . Deje un comentario si ve algún margen de mejora.
Shaggy
¡@Shaggy se ve bien y felicidades por tu insignia de oro!
Justin Mariner
2

R , 210 205 bytes

l=scan();w=max(l);h=sum(l|1);a=1:h;p=h+1;m=matrix(' ',w,p);m[,p]='+';for(x in a)m[l[x]:1,x]='*';f=function()write(m,'',w,sep='');f();while(any(i<-m[,a]>m[,a+1])){s=which(i);m[,a][s]=' ';m[,a][s+w]='*';f()}

Pruébalo en línea!

lee en la lista de stdin; separados por +caracteres en lugar de -. Es mucho más largo de lo que hubiera pensado que sería. Aprovecha el hecho de que la comparación se '*'>'+'evalúa FALSEpero '*'>' 'es TRUE, al menos en TIO (en mi máquina que usé, '='que se veía un poco mejor).

Logré jugar golf 5 bytes por debajo de todas las técnicas que aprendí desde que escribí la respuesta original.

Pruébalo en línea!

Giuseppe
fuente
1

Haskell , 213 211 208 bytes

import Data.List
(?)=replicate
p=transpose
s l|w<-length l,i<-[n?'*'++w?' '|n<-l]=intercalate[w?'-']$i:(p<$>unfoldr f(p i))
f i|i==n=mempty|2>1=Just(n,n)where n=t<$>i
t(a:b:y)|a>b=" *"++t y|2>1=a:t(b:y);t k=k

Pruébalo en línea!

bartavelle
fuente
1

Javascript, 274 bytes

a=>(r="",m=Math.max(...a),b=a.map(n=>Array(m).fill(0).map((_,i)=>i<n)),(k=_=>(b.map(c=>r+=c.map(v=>v?"*":" ").join``.trim()+`
`),r+="-".repeat(m)+`
`,n=0,b.map((r,i)=>(s=b[i+1])&&r.map((c,j)=>s[j]||(n|=s[j]=-(c>0),c>0&&(r[j]=0)))),b=b.map(c=>c.map(n=>n<0?1:n)),n&&k()))(),r)

Fragmento de código de ejemplo:

f =

a=>(r="",m=Math.max(...a),b=a.map(n=>Array(m).fill(0).map((_,i)=>i<n)),(k=_=>(b.map(c=>r+=c.map(v=>v?"*":" ").join``.trim()+`
`),r+="-".repeat(m)+`
`,n=0,b.map((r,i)=>(s=b[i+1])&&r.map((c,j)=>s[j]||(n|=s[j]=-(c>0),c>0&&(r[j]=0)))),b=b.map(c=>c.map(n=>n<0?1:n)),n&&k()))(),r)

o.innerText = f([6,4,2,5,3,1])
<pre id=o>

Herman L
fuente