Abelowa sandpile , dla naszych celów jest nieskończona siatka współrzędnych całkowitych, początkowo pusty piasku. Po każdej sekundzie ziarenko piasku umieszczane jest na (0,0). Ilekroć komórka siatki ma 4 lub więcej ziaren piasku, rozlewa jedno ziarno piasku do każdego z czterech sąsiadów jednocześnie. Sąsiedzi (x, y) to (x-1, y), (x + 1, y), (x, y-1) i (x, y + 1).

Gdy komórka się rozlewa, może to spowodować rozlanie jej sąsiadów. Kilka faktów:

• Ta kaskada ostatecznie się skończy.
• Kolejność rozlewania się komórek jest nieistotna; wynik będzie taki sam.

Przykład

Po 3 sekundach wygląda siatka

.....
.....
..3..
.....
.....

Po 4 sekundach:

.....
..1..
.1.1.
..1..
.....

Po 15 sekundach:

.....
..3..
.333.
..3..
.....

A po 16 sekundach:

..1..
.212.
11.11
.212.
..1..

Wyzwanie

W jak najmniejszej liczbie bajtów napisz funkcję, która przyjmuje pojedynczą dodatnią liczbę całkowitą t i wysyła obraz stosu piasku po t sekundach.

Wejście

Pojedyncza dodatnia liczba całkowita t , w dowolnym wybranym formacie.

Wynik

Zdjęcie stosu piasku po t sekundach przy użyciu znaków

 . 1 2 3

Edycja: użyj dowolnych czterech wyraźnych znaków lub narysuj obrazek. Jeśli nie używasz „.123” lub „0123”, podaj w odpowiedzi, co oznaczają znaki.

W przeciwieństwie do przykładów, dane wyjściowe powinny zawierać minimalną liczbę wierszy i kolumn niezbędnych do wyświetlenia niezerowej części sandpile.

Oznacza to, że dla wejścia 3 wyjście powinno być

 3

Dla 4 wyjście powinno być

 .1.
 1.1
 .1.

Punktacja

Obowiązuje standardowa punktacja golfowa.

Zasady

Niedozwolone są funkcje językowe i biblioteki, które już wiedzą, co to jest sandpile.

Edycja: Sekcja wyników została edytowana, ograniczenie zestawu znaków zostało całkowicie zniesione. Użyj dowolnych czterech różnych znaków lub kolorów, które lubisz.

R, 378 343 297 291 bajtów

Jak zwykle użytkownik dostarcza swoje dane wejściowe za pośrednictwem scan()(już użyłem zmiennej t, więc weźmy zzamiast tego), więc drugą linię należy uruchomić osobno, a następnie resztę:

e=numeric
a=1%*%scan()
x=1
o=a>3
n=1
while(any(o)){
v=which(o,T)
if(any(v==1)){a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2));x=x+1;n=n+2;v=which(a>3,T)}
q=nrow(v)
u=cbind(e(q),1)
l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1]
a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1
a[v]=a[v]-4
o=a>3}
a

Wyjścia tablicę zawierającą wartości aw ttej generacji (0, 1, 2 lub 3).

Przypadki testowe:

z=3
     [,1]
[1,]    3
z=4
     [,1] [,2] [,3]
[1,]    0    1    0
[2,]    1    0    1
[3,]    0    1    0
z=16
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    1    0    0
[2,]    0    2    1    2    0
[3,]    1    1    0    1    1
[4,]    0    2    1    2    0
[5,]    0    0    1    0    0

Pomaga nam to, że ta rzecz jest symetryczna zarówno w pionie, jak iw poziomie, co oznacza, że ​​skrajnie lewy punkt otrzymuje wysokość 4, co oznacza, że ​​najwyższe, prawe i najniższe punkty to również 4.

Aha, i czy powiedziałem, że możesz robić piękne wizualizacje?

Po 1000 kropli:

Po 50000 kroplach (≈4 sekundy):

Po 333333 kroplach (≈15 minut):

Ty też możesz to narysować!

image(1:n,1:n,a,col=colorRampPalette(c("#FFFFFF","#000000"))(4), axes=F, xlab="", ylab="")

To zajęło 4 sekundy dla 10000 iteracji, ale znacznie spowalnia dla większych rozmiarów macierzy (np. Kilka minut dla 100000 iteracji). Właśnie dlatego robi się tak wolno (oszacowałem tempo wzrostu jak i otrzymałem τ (i) ≈689 · i ^ 1,08, więc średni czas na jedno dodatkowe ziarno, aż cała kupka osiada po itym kroku jest nieco większa niż jeden) , a całkowity czas w zależności od liczby ziaren rośnie nieco wolniej niż kwadratowo (T (i) ≈0,028 * i ^ 1,74):

