Perform gravity sort

Question

Challenge

Given a list of integers, show how gravity sort would be done.

Gravity Sort

In gravity sort, imagine the numbers as rows of asterisks. Then, everything falls, and the new rows will be obviously sorted. Let's look at an example:

[2, 7, 4, 6]:

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

Notice that this is pretty much just parallelized bubble sort.

Exact Specs

On each iteration, starting from the top row, take every asterisk from the row that doesn't have an asterisk below it, and move it down a row. Keep doing that until the list is sorted.

Input

Input will be a list of strictly positive integers.

Output

For the output, you must output each step. You can choose any two non-whitespace printable ASCII characters, one to be the "asterisks", and one to be the separating "dashes". The rows of asterisks must be separated with a standard newline of some sort (e.g. \n or \r\f). The row of dashes must be at least the width of the widest row (otherwise your asterisks are going to fall too far down!). A row of dashes at the very bottom is optional. A trailing newline at the end is permitted. Trailing spaces on each line are permitted.

Test Cases

input will be represented as a list, then output will be listed immediately below. Test cases are separated by a double-newline.

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

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

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

[2, 7, 4, 6]
**
*******
****
******
-------
**
****
*******
******
-------
**
****
******
*******

Please feel free to correct my test cases if they're wrong, I made them by hand :)

Note: Do not output the sorted list at the end. :)

Scoring

All of your programs will be written on top of each other. You wouldn't want pieces of your program to fall down, so make sure you have the shortest code!

Answer 1

Pyth, 27 bytes

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

Try it online!

Answer 2

Perl 5, 118 bytes

115 bytes of code + -pla flags.

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

Try it online!

It seems a bit too long. But again, dealing with multiline strings with regex is usually not easy.

I'm using Y instead of * and _ instead of -.

Answer 3

Octave, 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)

*Requires image package.

Try it online!

Explanation:

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

Answer 4

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

Answer 5

Japt, 69 62 bytes

-7 bytes thanks to @Shaggy

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

Learning Japt and wanted to try out a more complicated challenge. Outputs with xs and "s instead of asterisks and dashes; takes input as an array of numbers. Assumes sorting will be complete within input.length steps; correct me if that is ever not the case.

Try it online!

Explanation

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

Answer 6

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

Try it online!

reads in the list from stdin; separated by + characters instead of -. It's a lot longer than I would have thought it would be. Takes advantage of the fact that the comparison '*'>'+' evaluates to FALSE but '*'>' ' is TRUE, at least on TIO (on my machine I used '=' which looked a little better).

Managed to golf 5 bytes down from all the techniques I've learned since writing the original answer.

Try it online!

Answer 7

Japt -R, 32 31 30 32 31 30 bytes

Really enjoyed this one but not entirely happy with the final result, especially after having to add 2 bytes to fix a bug. Still determined to get it down under 30 bytes, though.

Uses n instead of *.

¡P=yÈrSùÍSúÍê¡Xçn÷úÃâ qR² ú-

Try it (footer replaces ns with *s) or run all test cases

¡P=yÈrSùÍSúÍê¡Xçn÷úÃâ qR² ú-     :Implicit input of array U
¡                                  :Map
 P=                                :  Reassign to P (initially the empty string)
   y                               :    Transpose P
    È                              :    Pass through the following function and transpose back
     r                             :      Replace
      S                            :        Space
       ù                           :        Left padded with
        Í                          :        "n" to length 2
         SúÍ                       :        With a space right padded with "n" to length 2
            Ã                      :    End function
             ª                     :    Logical OR ('cause it'll still be the empty string on the first iteration)
              ¡                    :      Map each X in U
               Xçn                 :        "n" repeated X times
                  Ã                :      End map
                   ·               :      Join with newlines
                    ú              :      Right pad each with spaces to the length of the longest
                      Ã            :End map
                       â           :Deduplicate
                         q         :Join with
                          R        :  Newline
                           ²       :  Repeated twice
                             ú-    :Right pad each line with "-" to the length of the longest

Answer 8

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

Try it online!

Answer 9

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)

Example code snippet:

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>

Answer 10

J, ⁴⁹ 45 bytes

' *-'{~2,/@,.~[:((]+[-1|.])]<_1|.!.0])^:a:#&1

Try it online!

Takes input as a column vector.

About a third of the bytes are just to conform to the output specs.

• #&1 Convert to rows of ones, with 0 fill.
• [:(...)^:a: Do ... until a fixed point is reached, keeping track of intermediate results.
• ]<_1|.!.0] Rotate the rows down, then ask: "where is that less than the original input?" This will pick out just the valid falling pieces, in their "next" position. Call these the "rain".
• (]+[-1|.]) Add the rain to this step's input minus the rain rotated up. That is, rewind the "rain" one step, remove this rewinded-rain from the input, and then add the not-rewinded rain. This is precisely the rain plus the static pieces, which is what we want for the next iteration.
• ' *-'{~2,/@,.~ Conform to output spec.