# 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!

• Can we avoid printing dashes? and Instead of printing asterisks can we print matrix of 0s and 1s?I think format of printing adds nothing to the challenge. – rahnema1 May 11 '17 at 15:44
• If we don't want pieces of the program to fall down, does this mean that we can't have longer lines of code on top of our shorter lines of code? :o – Value Ink May 11 '17 at 20:19
• Hey that's how I sort my books! – Robert Fraser Jul 10 '17 at 15:05
• I don't suppose we could include a leading or trailing line of -s, could we? – Shaggy Nov 5 '20 at 18:27
• No worries; figured that'd be the case but it never hurts to ask :) Thanks for the fun challenge - can't remember the last time I spent this long on a solution. – Shaggy Nov 5 '20 at 18:32

# Pyth, 27 bytes

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


Try it online!

# 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 -. # 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  • sadly, probably there's no bonus points for frame-by-frame animation :| – quetzalcoatl May 11 '17 at 21:12 • have now - my apologies, comment retracted – TessellatingHeckler Jul 6 '17 at 17:44 # 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')  • Where are the dashes? – Leaky Nun May 11 '17 at 17:11 • @LeakyNun fixed – Uriel May 11 '17 at 17:15 • Consider using Python 2 instead of your current Python 3, where map returns an array immediately so you don't need to splat it. You'd want to assign a variable to '\n'.join to help you make up for the lack of sep='\n', though, but it's probably still shorter that way. – Value Ink May 11 '17 at 22:59 • @ValueInk how would you go about the zips? the lack of unpacking might cost many bytes – Uriel May 11 '17 at 23:10 • Python 2 lets you unpack into a function just fine; I only heard that unpacking into an array sometimes has issues. With only my suggested changes the Python 2 code is 194 bytes, try it online – Value Ink May 11 '17 at 23:31 # 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  • A few quick savings for you. I'm sure there are more but I'm quite tired. – Shaggy Jul 10 '17 at 9:16 • @Shaggy Thanks a lot! That's a really good example of setting variables according to the line the statement is on. If that isn't on the Japt tips post, it should be. – Justin Mariner Jul 10 '17 at 10:32 • Done. Leave a comment if you see any room for improvement. – Shaggy Jul 10 '17 at 10:54 • @Shaggy Looks good, and congrats on your gold badge! – Justin Mariner Jul 10 '17 at 11:12 # 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! # Japt-R, 32313032 31 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 byes, though. Uses n for * and " for -. Q¸ï¡P=yÈrSùÍSúÍÃªUËçÍÃúÃâ)c ÅúQ  Try it (footer replaces characters used with * & -) or run all test cases Q¸ï¡P=yÈrSùÍSúÍÃªUËçÍÃúÃâ)c ÅúQ :Implicit input of array U Q :Literal " ¸ :Split on spaces ï :Cartesian product with ¡ : Map U 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) UË : Map each D in U ç : D times repeat Í : "n" Ã : End map ú : Right pad each with spaces to the length of the longest Ã : End map â : Deduplicate ) :End cartesian product c :Flatten Å :Slice off the first element úQ :Right pad each element with " to the length of the longest :Implicit output joined with newlines  # Haskell, 213211 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!

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