A teraz z pełnym wyjaśnieniem:

e=numeric # Convenient abbreviation for further repeated use
a=1%*%scan() # Creates a 1×1 array with a user-supplied number
x=1 # The coordinate of the centre
o=a>3 # Remember which cells were overflown
n=1 # Array height that is going to change over time
while(any(o)){ # If there is still any overflow
  v=which(o,T) # Get overflown cells' indices
  if(any(v==1)){ # If overflow occurred at the border, grow the array
    a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2)) # Growing
    x=x+1 # Move the centre
    n=n+2 # Change the height
    v=which(a>3,T) # Re-index the overflowed cells
    }
  q=nrow(v) # See how many indices are overflown
  u=cbind(e(q),1) # Building block for neighbours' indices
  l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1] # L, R, T, B neighbours
  a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1 # Increment neighbours
  a[v]=a[v]-4 # Remove 4 grains from the overflown indices
  o=a>3} # See if still overflown indices remain
a # Output the matrix

To pierwszy raz w moim życiu, gdy rosnące obiekty (takie jak a <- c(a, 1)) działają o wiele szybciej niż wstępnie przydzielają dużą pustą macierz dla wartości i wypełniają ją stopniowo niewykorzystaną toną zer.

Aktualizacja. Golfed 18 bajtów, usuwając arr.indz whichpowodu Billywob i zastępując rep(0,n)z e=numeric;e(n)w 5 przypadkach ze względu na JDL i 17 więcej bajtów powodu JDL .

Aktualizacja 2. Ponieważ stos piasków jest abelowy, może zaczynać się od stosu pożądanej wysokości, więc usunąłem zbędną pętlę i zyskałem ogromny wzrost wydajności!

MATL , 55 53 48 43 42 bajty

Zainspirowany odpowiedzią @ flawr .

Wyjście graficzne :

0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)1YG

Wypróbuj w MATL Online! . Wejście zajmuje około 10 sekund 30. Może być konieczne odświeżenie strony i ponowne naciśnięcie przycisku „Uruchom”, jeśli nie działa.

Oto przykładowy wynik dla danych wejściowych 100:

Wyjście ASCII (43 bajty) :

0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)48+c

Wypróbuj online!

Wyjaśnienie

0          % Push a 0. This is the initial array. Will be resized in first iteration
i:         % Take input n. Generate range [1 2 ... n]
"          % For each, i.e. repeat n times
  Gto~+    %   Push input and add negate parity. This "rounds up" n to odd number
           %   m = n or n+1
  Xy       %   Identity matrix with that size
  tP*      %   Multiply element-wise by vertically flipped copy. This produces a
           %   matrix with a 1 in the center and the rest entries equal to 0
  +        %   Add to previous array. This updates the sandpile array
  t        %   Duplicate
  "        %   For each column (i.e. repeat m times)
    t4=    %     Duplicate. Compare with 4 element-wise. This gives a 2D mask that
           %     contains 1 for entries of the sandpile array that equal 4, and 0
           %     for the rest
    t      %     Duplicate
    1Y6    %     Predefined literal: [0 1 0; 1 0 1; 0 1 0]
    Z+     %     2D convolution, maintaining size
    b      %     Bubble up to bring sandpile array to top
    +      %     Element-wise addition. This adds 1 to the neighbours of a 4
    w      %     Swap to bring copy of mask to top
    ~*     %     Multiply bu negated mask. This removes all previous 4
  ]        %  End
]          % End
t          % Duplicate the updated sandpile array
a          % 1D mask that contains 1 for columns that contain a 1. This will be
           % used as a logical index to select columns
t          % Duplicate. This will be used as logical index to select rows (this
           % can be done because of symmetry)
3$)        % Keep only those rows and columns. This trims the outer zeros in the
           % sandpile array
1YG        % Display as scaled image

Matlab, 160 156 148 bajtów

n=input('');z=zeros(3*n);z(n+1,n+1)=n;for k=1:n;x=z>3;z=z+conv2(+x,1-mod(spiral(3),2),'s');z(x)=z(x)-4;end;v=find(sum(z));z=z(v,v);[z+48-(z<1)*2,'']

Najpierw tworzona jest zbyt duża matryca, ngdzieś pośrodku. Następnie kaskadowanie jest obliczane z bardzo wygodnym splotem 2d. Na koniec nadmiar jest usuwany, a całość jest przekształcana w sznurek.

Przykładowe dane wyjściowe dla t=100

...121...
..32.23..
.3.323.3.
123.3.321
2.23.32.2
123.3.321
.3.323.3.
..32.23..
...121...

Jak zawsze:

Konwolucja jest kluczem do sukcesu.

Python 2, 195 +1 +24 = 220 217

