Przewróć stos piasku

12

(Istnieją pokrewne pytania dotyczące nieskończonych piaskowców i znajdowania elementów tożsamości piaskowców .)

Biorąc pod uwagę macierz nieujemnych liczb całkowitych, zwróć macierz o takich samych wymiarach, ale przewrócona :

  1. Jeśli macierz nie zawiera wartości większych niż 4, zwróć ją.
  2. Każda „komórka”, która jest większa niż 3, zostaje zmniejszona o 4, a wszystkie bezpośrednio sąsiadujące komórki (powyżej, poniżej, lewej i prawej) są zwiększane, jeśli istnieją.
  3. GOTO 1.

Przykłady:

0 1 0        0 2 0
2 4 0   ->   3 0 1
0 0 3        0 1 3

1 2 3    2 3 4    2 5 1    4 1 2    0 3 3    0 3 3    0 3 3
4 5 6 -> 2 4 4 -> 4 2 3 -> 0 5 4 -> 3 2 1 -> 3 3 1 -> 3 3 2
7 8 9    5 7 7    2 6 5    4 3 2    0 5 3    1 1 4    1 2 0

(Musisz tylko zwrócić wynik końcowy. Ścieżka, na którą do niego dojdziesz, może różnić się od pokazanej tutaj: nie ma znaczenia, w jakiej kolejności wykonujesz operacje obalenia, wszystkie prowadzą do tego samego wyniku).

W celu uzyskania głębszego wyjaśnienia i pewnej motywacji zobacz ten film Numberphile lub artykuł w Wikipedii na temat modelu Abelian Sandpile .

Zasady:

  • Możesz pobierać dane wejściowe i wyjściowe na dowolny ze standardowych sposobów
  • Luki są zabronione
  • Dane wejściowe i wyjściowe mogą być:
    • zagnieżdżona lista: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    • prosta lista: [1, 2, 3, 4, 5, 6, 7, 8, 9]i kształt
    • jakiś rodzimy typ macierzy
    • ciąg, np 1 2 3\n4 5 6\n7 8 9
    • lub cokolwiek innego, co działa w twoim języku.
  • Dane wejściowe i wyjściowe muszą być w tej samej formie
  • Dane wejściowe mogą zawierać większe liczby niż te pokazane tutaj, ale rozmiar może być ograniczony przez ograniczenia twojego języka (odpowiedniki MAXINT, jeśli dotyczy)
  • Matryca może mieć dowolny kształt (np. 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
  • Nie musisz zajmować się przypadkiem, w którym kształt ma wartość 0xN lub Nx0.

Przypadki testowe

[[2, 5, 4], [8, 6, 4], [1, 2, 3]] -> [[3, 3, 0], [1, 2, 2], [1, 3, 2]]
[[0, 0, 2], [1, 3, 3], [0, 0, 0]] -> [[0, 0, 2], [1, 3, 3], [0, 0, 0]]
[[9, 9, 9], [9, 9, 9], [9, 9, 9]] -> [[1, 3, 1], [3, 1, 3], [1, 3, 1]]
[[4, 5], [2, 3]] -> [[2, 3], [0, 1]]
[[2, 3, 5], [2, 2, 0]] -> [[3, 0, 2], [2, 3, 1]]
[[7]] -> [[3]]

To jest , najkrótszy kod (na język).

L3viathan
źródło
Czy można wyświetlać wszystkie wyniki pośrednie?
feersum
@feersum Chyba tak, o ile jest jasne, jaki jest końcowy wynik.
L3viathan

Odpowiedzi:

8

MATL , 17 bajtów

tss:"t3>t1Y6Z+w4*-+

Wypróbuj w MATL Online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Program iteruje tyle razy, ile suma danych wejściowych. Jest to luźna górna granica wymaganej liczby iteracji.

Dla każdej iteracji 3wykrywane są przekroczenia matrycy stosu piasku , co daje macierz 1i 0, która jest spleciona z maską 4-sąsiednią. Wpisy przekraczające 3w macierzy piasku są zmniejszane o 4i dodawany jest wynik splotu.

Dla ostatnich iteracji, w których macierz piasku nie ma żadnych liczb przekraczających 3, zera są odejmowane i dodawane do niej, więc nie ma to wpływu.

t       % Implicit input (matrix). Duplicate
ss      % Sum of matrix entries
:"      % Repeat that many times
  t     %   Duplicate
  3>    %   True for matrix entries that exceed 3
  t     %   Duplicate
  1Y6   %   Push predefined literal [0, 1, 0; 1, 0, 1; 0, 1, 0]
  Z+    %   2D convolution, keeping size
  w     %   Swap
  4*    %   Multiply by 4
  -     %   Subtract
  +     %   Add
        % Implicit end. Implicit display
Luis Mendo
źródło
3
Piąta konwencja.
Martin Ender
@MartinEnder Ah, również używałeś tego :-) Miło widzieć kolegę zwojnika! Jestem pewien, że flawr wkrótce do nas dołączy
Luis Mendo
2
@LuisMendo Convolutionista
Suever
4

