In dieser Herausforderung erhalten Sie eine Karte eines zweidimensionalen Geländes, von der Seite gesehen. Leider schweben einige Teile des Geländes in der Luft, was bedeutet, dass sie abstürzen. Ihre Aufgabe ist es, vorherzusagen, wo sie landen.

Die Eingabe

Ihre Eingabe besteht aus einer oder mehreren durch Zeilenumbrüche getrennten Zeichenfolgen gleicher Länge, die nur die Zeichen #(ein Zahlenzeichen , das einen Stein kennzeichnet) oder .(einen Punkt, das Leerzeichen kennzeichnet) enthalten.

Die Ausgabe

Ihre Ausgabe hat dasselbe Format wie die Eingabe, jedoch mit der folgenden Änderung. Betrachten wir die Eingabezeichenfolge als zweidimensionales Gitter aus Steinen. Jeder Felsen im Eingang, der durch einen Pfad benachbarter Felsen mit dem Boden des Gitters verbunden ist, ist fest ; andere felsen sind lose . Diagonal benachbarte Gesteine ​​gelten nicht als benachbart. Alle losen Steine ​​fallen gerade nach unten und enden als Stapel auf einem festen Stein oder der unteren Reihe. Die losen Steine ​​sind nicht aneinander gebunden, daher fallen sie einzeln nicht als große Formationen aus. Die Ausgabe ist das resultierende Raster.

Beispiele

• Die Eingabe

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

  enthält keine losen Steine, daher ist die Ausgabe identisch.

• Die Eingabe

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

  enthält oben einen losen Stein, der auf den festen Stein darunter fällt. Die Ausgabe ist

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

• Die Eingabe

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

  hat eine große Gruppe von losen Steinen auf der linken Seite. Die Gruppe zerfällt, wenn die Steine ​​fallen, und der Output ist

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

Klarstellungen

• Sie können entweder die Eingabe von STDIN übernehmen und an STDOUT ausgeben oder eine Funktion schreiben.
• Dies ist Code-Golf, also ist das kürzeste Programm (in Bytes) der Gewinner.
• Standardlücken sind nicht zulässig.

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*

Es ist definitiv viel Golf möglich, aber ich wollte es erst posten, nachdem es vollständig funktioniert hat.

Schau ma! Keine Bildlaufleisten!

Nimmt das Rocks-Raster (bestehend aus .und #ohne abschließenden Zeilenumbruch) von STDIN und druckt die Ausgabe an STDOUT

UPDATE : Verwenden einer ineffizienten, aber kürzeren Teilflutfüllung, um feste Gesteine ​​zu ermitteln.

UPDATE 2 : Der Algorithmus zum Herunterfallen der Steine ​​wurde geändert. Jetzt viel kürzer!

UPDATE 3 : Habe einige kleine Optimierungen vorgenommen und am Ende konnte ich die Byteanzahl auf die Hälfte des ursprünglichen Codes senken!

Wie es funktioniert :

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

Für die Überflutung durchlaufen wir die gesamten Rasterlängen- (Raster-) Zeiten. In jeder Iteration wird garantiert, dass mindestens 1, #das ein Leerzeichen direkt berührt, in (Leerzeichen) konvertiert wird . Der Raum repräsentiert hier eine feste Rockgruppe. Somit ist am Ende der Längeniterationen (Gitteriterationen) garantiert, dass alle festen Gesteine ​​durch Leerzeichen dargestellt werden.

Probieren Sie es hier online aus

Perl 5: 98

98 einschließlich 2 Befehlszeilenflags.

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

Erläuterung:

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

Als Funktion mit einem String-Parameter und Rückgabe eines Strings.

Fügen Sie zunächst eine untere Zeile mit '1' hinzu, um die Erdungslinie zu identifizieren.
Die erste Schleife sucht nach den festen Steinen (die sich in der Nähe einer '1' befinden) und markiert sie ebenfalls als '1'. Die Suche wird wiederholt, bis keine festen Steine ​​mehr gefunden werden.
Die zweite Schleife verschiebt die verbleibenden '#' Zeichen in die untere Reihe. Dies wird wiederholt, bis kein Stein mehr bewegt werden kann.
Ersetzen Sie zuletzt die '1' erneut durch '#' und schneiden Sie die untere Reihe aus.

Weniger golfen

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 (Sie können nachweisen, welche Steine ​​fest sind und welche gefallen sind)

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←⎕]

Da es meines Wissens nicht möglich ist, bei Eingabeaufforderung Zeilenumbrüche einzugeben, verwendet dieses Programm eine Zeichenmatrix als Eingabe.

Der verwendete Algorithmus konvertiert zuerst in eine binäre Matrix ( 0ist Luft und 1ist Gestein) und füllt dann die unterste Reihe mit einer Flut, um festes Gestein als zu markieren 2. Teilen Sie dann jede Säule in "Zwischenräume zwischen festen Steinen" und sortieren Sie jede Trennwand so, dass der lose Stein "durch die Luft fällt".

Edit1: Golf einige mit einem anderen Flood-Fill-Algorithmus

Testläufe

Führen Sie 1 aus

Definieren Sie eine Zeichenmatrix Aund drucken Sie diese aus:

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

Dann Ain das Programm einspeisen:

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

Führen Sie 2 aus

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

Überflutung füllt die Steine ​​von unten und bringt die nicht überfluteten Steine ​​nach unten. Verwendet eine Menge Rekursion bei der Überflutung, so dass Ihr Browser möglicherweise eine Weile nachlässt.

Es ist eine Funktion - nennen Sie es mit g("input")

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

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

Python 3, 364 Bytes

Ich bin sicher, es könnte noch mehr daraus werden ... aber es wird sowieso nie mit CJam und Perl konkurrieren.

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

Ähnlich wie bei anderen Antworten. Eine Besonderheit ist, dass das Raster zuerst auf den Kopf gestellt wird (um die Schleifenindizes bequemer zu machen) und eine zusätzliche Zeile und Spalte .hinzugefügt -1werden (um Probleme beim Umbrechen von Indizes zu vermeiden ). Laufen Sie mit einem Anruf P(string).