Predict the Falling Rocks

Question

In this challenge, you are given a map of a two-dimensional terrain, viewed from the side. Unfortunately, some parts of the terrain are floating in the air, which means they'll come crashing down. Your job is to predict where they land.

The Input

Your input is one or more newline-separated strings of equal lengths, containing only the characters # (a number sign, signifying a rock) or . (a period, signifying empty space).

The Output

Your output has the same format as the input, but with the following modification. Let us view the input string as a two-dimensional grid of rocks. Every rock in the input which is connected to the bottom of the grid by a path of adjacent rocks is firm; other rocks are loose. Diagonally adjacent rocks are not considered to be adjacent. All the loose rocks will fall straight down, and end up as a stack on top of either a firm rock or the bottom row. The loose rocks are not attached to each other, so they fall individually, not as big formations. The output is the resulting grid.

Examples

• The input

  ..###.
  .##.#.
  .#....
  .##.#.
  

  contains no loose rocks, so the output is identical to it.

• The input

  ...#..
  .#..#.
  .#..##
  .#...#
  .#####
  .#...#
  

  contains one loose rock at the top, which falls down on the firm rock under it. The output is

  ......
  .#..#.
  .#..##
  .#.#.#
  .#####
  .#...#
  

• The input

  .#####....
  .#....####
  ###.###..#
  #.#...##..
  .####..#.#
  ......###.
  ..#...#..#
  ..#...#..#
  

  has a large group of loose rocks on the left. The group breaks down as the rocks fall, so the output is

  ..........
  ....######
  ..#.###..#
  . #...##..
  .##....#..
  .##...####
  ####..#..#
  #####.#..#
  

Clarifications

• You can either take the input from STDIN and output to STDOUT, or write a function.
• This is code-golf, so shortest program (in bytes) is the winner.
• Standard loopholes are disallowed.

Answer 1

CJam, 180 ... 133 101 ... 94 90 87 bytes

qN/~'#/S*_,):L;]N*_,_,*{:A1$='#={[W1LL~)]Af+{W>},1$f=S&,{ASct}*}*}/N/z{S/{$W%}%'#*}%zN*

There is definitely lots of golfing possible, but I wanted to post it first after getting it to work completely.

Look ma! No scrollbars!

Takes the rocks grid (made up of . and # without a trailing newline) from STDIN and prints the output to STDOUT

UPDATE : Using an inefficient but shorter partial flood fill to figure out firm rocks.

UPDATE 2: Changed the algorithm for making the rocks fall down. Much shorter now!

UPDATE 3: Did several small optimizations and in the end I was able to bring down the byte count to half of the original code!

How it works:

qN/~'#/S*_,):L;]N*             "Preparations";
qN/~                           "Read the input, split by new line and expand the array";
    '#/S*                      "In the last row, replace # by space";
         _,):L                 "Copy the last row and store length + 1 in L";
              ;]N*             "Pop the length, wrap everything in array and join by \n";

_,_,*{ ... }/                  "Flood fill";
_,                             "Copy the array and calculate its length";
  _,                           "Copy the length and calculate [0 - length] array";
    *                          "Repeat the above array, length times";
     { ... }/                  "Run the code block on each element of the array";

:A1$='#={ ... }*               "Process only #";
:A1$                           "Store the number in A and copy the input array to stack";
    =                          "Get Ath index element from input array";
     '#={ ... }*               "Run the code block if Ath element equals #";

[W1LL~)]Af+{W>},1$f=S&,{ASct}* "Flood fill spaces";
[W1LL~)]Af+                    "Get the indexes of the 4 elements on the cross formed by"
                               "the Ath index";
           {W>},               "Filter out the negative values";
                1$f=           "For each of the index, get the char from input string";
                    S&,        "Check if space is one of the 4 chars from above step";
                       {    }* "Run the code block if space is present";
                        ASct   "Make the Ath character of input string as space";

