Wyzwanie

Biorąc pod uwagę listę liczb całkowitych, pokaż, jak zostanie wykonane sortowanie grawitacyjne.

Sortowanie grawitacyjne

W sortowaniu grawitacyjnym wyobraź sobie liczby jako rzędy gwiazdek. Wtedy wszystko spada, a nowe rzędy zostaną oczywiście posortowane. Spójrzmy na przykład:

[2, 7, 4, 6]:

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

Zauważ, że jest to właściwie tylko równoległe sortowanie bąbelkowe.

Dokładne specyfikacje

Na każdej iteracji, zaczynając od górnego rzędu, weź każdą gwiazdkę z rzędu, który nie ma gwiazdki pod nią, i przesuń ją w dół o rząd. Rób tak, dopóki lista nie zostanie posortowana.

Wkład

Dane wejściowe będą listą liczb całkowitych ściśle dodatnich.

Wydajność

W przypadku danych wyjściowych należy wyprowadzić każdy krok. Możesz wybrać dowolne dwa znaki ASCII drukowalne bez białych znaków, jeden jako „gwiazdki”, a drugi jako „myślniki”. Rzędy gwiazdek muszą być oddzielone standardowym rodzajem nowej linii (np. \nLub \r\f). Rząd myślników musi mieć co najmniej szerokość najszerszego rzędu (w przeciwnym razie Twoje gwiazdki spadną zbyt głęboko!). Rząd myślników na samym dole jest opcjonalny. Końcowy znak nowej linii na końcu jest dozwolony. Końcowe spacje w każdej linii są dozwolone.

Przypadki testowe

dane wejściowe będą reprezentowane jako lista, a następnie dane wyjściowe zostaną wymienione bezpośrednio poniżej. Przypadki testowe są oddzielone podwójnym znakiem nowej linii.

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

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

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

Prosimy o poprawienie moich przypadków testowych, jeśli są błędne, zrobiłem je ręcznie :)

Uwaga: Nie wysyłaj posortowanej listy na końcu. :)

Punktacja

Wszystkie twoje programy będą pisane jeden na drugim. Nie chciałbyś, aby części twojego programu upadały, więc upewnij się, że masz najkrótszy kod!

Pyth , 27 bajtów

jsCM.u:R"v "" v"N+R\-.t*L\v

Wypróbuj online!

Perl 5 , 118 bajtów

115 bajtów kodu + -plaflagi.

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

Wypróbuj online!

To wydaje się trochę za długie. Ale znowu radzenie sobie z ciągami wielowierszowymi za pomocą wyrażenia regularnego zwykle nie jest łatwe.

Używam Yzamiast *i _zamiast -.

Oktawa, 104 bajty

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)

* Wymaga pakietu obrazu.

Wypróbuj online!

Wyjaśnienie:

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

Python, 203 199 bajtów

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')

Japt , 69 62 bajtów

-7 bajtów dzięki @Shaggy

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

Ucząc się Japt, chciałem wypróbować bardziej skomplikowane wyzwanie. Wyprowadza za pomocą xsi "si zamiast gwiazdek i myślników; przyjmuje dane wejściowe jako tablicę liczb. Zakłada, że ​​sortowanie zostanie zakończone w kilku input.lengthkrokach; popraw mnie, jeśli tak nie jest.

Wypróbuj online!

Wyjaśnienie

                              // 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

R , 210 205 bajtów

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

Wypróbuj online!

czyta na liście ze standardowego wejścia; oddzielone +znakami zamiast -. To dużo dłużej, niż bym się spodziewał. Wykorzystuje fakt, że porównanie '*'>'+'ocenia, FALSEale '*'>' 'dotyczy TRUEprzynajmniej TIO (na mojej maszynie użyłem, '='która wyglądała nieco lepiej).

Udało mi się zagrać w golfa o 5 bajtów w dół od wszystkich technik, których nauczyłem się od czasu napisania oryginalnej odpowiedzi.

Wypróbuj online!

Haskell , 213 211 208 bajtów

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

Wypróbuj online!

JavaScript, 274 bajty

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)

Przykładowy fragment kodu:

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>