from pylab import*
ifrom scipy.signal import convolve2d as c
k=(arange(9)%2).reshape(3,3)
def f(n):g=zeros((n,n),int);g[n/2,n/2]=n;exec"g=c(g/4,k,'same')+g%4;"*n;return g[any(g,0)].T[any(g,0)]

wyjście dla n = 16

array([[0, 0, 1, 0, 0],
       [0, 2, 1, 2, 0],
       [1, 1, 0, 1, 1],
       [0, 2, 1, 2, 0],
       [0, 0, 1, 0, 0]])

jest DUŻO niepotrzebnego wypełniania i iteracji, używając njako „wystarczającej” górnej granicy, ale n = 200 nadal ukończone w ciągu sekundy, a n = 500 w około 12 sekund

bez golfa

from pylab import*
from scipy.signal import convolve2d as c
k=array([0,1,0],
        [1,0,1],
        [0,1,0])
def f(n):
  g=zeros((n,n))                 # big grid of zeros, way bigger than necessary
  g[n/2,n/2]=n                   # put n grains in the middle
  exec"g=c(g/4,k,'same')+g%4;"*n # leave places with <4 grains as is, convolve the rest with the kernel k, repeat until convergence (and then some more)
  return g[any(g,0)].T[any(g,0)] # removes surrounding 0-rows and columns

zastąpienie return xprzez imshow(x)dodaje jeden znak i generuje brzydki interpolowany obraz, dodanie imshow(x,'gray',None,1,'nearest')usuwa rozmytą interpolację, dostosowując dane wyjściowe do specyfikacji

Perl, 157 147 bajtów

Obejmuje +1 dla -p

Uruchom z liczeniem na STDIN, drukuje mapę używając 0123do STDOUT:

sandpile.pl <<< 16

sandpile.pl:

#!/usr/bin/perl -p
map{++substr$_,y///c/2-1,1;/4
/?$.+=s%^|\z%0 x$..$/%eg+!s/\b/0/g:s^.^$&%4+grep{3<substr$\,0|$_+"@+",1}-$.-2,-2,0,$.^eg while/[4-7]/}($\="0
")x$_}{

Python 3 2, 418 385 362 342 330 bajtów

w='[(i,j)for i in r(n)for j in r(n)if a[i][j]>3]'
def f(z):
 a,x,r=[[z]],0,range
 for _ in[0]*z:
  n=len(a);v=eval(w)
  if[1for b,c in v if(b==0)+(c==0)]:n+=2;a=[[0]*n]+[[0]+a[i]+[0]for i in r(n-2)]+[[0]*n];x+=1;v=eval(w)
  for c,d in v:exec'a[c+%s][d+%s]+=1;'*4%(-1,0,1,0,0,-1,0,1);a[c][d]-=4
 for i in a:print''.join(map(str,i))

Edycja: zapisano 6 bajtów dzięki @ Qwerp-Derp

Podziękowania dla @ Andreï Kostyrka, ponieważ jest to bezpośrednie tłumaczenie jego kodu R na Python.

JavaScript, 418 416 406 400 393 bajtów

Tworzy anonimową funkcję, która wyświetla dane wyjściowe na konsoli.

var f =
    t=>{a=(q,w)=>Math.max(q,w);c=_=>{x=a(p[0],x);y=a(p[1],y);m[p]=(g(p)+1)%4;if(!m[p]){s.push([p[0],p[1]]);}};x=y=0,m={};g=k=>{v=m[k];return!v?0:v;};m[o=[0,0]]=1;s=[];while(--t){m[o]=(m[o]+1)%4;if(!m[o]){s.push(o);}while(s.length){p=s.pop();p[0]++;c();p[0]-=2;c();p[0]++;p[1]++;c();p[1]-=2;c();p[1]++;}}s='';for(i=-x;i<=x;i++){for(j=-y;j<=y;j++){v=g([i,j]);s+=v==0?'.':v;}s+='\n';}console.log(s);}

<input id="i" type="number"><input type="button" value="Run" onclick="var v = +document.getElementById('i').value; if (v>0) f(v)">

Nim, 294 znaki

import os,math,sequtils,strutils
var
 z=parseFloat paramStr 1
 y=z.sqrt.toInt+1
 w=y/%2
 b=y.newSeqWith newSeq[int] y
 x=0
proc d(r,c:int)=
 b[r][c]+=1;if b[r][c]>3:b[r][c]=0;d r-1,c;d r,c+1;d r+1,c;d r,c-1
for i in 1..z.toInt:d w,w
while b[w][x]<1:x+=1
for r in b[x..< ^x]:echo join r[x..< ^x]

Kompiluj i uruchamiaj:

nim c -r sandbox.nim 1000

Uwagi:

1. Udało mi się wymyślić krótszą wersję, która wykorzystuje stały rozmiar tabeli, ale zredagowałem ją na korzyść dynamicznej.
2. Po obliczeniu piaskownicy jest obliczany xjako liczba zerowych kolumn na początku środkowego rzędu.
3. Do wyświetlania tabela jest dzielona na części, wykluczając xwiersze i kolumny z każdego końca.

Występ

nim c --stackTrace:off --lineTrace:off --threads:off \ 
      --checks:off --opt:speed sandbox.nim

time ./sandbox   10000       0.053s
time ./sandbox   20000       0.172s
time ./sandbox   30000       0.392s
time ./sandbox   40000       0.670s
time ./sandbox  100000       4.421s
time ./sandbox 1000000    6m59.047s

Scala, 274 bajty

val t=args(0).toInt
val s=(Math.sqrt(t)+1).toInt
val (a,c)=(Array.ofDim[Int](s,s),s/2)
(1 to t).map{_=> ?(c,c)}
println(a.map{_.mkString}.mkString("\n"))
def?(b:Int,c:Int):Unit={
a(b)(c)+=1
if(a(b)(c)<4)return
a(b)(c)=0
?(b+1,c)
?(b-1,c)
?(b,c+1)
?(b,c-1)
}

Stosowanie:

scala sandpile.scala <iterations>

Nie sądzę, żeby było o tym wiele do wyjaśnienia. Zasadniczo dodaje tylko jedno ziarnko piasku do środka. Następnie sprawdza, czy jest większy niż 4, jeśli tak, rozleje się i sprawdzi, czy sąsiedzi powyżej 4, przeleją się itp. Jest dość szybki.

Występ:

• t = 10000 72 ms
• t = 20000 167 ms
• t = 30000 419 ms
• t = 40000 659 ms
• t = 100000 3413 ms
• t = 1000000 około 6 minut

J, 76 bajtów

p=:0,.~0,.0,~0,]
p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_

