# Challenge

Given a rectangular grid of printable ascii characters as a string or through standard input, write a function or program that collapses the non-space characters into a pile on the bottom.

## The rules:

• The output has the same dimensions and characters as the input.
• A non-space character at (row a,column b) can't have a space character ' ' at (a-1, b), (a-1,b-1) or (a-1,b+1), where rows are numbered up from the bottom-most. This has the consequence that all vertical piles should collapse sideways.
• A non-space character can travel at most (initial height - final height) places to the left or right (see Fig. 1).
• You can assume the picture has enough space to collapse without characters falling out of the screen.

Figure 1: possible final locations for characters @#$ shown as x,y,z, respectively. .............. ...@.......... ..xxx......... .xxxxx...#.... xxxxxxx.yyy.$.


The order in which characters collapse can be chosen freely. Trailing spaces are not okay but trailing newlines are.

This is , so the shortest answer in bytes wins!

## Example

                 (__)
(oo)
/------\/
/ |    ||
*  /\---/\
~~   ~~
..."Have you mooed today?"...


One possible output:



--(_
/----|/|(o_)
/|/~\---~\\/o)
..."Have*you~mooed~today?"...

• Just to clarify, the way characters fall can be hard-coded rather than randomly generated each time? – ETHproductions Nov 28 '16 at 19:44
• What did that cow ever do to you?? :( – FlipTack Nov 28 '16 at 19:46
• @ETHproductions that's correct. My example does it bottom to top, left to right but random order or something else is fine, as long as the rules are obeyed. – Angs Nov 28 '16 at 19:52
• @Flp.Tkc It's only a model. – Angs Nov 28 '16 at 19:52
• @DestructibleWatermelon if a character happens to fall out of the screen, it's their fault, not yours. – Angs Nov 29 '16 at 14:04

## JavaScript (ES6), 10090 88 bytes

f=s=>s==(l=s.search
,s=s.replace(eval(/(\\S)([^]{${l-1},${l+1}}) /), $2$1))?s:f(s)
s=                 (__)
(oo)
/------\\/
/ |    ||
*  /\\---/\\
~~   ~~
..."Have you mooed today?"...
console.log(s)
console.log(f(s))

Requires the the string to have at least two lines and all lines padded to equal length. Output for the example image:

              ( --
/|---/|-(o__
*/~~\---~\|\/o))
..."Have you/mooed~today?"...


Note that as it tries to move elements to the right if possible, the * did not fall between the Have and the you.

Edit: Saved 10% thanks to @ETHproductions. Saved another 2 bytes thanks to @DanielIndie.

# Retina 0.8.2, 50 bytes

+(?<=(.)*)(\S)(.*¶(?<-1>)?(?>(?<-1>.)*).?)
$3$2


Try it online! A slightly different approach to my JavaScript answer, this uses a balancing group to match a space below the non-space character; the (?<-1>)? allows the space to be one column to the left while the .? allows the space to be one column to the right.

# Retina, 40 bytes

~0L$.(.*)¶ +s(\S)(.{$.1,$.&}) ¶ $$2$$1  Try it online! Port of my JavaScript answer. The 0L$ atomic stage takes the input and substitutes the two lengths into the second line resulting in the command that actually performs the replacement, which is then evaluated on the original input by the ~ compound stage.

• This is a great algorithm! You can replace \n with a literal newline to get it down to two digits ;-) – ETHproductions Dec 1 '16 at 16:19
• Also, I think you can so l=s.search\n  to save a few bytes. – ETHproductions Dec 1 '16 at 16:21
• tio.run/##ZY/… 86 bytes – DanielIndie Apr 14 '18 at 10:53
• @DanielIndie The f= is required for the recursion, but it still saves me 2 bytes, thanks! – Neil Apr 14 '18 at 15:37
• you are right, sorry :P – DanielIndie Apr 14 '18 at 17:14

## Python 2, 298 bytes

a=input()
L=len(a);s=' '
a=[list(s*L+l.ljust(L+max(map(len,a))))for l in a]
t=1
while t:
t=0
for y in range(L-1):
for x in range(len(a[y])):
c=a[y][x];C=a[y+1][x-1:x+2]
if s!=c and s in C:t=1;a[y][x]=s;a[y+1][[[x+1,x][C[1]==s],x-1][C[0]==s]]=c
for l in map(''.join,a):print l[L:].rstrip()


Takes input as a list of strings (one per line)

Example: Input:

['                 (__)',
'                 (oo)',
'           /------\/',
'          / |    ||',
'         *  /\---/\ ',
'            ~~   ~~',
'..."Have you mooed today?"...']


