En este desafío, se te da un mapa de un terreno bidimensional, visto desde un lado. Desafortunadamente, algunas partes del terreno están flotando en el aire, lo que significa que se derrumbarán. Su trabajo es predecir dónde aterrizan.

La entrada

Su entrada es una o más cadenas separadas por una nueva línea de igual longitud, que contiene solo los caracteres #(un signo de número, que significa una roca) o .(un punto, que significa espacio vacío).

La salida

Su salida tiene el mismo formato que la entrada, pero con la siguiente modificación. Veamos la cadena de entrada como una cuadrícula de rocas bidimensional. Cada roca en la entrada que está conectada al fondo de la cuadrícula por un camino de rocas adyacentes es firme ; Otras rocas están sueltas . Las rocas adyacentes en diagonal no se consideran adyacentes. Todas las rocas sueltas caerán hacia abajo y terminarán como una pila encima de una roca firme o en la fila inferior. Las rocas sueltas no están unidas entre sí, por lo que caen individualmente, no como formaciones grandes. La salida es la cuadrícula resultante.

Ejemplos

• La entrada

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

  no contiene rocas sueltas, por lo que la salida es idéntica.

• La entrada

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

  contiene una roca suelta en la parte superior, que cae sobre la roca firme debajo de ella. La salida es

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

• La entrada

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

  tiene un gran grupo de rocas sueltas a la izquierda. El grupo se descompone a medida que caen las rocas, por lo que la salida es

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

Aclaraciones

• Puede tomar la entrada de STDIN y la salida a STDOUT, o escribir una función.
• Este es el código de golf, por lo que el programa más corto (en bytes) es el ganador.
• Las lagunas estándar no están permitidas.

CJam, 180 ... 133101 ... 94 90 87 bytes

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

Definitivamente hay muchos campos de golf posibles, pero quería publicarlo primero después de que funcionara por completo.

Mira ma! No hay barras de desplazamiento!

Toma la cuadrícula de rocas (compuesta .y #sin una nueva línea final) de STDIN e imprime la salida en STDOUT

ACTUALIZACIÓN : Uso de un relleno de inundación parcial ineficiente pero más corto para descubrir rocas firmes.

ACTUALIZACIÓN 2 : Cambió el algoritmo para hacer que las rocas caigan. Mucho más corto ahora!

ACTUALIZACIÓN 3 : ¡Hice varias pequeñas optimizaciones y al final pude reducir el conteo de bytes a la mitad del código original!

Cómo funciona :

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";

Para el relleno, iteramos a través de toda la longitud de la cuadrícula (cuadrícula) veces. En cada iteración, tenemos la garantía de convertir al menos 1 #que está tocando directamente un espacio en (espacio). El espacio aquí representa un grupo de rock firme. Por lo tanto, al final de las iteraciones de longitud (cuadrícula), tenemos la garantía de tener todas las rocas firmes representadas por espacios.

Pruébalo en línea aquí

Perl 5: 98

98 incluyendo 2 banderas de línea de comando.

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

Explicación:

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

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

Como una función con un parámetro de cadena y devolviendo una cadena.

Al principio, agregue una fila inferior de '1' para identificar la línea de tierra.
El primer ciclo busca las rocas fijas (que están cerca de un '1') y también las marca como '1'. La búsqueda se repite hasta que no se encuentren más rocas firmes.
El segundo bucle mueve los caracteres '#' restantes hacia la fila inferior. Nuevamente, esto se repite hasta que no se pueda mover la roca.
Por último, reemplace el '1' con '#' nuevamente y corte la fila inferior.

Menos golf

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

Prueba (puede tener evidencia de qué rocas son firmes y qué han caído)

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

APL, 130 119

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

Como no es posible (hasta donde yo sé) ingresar nuevas líneas cuando se solicita la entrada, este programa toma una matriz de caracteres como entrada.

El algoritmo usado es primero convirtiendo a una matriz binaria ( 0es aire y 1es roca) luego inundar el llenado de la fila inferior para marcar rocas firmes como 2. Luego divida cada columna en "espacios entre rocas firmes" y clasifique cada partición para hacer que la roca suelta "caiga" por el aire.

Edit1: Golfed algunos utilizando un algoritmo de relleno de inundación diferente

Pruebas de funcionamiento

Correr 1

Define una matriz de caracteres Ay la imprime:

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

Luego alimente Ael programa:

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

Correr 2

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

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,"#")};

Las inundaciones llenan las rocas del fondo y luego las derriban. Utiliza mucha recursividad con el relleno de inundación, por lo que puede retrasar un poco su navegador.

Es una función: llámalo con g("input")

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

JSFiddle sin golf: http://jsfiddle.net/mh66xge6/

Python 3, 364 bytes

Estoy seguro de que se podría sacar más de esto ... pero nunca va a competir con CJam y Perl de todos modos.

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 a otras respuestas. Una peculiaridad es que primero pone la cuadrícula al revés (para que los índices de bucle sean más convenientes) y agrega una fila y columna adicionales de .(para evitar problemas con los -1índices de ajuste). Ejecutar llamando P(string).