29
\$\begingroup\$

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]
********
****
**
*
--------
****
**  ****
* **
**
--------
**
* **
**  ****
****
--------
*
**
****
********

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – rahnema1 May 11 '17 at 15:44
  • \$\begingroup\$ @rahnema1 1. You may replace the dashes with some other non-whitespace character 2. No. \$\endgroup\$ – HyperNeutrino May 11 '17 at 15:51
  • \$\begingroup\$ I believe you are missing an asterisk on the 2nd iteration of your last test case \$\endgroup\$ – MildlyMilquetoast May 11 '17 at 16:56
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Value Ink May 11 '17 at 20:19
  • 1
    \$\begingroup\$ Hey that's how I sort my books! \$\endgroup\$ – Robert Fraser Jul 10 '17 at 15:05
7
\$\begingroup\$

Pyth, 27 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ sadly, probably there's no bonus points for frame-by-frame animation :| \$\endgroup\$ – quetzalcoatl May 11 '17 at 21:12
  • \$\begingroup\$ have now - my apologies, comment retracted \$\endgroup\$ – TessellatingHeckler Jul 6 '17 at 17:44
3
\$\begingroup\$

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')
\$\endgroup\$
  • 1
    \$\begingroup\$ Where are the dashes? \$\endgroup\$ – Leaky Nun May 11 '17 at 17:11
  • \$\begingroup\$ @LeakyNun fixed \$\endgroup\$ – Uriel May 11 '17 at 17:15
  • \$\begingroup\$ 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. \$\endgroup\$ – Value Ink May 11 '17 at 22:59
  • \$\begingroup\$ @ValueInk how would you go about the zips? the lack of unpacking might cost many bytes \$\endgroup\$ – Uriel May 11 '17 at 23:10
  • \$\begingroup\$ 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 \$\endgroup\$ – Value Ink May 11 '17 at 23:31
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ A few quick savings for you. I'm sure there are more but I'm quite tired. \$\endgroup\$ – Shaggy Jul 10 '17 at 9:16
  • \$\begingroup\$ @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. \$\endgroup\$ – Justin Mariner Jul 10 '17 at 10:32
  • \$\begingroup\$ Done. Leave a comment if you see any room for improvement. \$\endgroup\$ – Shaggy Jul 10 '17 at 10:54
  • \$\begingroup\$ @Shaggy Looks good, and congrats on your gold badge! \$\endgroup\$ – Justin Mariner Jul 10 '17 at 11:12
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.