W tym wyzwaniu otrzymasz mapę dwuwymiarowego terenu widzianego z boku. Niestety niektóre części terenu unoszą się w powietrzu, co oznacza, że ​​spadną. Twoim zadaniem jest przewidzieć, gdzie wylądują.

Wejście

Twoje dane wejściowe to jeden lub więcej ciągów oddzielonych znakiem nowej linii o równej długości, zawierających tylko znaki #(znak liczbowy, oznaczający skałę) lub .(kropka, oznaczająca puste miejsce).

Wyjście

Twoje dane wyjściowe mają ten sam format co dane wejściowe, ale z następującą modyfikacją. Zobaczmy łańcuch wejściowy jako dwuwymiarową siatkę skał. Każda skała na wejściu, która jest połączona z dnem siatki ścieżką sąsiednich skał, jest twarda ; inne skały są luźne . Skały przyległe po przekątnej nie są uważane za sąsiadujące. Wszystkie luźne skały spadną prosto w dół i wylądują jako stos na twardej skale lub w dolnym rzędzie. Luźne skały nie są ze sobą połączone, więc spadają indywidualnie, a nie jako duże formacje. Dane wyjściowe to wynikowa siatka.

Przykłady

• Dane wejściowe

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

  nie zawiera luźnych kamieni, więc wynik jest z nim identyczny.

• Dane wejściowe

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

  zawiera jedną luźną skałę u góry, która spada na twardą skałę pod nią. Dane wyjściowe to

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

• Dane wejściowe

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

  ma dużą grupę luźnych kamieni po lewej stronie. Grupa rozpada się, gdy skały spadają, więc wynik jest

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

Wyjaśnienia

• Możesz albo pobrać dane wejściowe ze STDIN, a dane wyjściowe do STDOUT, lub napisać funkcję.
• To jest golf golfowy, więc zwycięzcą jest najkrótszy program (w bajtach).
• Standardowe luki są niedozwolone.

CJam, 180 ... 133 101 ... 94 90 87 bajtów

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

Gra w golfa jest zdecydowanie możliwa, ale chciałem opublikować ją po tym, jak całkowicie zacznie działać.

Spójrz ma! Brak pasków przewijania!

Pobiera siatkę skał (utworzoną .i #bez nowej linii) ze STDIN i drukuje dane wyjściowe do STDOUT

AKTUALIZACJA : Wykorzystanie nieefektywnego, ale krótszego częściowego wypełnienia powodziowego w celu wykrycia twardych skał.

AKTUALIZACJA 2 : Zmieniono algorytm powodujący opadanie skał. Znacznie krótszy teraz!

AKTUALIZACJA 3 : Dokonałem kilku drobnych optymalizacji i ostatecznie udało mi się zmniejszyć liczbę bajtów do połowy oryginalnego kodu!

Jak to działa :

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

W przypadku wypełnienia zalewowego iterujemy razy całą długość siatki (siatki). W każdej iteracji gwarantujemy konwersję co najmniej 1, #który bezpośrednio dotyka spacji na (spację). Przestrzeń tutaj reprezentuje mocną grupę rockową. Zatem na końcu iteracji długości (siatki) gwarantujemy, że wszystkie twarde skały będą reprezentowane przez spacje.

Wypróbuj online tutaj

Perl 5: 98

98 w tym 2 flagi wiersza poleceń.

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

Wyjaśnienie:

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

Jako funkcja z parametrem ciągu i zwracaniem ciągu.

Najpierw dodaj dolny wiersz „1”, aby zidentyfikować linię podłoża.
Pierwsze wyszukiwanie pętli dla ustalonych skał (które znajdują się w pobliżu „1”) i oznacza je również jako „1”. Wyszukiwanie jest powtarzane, dopóki nie zostaną znalezione twarde skały.
Druga pętla przesuwa pozostałe znaki „#” w kierunku dolnego rzędu. Ponownie, powtarza się to, dopóki nie można przenieść skały.
Na koniec zamień ponownie „1” na „#” i wytnij dolny rząd.

Mniej golfa

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 (możesz mieć dowód na to, jakie skały są twarde, a które spadły)

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

Ponieważ, o ile mi wiadomo, nie jest możliwe wprowadzanie nowych wierszy po wyświetleniu monitu, program ten przyjmuje macierz znaków jako dane wejściowe.

Zastosowany algorytm najpierw przekształca się w macierz binarną ( 0jest powietrzem i 1skałą), a następnie wypełnia zalew z dolnego rzędu, aby oznaczyć twarde skały jako 2. Następnie podziel każdą kolumnę na „przestrzenie między twardymi skałami” i uporządkuj każdą przegrodę, aby luźna skała „spadła” w powietrze.

Edycja1: Grałeś w golfa przy użyciu innego algorytmu wypełniania zalewem

Testy przebiegają

Uruchom 1

Zdefiniuj matrycę znaków Ai wydrukuje ją:

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

Następnie wprowadź Ado programu:

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

Uruchom 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 bajty

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

Powódź wypełnia skały od dołu, a następnie spuszcza skały niewypełnione. Wykorzystuje dużo rekurencji z wypełnieniem powodziowym, więc może nieco opóźnić przeglądarkę.

To funkcja - nazwij to za pomocą g("input")

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

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

Python 3, 364 bajty

Jestem pewien, że można by z tego wycisnąć więcej ... ale i tak nigdy nie będzie konkurować z CJamem i Perlem.

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

Podobne do innych odpowiedzi. Jednym dziwactwem jest to, że najpierw odwraca siatkę do góry nogami (aby uczynić indeksy pętlowe wygodniejszymi) i dodaje dodatkowy wiersz i kolumnę .(aby uniknąć problemów z zawijaniem -1indeksów). Uruchom, dzwoniąc P(string).