Mathematica, 65 bajtów

#//.s_:>s+ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]-4x&

Wyjaśnienie

#//.s_:>...&

Wielokrotnie przekształcaj dane wejściowe, przewracając wszystkie stosy większe niż 3. Proces ten zatrzymuje się automatycznie, gdy transformacja nie zmieni matrycy (tj. Gdy nie ma już dużych stosów). W poniższym wyrażeniu wywoływana jest macierz s.

...x=UnitStep[s-4]...

Utwórz macierz, która ma 1ilekroć bieżąca macierz ma a 4lub większą, a zero w przeciwnym razie. Zasadniczo jest to maska ​​wskazująca, które stosy należy obalić. Zadzwoń do maski x.

ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]

Najpierw obliczamy liczbę piasku dodawanego do każdego stosu ze względu na przewrócone sąsiednie stosy. Odbywa się to poprzez splot następującej matrycy x:

0 1 0
1 0 1
0 1 0

Zasadniczo dodaje jeden do bieżącej komórki dla każdego z sąsiadów von-Neumanna w masce.

s+...-4x

Dodajemy poprzedni wynik, sa następnie odejmujemy od niego czterokrotnie maskę, aby zmniejszyć przewrócone stosy.

Martin Ender
źródło
3

Oktawa, 65 bajtów

To nie wydaje się zbyt dobre, chyba brakuje mi trików ...

m=input(0);do;m+=conv2(m>3,[0 1 0;1 -4 1;0 1 0],"same")
until m<4
feersum
źródło
Jakiej wersji Octave używasz, która pozwala input(0)?
Suever
@Suever >> version ans = 4.0.1
feersum
2

JavaScript (ES6), 101 95 bajtów

Pobiera szerokość macierzy wi tablicę wartości aw składni curry (w)(a). Zwraca tablicę wartości.

w=>g=a=>(b=a.map((n,i)=>n%4+(F=d=>~m|i%w&&a[i+d]>>2)(m=w)+F(-w)+F(m=-1)+F(!++i)))+0==a+0?a:g(b)

Sformatowane i skomentowane

w =>                      // main function: takes w as input, returns g
  g = a =>                // recursive function g: takes a as input
    (                     //
      b = a.map((n, i) => // for each element n at position i in a:
        n % 4 + (         //   keep only n MOD 4
          F = d =>        //   define F(): function that takes d as input
            ~m |          //     if m is not equal to -1
            i % w &&      //     or i MOD w is not null:
            a[i + d] >> 2 //       return a fourth of the value of the cell at i + d
        )(m = w) +        //   test the cell below the current cell
        F(-w) +           //   test the cell above
        F(m = -1) +       //   test the cell on the left
        F(!++i)           //   test the cell on the right
      )                   // end of map(): assign the result to b
    ) + 0 == a + 0 ?      // if b is equal to a:
      a                   //   stop recursion and return a
    :                     // else:
      g(b)                //   do a recursive call with b

Przypadki testowe

Arnauld
źródło
1

JavaScript (ES6), 118 114 104 bajtów

Zaoszczędź 2 bajty dzięki @Neil

f=a=>a.find(b=>++y&&b.find(c=>++x&&c>3,x=0),y=0)?f(a.map(b=>b.map(c=>c+=--i|y?i*i+y*y==1:-4,i=x,--y))):a
ETHprodukcje
źródło
Czy (i-=x)|y-j?i*i+pomaga
Neil
@Neil To prawda, dzięki!
ETHprodukcje
... rozmawiałem przez telefon, ale zastanawiałem się również a.find(...b.find(...c>3&&a.map(...)))&&f(a).
Neil
@Neil Nie sądzę, żeby to zadziałało, ponieważ .mapnie
mutuje
Wygląda na to, że zmutowanie kosztuje nieco mniej niż przeniesienie mapy wewnątrz znaleziska, co oszczędza:f=a=>a.find((b,x)=>b.find((c,y)=>c>3&&a.map(b=>b.map((_,j)=>b[j]+=x|(j-=y)?x*x+j*j==1:-4)&x--)))&&f(a)
Neil
1

C ++, 261 258 250 bajtów

#import<vector>
#define S size()
void f(std::vector<std::vector<int>>&m){s:int i,j,r;for(i=r=0;i<m.S;++i)for(j=0;j<m[i].S;++j){if(m[i][j]>3){r=1;m[i][j]-=4;j>0&&m[i][j-1]++;i>0&&m[i-1][j]++;j<m[i].S-1&&m[i][j+1]++;i<m.S-1&&m[i+1][j]++;}}if(r)goto s;}

Pobiera dane wejściowe jako odniesienie do wektora wektorów i modyfikuje go bezpośrednio.

Wypróbuj online!

Steadybox
źródło