Output:

              (
-----/|-(o__
//|~~\---~\|\/o))
..."Have*you/mooed~today?"...


C, 252 bytes

e=1,l,c,i,j,p,r,w,a[999];f(){while((i=getchar())>0)a[w++]=i,i<16?l++:0,l?0:c++;while(e)for(i=e=0;i<c;i++)for(j=l;j>=0;j--)e=(r=a[p=j*(c+1)+i]-32?a[r=p+c+1]-32?a[r=p+c]-32?a[r=p+c+2]-32?0:r:r:r:0)?l=a[p],a[p]=a[r],a[r]=l:e;for(i=0;i<w;)putchar(a[i++]);}


Ungolfed test code:

#include <stdio.h>

e=1,l,c,i,j,p,r,w,a[999];
f()
{
// counting lines and columns
while ((i = getchar())>0)a[w++] = i, i<16 ? l++ : 0, l ? 0 : c++;
// main shaking loop
while (e) // repeat while collapsing
for (i = e = 0; i < c; i++) // columns loop
for (j = l; j >= 0; j--) // lines loop
e = ( // remember that collapsing was
r = // find place to collapse
a[p = j*(c + 1) + i] - 32 ? // if not space
a[r = p + c + 1] - 32 ? // if char under the current is not a space
a[r = p + c] - 32 ? // see one position left
a[r = p + c + 2] - 32 ? 0 // then one position right
: r
: r
: r
: 0
) ? // and if place was found
l=a[p],a[p]=a[r],a[r]=l // replace values in positions p and r
: e;
//print resulting picture
for(i=0;i<w;)putchar(a[i++]);
}

int main(void)
{
int cnt;
FILE * testf = fopen("caw.txt","w");
char testd[][31] = {
"                 (__)        \n",
"                 (oo)        \n",
"           /------\\/         \n",
"          / |    ||          \n",
"         *  /\\---/\\          \n",
"            ~~   ~~          \n",
"...\"Have you mooed today ? \"...",
"" };
// prepare data for test
printf("Initial data:\n");
for(cnt = 0; cnt < 7; cnt++)
{
printf("%s", testd[cnt]);
fprintf(testf, testd[cnt]);
}
fclose(testf);
// redirect standard input
freopen("caw.txt", "r", stdin);
printf("\n\nResult:\n");
// start test
f();
}


Result of test:

Algodoo (non-competing)

Input - degenerate example used.

Runnning - default gravity and bouncing.

Output - accuracy can be adjusted via Friction and Density settings on the objects.

• Why is this non-competing? Non-competing is generally reserved for answers in languages newer than the challenge. – Wheat Wizard Dec 1 '16 at 8:02
• Although Algodoo can do real logic, this simulation is equivalent to dropping a shredding print-out of the input on the floor and taking a picture of it. I'm not sure offhand how to even capture that output in a programmatic way. – wyldstallyns Dec 1 '16 at 15:34
• And it seemed wrong to say "zero byte program! i win!" – wyldstallyns Dec 1 '16 at 15:35
• I suspect that this is not in fact a zero byte answer. You talk about tweaking settings which seems to be the equivalent to writing code. It might be a good idea to open a meta question about scoring Algodoo. I also don't think there is anything wrong with having a zero byte program. – Wheat Wizard Dec 1 '16 at 15:40
• I'll open that meta. – wyldstallyns Dec 1 '16 at 16:03

# JavaScript, 286 bytes

b=>eval('f=b=>b==null||" "==b;b=b.split\n.map(b=>[...b]);a:for(;;){for(c=0;c<b.length-1;c++)for(g=b[c],d=0;d<g.length;d++){h=g[d];if(!f(h)){e=0;f(b[c+1][d])?e=2:f(b[c+1][d-1])?e=1:f(b[c+1][d+1])&&(e=3);if(e){b[c+1][d+e-2]=h;b[c][d]=" ";continue a}}}break}b.map(b=>b.join).join\n')


## Examples

// Here I assume that you've assigned the above function to fall
console.log(fall(
(__)
(oo)
/------\/
/ |    ||
*  /\---/\\
~~   ~~
..."Have you mooed today?"...))


Output:

                -
/--(-\--(__
/|~~---/~||/oo))
..."Have*you/mooed~today?"...


Another example:

console.log(fall(
(\__/)  .~    ~. ))
/O O  ./      .'
{O__,   \    {
/ .  . )    \\
|-| '-' \    }
.(   _(   )_.'
'---.~_ _ _&))


Output:

    _ , /
OO/__'_.. .
{.(|-|.(O'))/.~{
/('---.~___-_&)_.'}\~.'))


## Ungolfed function

function fall(input) {
let move = true
let lines = input.split("\n").map(line => line.split(""))
let isSpace = c => c == null || c == " "
loop: for (;;) {
for (let y = 0; y < lines.length - 1; y++) {
let line = lines[y]
for (let x = 0; x < line.length; x++) {
let ch = line[x]
if (!isSpace(ch)) {
let dx = 0
if (isSpace(lines[y+1][x])) { dx = 2 }
else if (isSpace(lines[y+1][x-1])) { dx = 1 }
else if (isSpace(lines[y+1][x+1])) { dx = 3 }
if (dx) {
lines[y + 1][x + dx - 2] = ch
lines[y][x] = " "
continue loop
}
}
}
}
break
}
return lines.map(line => line.join("")).join("\n")
}

• A short way to test for not blank is c>" " where c` represents the character you are testing. – Neil Nov 30 '16 at 21:40