N/z{S/{$W%}%'#*}%zN*           "Let the rocks fall";
N/z                            "Split the resultant string by newlines and"
                               "transpose the matrix";
   {           }%              "Run the code block for each row (column of original)";
    S/{   }%                   "Split by space and run the code block for each part";
       $W%                     "Sort and reverse. This makes # come down and . to go up";
            '#*                "Join by 3, effectively replacing back spaces with #";
                 zN*           "Transpose to get back final matrix and join by newline";

For the floodfill, we iterate through the whole grid length(grid) times. In each iteration, we are guaranteed to convert at least 1 # which is directly touching a space to (space). Space here represents a firm rock group. Thus at the end of length(grid) iterations, we are guaranteed to have all firm rocks represented by spaces.

Try it online here

Answer 2

Perl 5: 98

98 including 2 command line flags.

#!perl -p0
1while/
/,($x="($`)")=~y!#!.!,s/#(.*
$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;1while s/#$x\./.$1#/s;y!%!#!

Explanation:

#!perl -p0 #read entire input to $_ and print at the end
/\n/;($x="($`)")=~y!#!.!; #calculate pattern matching space
                          #between two characters in the same column
                          #looks like "(......)" 
1 while s/#(.*\n$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;
                          #flood fill solid rock with %
1 while s/#$x\./.$1#/s;   #drop loose rock
y!%!#!                    #change % back to #

Answer 3

JavaScript (ES6) 232

s=>{for(s=[...s+'1'.repeat(r=1+s.search('\n'))];s=s.map((c,p)=>c=='#'&(s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f;);for(;s.map((c,p)=>c=='#'&s[p+r]=='.'&&(s[p]='.',f=s[p+r]=c),f=0),f;);return s.join('').replace(/1/g,rok).slice(0,-r)}

As a function with a string parameter and returning a string.

At first, add a bottom row of '1' to identify the ground line.
The first loop search for the fixed rocks (that are near a '1') and marks them as '1' as well.The search is repeated until no more firm rocks are found.
The second loop move the remaining '#' characters towards the bottom row. Again, this is repeated until no rock can be moved.
At last, replace the '1' with '#' again and cut the bottom row.

Less golfed

s=>{
  r = 1+s.search('\n');
  s = [...s+'1'.repeat(r)];
  for (; s = s.map((c,p) => c=='#' & (s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f; );
  for (; s.map((c,p) => c=='#' & s[p+r]=='.'&& (s[p] ='.', s[p+r]=c, f=1),f=0),f; );
  return s.join('')
    .replace(/1/g,'#')
    .slice(0,-r)
}

Test (You can have evidence of what rocks are firm and what have fallen)

F=
s=>{for(s=[...s+'1'.repeat(r=1+s.search('\n'))];s=s.map((c,p)=>c=='#'&(s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f;);for(;s.map((c,p)=>c=='#'&s[p+r]=='.'&&(s[p]='.',f=s[p+r]=c),f=0),f;);return s.join('').replace(/1/g,rok).slice(0,-r)}

var rok // using rok that is 3 chars like '#'

function update() {
  rok = C.checked ? '@' : '#';
  O.textContent=F(I.textContent)
}

update()

td { padding: 5px }
pre { border: 1px solid #000; margin:0 }

<table><tr><td>Input</td><td>Output</td></tr>
<tr><td><pre id=I>.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#</pre></td>
<td><pre id=O></pre>
</td></tr></table>
<input type='checkbox' id=C oninput='update()'>Show firm rocks

Answer 4

APL, 130 119

'.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓ ⍉⊃⌈/(1,¨⍳⍴⊃↓x){x←⍵⋄(⍺⌷x)∧←2⋄x≡⍵:x⋄⊃⌈/((⊂⍴⍵)⌊¨1⌈(,∘-⍨↓∘.=⍨⍳2)+⊂⍺)∇¨⊂x}¨⊂⊖'#'=x←⎕]

Since it is not possible (as far as I know) to enter newlines when input is prompted, this program takes a character matrix as input.

The algorithm used is first converting to a binary matrix (0 is air and 1 is rock) then flood filling from the bottom row to mark firm rocks as 2. Then partition each column into "spaces between firm rocks" and sort each partition to make the loose rock "fall through" the air.

Edit1: Golfed some using a different flood fill algorithm

---

Test runs

Run 1

Define a character matrix A and prints it:

      A←↑('.#####....') ('.#....####') ('###.###..#') ('#.#...##..') ('.####..#.#') ('......###.') ('..#...#..#') ('..#...#..#')
      A
.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#

Then feed A into the program:

      '.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓⍉(1,¨⍳⊃⌽⍴x){⍵≡y←⊃⌈/x←⍺{x←⍵⋄(⍺⌷x)∧←2⋄x}¨⊂⍵:y⋄((⊂⍴⍵)⌊¨1⌈,(,∘-⍨↓∘.=⍨⍳2)∘.+⍺/⍨x≢¨⊂⍵)∇y}⊖'#'=x←⎕]
⎕:
      A
..........
....######
..#.###..#
..#...##..
.##....#..
.##...####
####..#..#
#####.#..#

Run 2

      A←↑('#######')('#.....#')('#.#.#.#')('#.....#')('#######')
      A
#######
#.....#
#.#.#.#
#.....#
#######
      '.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓⍉(1,¨⍳⊃⌽⍴x){⍵≡y←⊃⌈/x←⍺{x←⍵⋄(⍺⌷x)∧←2⋄x}¨⊂⍵:y⋄((⊂⍴⍵)⌊¨1⌈,(,∘-⍨↓∘.=⍨⍳2)∘.+⍺/⍨x≢¨⊂⍵)∇y}⊖'#'=x←⎕]
⎕:
      A
#######
#.....#
#.....#
#.#.#.#
#######

Answer 5

JS - 443 bytes

function g(b){function f(b,c,e){return b.substr(0,c)+e+b.substr(c+1)}function e(d,c){"#"==b[c][d]&&(b[c]=f(b[c],d,"F"),1<d&&e(d-1,c),d<w-1&&e(d+1,c),1<c&&e(d,c-1),c<h-1&&e(d,c+1))}b=b.split("\n");w=b[0].length;h=b.length;for(i=0;i<w;i++)"#"==b[h-1][i]&&e(i,h-1);for(j=h-2;-1<j;j--)for(i=0;i<w;i++)if(k=j+1,"#"==b[j][i]){for(;k<h&&"F"!=b[k][i]&&"#"!=b[k][i];)k++;k--;b[j]=f(b[j],i,".");b[k]=f(b[k],i,"#")}return b.join("\n").replace(/F/g,"#")};

Flood fills rocks from the bottom, then brings un-flood-filled rocks down. Uses a lot of recursion with the flood fill so it may lag your browser for a bit.

It's a function - call it with g("input")

JSFiddle: http://jsfiddle.net/mh66xge6/1/

Ungolfed JSFiddle: http://jsfiddle.net/mh66xge6/

Answer 6

Python 3, 364 bytes

I'm sure more could be squeezed out of this... but it's never going to compete with CJam and Perl anyway.

z="%";R=range
def F(r,c,g):
 if z>g[r][c]:g[r][c]=z;[F(r+d%2*(d-2),c+(d%2-1)*(d-1),g)for d in R(4)]
def P(s):
 t=s.split()[::-1];w=len(t[0]);g=[list(r+".")for r in t+["."*w]];[F(0,c,g)for c in R(w)]
 for c in R(w):
  for r in R(len(g)):
   while g[r][c]<z<g[r-1][c]and r:g[r][c],g[r-1][c]=".#";r-=1
 return"\n".join(''.join(r[:w])for r in g[-2::-1]).replace(z,"#")

Similar to other answers. One quirk is that it turns the grid upside down first (to make the loop indices more convenient) and adds an extra row & column of . (to avoid problems with wrapping -1 indices). Run by calling P(string).