Effectuer un tri par gravité

29

Défi

Étant donné une liste d'entiers, montrez comment le tri par gravité serait effectué.

Tri par gravité

En ordre de gravité, imaginez les nombres sous forme de rangées d'astérisques. Ensuite, tout tombe, et les nouvelles lignes seront évidemment triées. Regardons un exemple:

[2, 7, 4, 6]:

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

Notez que c'est à peu près un tri de bulles parallélisé.

Spécifications exactes

À chaque itération, en commençant par la ligne du haut, prenez chaque astérisque de la ligne qui n'a pas d'astérisque en dessous et déplacez-le d'une ligne vers le bas. Continuez ainsi jusqu'à ce que la liste soit triée.

Contribution

L'entrée sera une liste d'entiers strictement positifs.

Sortie

Pour la sortie, vous devez sortir chaque étape. Vous pouvez choisir deux caractères ASCII imprimables non blancs, l'un pour les "astérisques" et l'autre pour les "tirets" de séparation. Les rangées d'astérisques doivent être séparées par une nouvelle ligne standard (par exemple \nou \r\f). La ligne de tirets doit être au moins de la largeur de la ligne la plus large (sinon vos astérisques vont tomber trop bas!). Une rangée de tirets tout en bas est facultative. Un retour à la ligne à la fin est autorisé. Les espaces de fin sur chaque ligne sont autorisés.

Cas de test

l'entrée sera représentée sous forme de liste, puis la sortie sera répertoriée immédiatement ci-dessous. Les cas de test sont séparés par un double saut de ligne.

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

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

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

N'hésitez pas à corriger mes cas de test s'ils sont faux, je les ai faits à la main :)

Remarque: ne sortez pas la liste triée à la fin. :)

Notation

Tous vos programmes seront écrits les uns sur les autres. Vous ne voudriez pas que des morceaux de votre programme tombent, alors assurez-vous d'avoir le code le plus court!

HyperNeutrino
la source
1
Pouvons-nous éviter d'imprimer des tirets? Au lieu d'imprimer des astérisques, pouvons-nous imprimer une matrice de 0 et de 1? Je pense que le format d'impression n'ajoute rien au défi.
rahnema1
@ rahnema1 1. Vous pouvez remplacer les tirets par d'autres caractères non blancs 2. Non.
HyperNeutrino
Je crois que vous manquez un astérisque lors de la 2e itération de votre dernier cas de test
MildlyMilquetoast
1
Si nous ne voulons pas que des morceaux du programme tombent, cela signifie-t-il que nous ne pouvons pas avoir de lignes de code plus longues par-dessus nos lignes de code plus courtes? : o
Value Ink
1
Hé, c'est comme ça que je trie mes livres!
Robert Fraser

Réponses:

4

Perl 5 , 118 octets

115 octets de code + -pladrapeaux.

\@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 /}

Essayez-le en ligne!

Cela semble un peu trop long. Mais encore une fois, traiter les chaînes multilignes avec l'expression régulière n'est généralement pas facile.

J'utilise Yau lieu de *et _au lieu de -.

Dada
la source
3

Octave, 104 octets

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)

* Nécessite un package d'images.

Essayez-le en ligne!

Explication:

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
la source
malheureusement, il n'y a probablement pas de points bonus pour l'animation image par image: |
quetzalcoatl
ai maintenant - mes excuses, commentaire rétracté
TessellatingHeckler
3

Python, 203 199 octets

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
la source
1
Où sont les tirets?
Leaky Nun
@LeakyNun fixed
Uriel
Pensez à utiliser Python 2 au lieu de votre Python 3 actuel, où maprenvoie un tableau immédiatement afin que vous n'ayez pas besoin de le répartir. Vous voudriez assigner une variable à '\n'.joinpour vous aider à compenser le manque sep='\n', mais c'est probablement encore plus court de cette façon.
Value Ink
@ValueInk comment feriez-vous pour les zips? le manque de déballage pourrait coûter de nombreux octets
Uriel
Python 2 vous permet de décompresser très bien dans une fonction; J'ai seulement entendu que le déballage dans un tableau a parfois des problèmes. Avec seulement mes modifications suggérées, le code Python 2 fait 194 octets, essayez-le en ligne
Value Ink
2

Japt , 69 62 octets

-7 octets grâce à @Shaggy


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

Apprendre Japt et vouloir essayer un défi plus compliqué. Sorties avec xs et "s au lieu d'astérisques et de tirets; prend l'entrée comme un tableau de nombres. Suppose que le tri sera terminé dans les input.lengthétapes; corrigez-moi si ce n'est jamais le cas.

Essayez-le en ligne!

Explication

                              // 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
la source
1
Quelques économies rapides pour vous . Je suis sûr qu'il y en a plus mais je suis assez fatigué.
Shaggy
@Shaggy Merci beaucoup! C'est un très bon exemple de définition de variables en fonction de la ligne sur laquelle se trouve l'instruction. Si ce n'est pas sur le post des astuces Japt, ça devrait l'être.
Justin Mariner
C'est fait . Laissez un commentaire si vous voyez des améliorations à apporter.
Shaggy
@Shaggy semble bon, et félicitations pour votre badge en or!
Justin Mariner
2

R , 210 205 octets

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

Essayez-le en ligne!

lit dans la liste depuis stdin; séparés par des +caractères au lieu de -. C'est beaucoup plus long que je ne l'aurais pensé. Profite du fait que la comparaison est '*'>'+'évaluée FALSEmais l' '*'>' 'est TRUE, au moins sur TIO (sur ma machine que j'ai utilisée '='qui avait l'air un peu mieux).

Géré au golf à 5 octets de toutes les techniques que j'ai apprises depuis la rédaction de la réponse originale.

Essayez-le en ligne!

Giuseppe
la source
1

Haskell , 213 211 208 octets

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

Essayez-le en ligne!

Bartavelle
la source
1

Javascript, 274 octets

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)

Exemple d'extrait de code:

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
la source