Definiuję czasownik, pktóry wypełnia granicę zer wokół wejścia. Główny czasownik przyjmuje tablicę jako dane wejściowe. Następnie sprawdza pierwszy rząd pod kątem stosu piasku zawierającego 4 lub więcej ziaren. Jeśli tak się dzieje, wyprowadza tę samą tablicę, z wyjątkiem użycia wypełnienia p, w przeciwnym razie wykonuje splot 2D w celu symulacji spadających ziaren. Główny czasownik powtarza się aż do konwergencji za pomocą operatora mocy ^:_.

Stosowanie

   p =: 0,.~0,.0,~0,]
   f =: p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_
   f 15
0 3 0
3 3 3
0 3 0
   f 50
0 0 0 1 0 0 0
0 0 3 1 3 0 0
0 3 2 2 2 3 0
1 1 2 2 2 1 1
0 3 2 2 2 3 0
0 0 3 1 3 0 0
0 0 0 1 0 0 0
   timex 'r =: f 50000'
46.3472
   load 'viewmat'
   ((256#.3&#)"0<.255*4%~i._4) viewmat r

Obliczenie wyniku dla n = 50000 zajmuje około 46 sekund , a wynik można wyświetlić za pomocą viewmatdodatku z monochromatyczną kolorystyką.

C 229 (z dużą ilością ostrzeżeń)

G[99][99],x,y,a=99,b=99,c,d;S(x,y){if(++G[y][x]>3)G[y][x]=0,S(x+1,y),S(x-1,y),S(x,y+1),S(x,y-1);a=x<a?x:a;b=y<b?y:b;c=x>c?x:c;d=y>d?y:d;}F(t){for(;t--;)S(49,49);for(y=b;y<=d;y++){for(x=a;x<=c;x++)printf("%d ",G[y][x]);puts("");}}

/* call it like this */
main(_,v)char**v;{F(atoi(v[1]));}

APL (Dyalog Unicode) , 51 bajtów ^SBCS

{m⌿r/⍨m←⌈/×r←(4∘|+{+/⊢/4 2⍴⌊⍵÷4}⌺3 3)0,∘⍉∘⌽⍣4⊢⍵}⍣≡⍪

Wypróbuj online!

PHP, 213 bajtów

function d($x,$y){global$p,$m;$m=max($m,$x);$q=&$p[$y][$x];if(++$q>3){$q=0;d($x+1,$y);d($x-1,$y);d($x,$y+1);d($x,$y-1);}}while($argv[1]--)d(0,0);for($y=-$m-1;$y++<$m;print"\n")for($x=-$m;$x<=$m;)echo+$p[$y][$x++];

rekurencyjnie tworzy stos $p, pamiętając rozmiar w $m; następnie drukuje za pomocą zagnieżdżonych pętli.
Uruchom z -r.