To pytanie dotyczy abelowych piaskowców . Przeczytaj poprzednie wyzwanie i obejrzyj wideo z numerami, aby dowiedzieć się więcej.

Abelowa kupa piasku o rozmiarze n na n jest siatką zawierającą liczbę 0, 1, 2 i 3 (reprezentującą liczbę ziaren piasku). Dodanie dwóch stosów piasków polega na dodaniu elementu po elemencie, a następnie obaleniu dowolnego elementu, który przekracza 3. Kolejność, w jakiej się przewrócisz, nie ma znaczenia, wynik końcowy jest taki sam. Kiedy komórka przewraca się, jej liczba zmniejsza się o 4, a każdy z jej bezpośrednich sąsiadów wzrasta o 1. Może to spowodować reakcję łańcuchową. Jeśli komórka znajduje się na krawędzi siatki, wszelkie ziarna spadające z siatki podczas obalania znikają.

Na przykład dodaję dwa stosy piasku 3 na 3 (co daje dość ekstremalną reakcję łańcuchową):

3 3 3   1 2 1   4 5 4    4 6 4    6 2 6    6 3 6    2 5 2    4 1 4    4 2 4    0 4 0    2 0 2    2 1 2
3 3 3 + 2 1 2 = 5 4 5 -> 6 0 6 -> 2 4 2 -> 3 0 3 -> 5 0 5 -> 1 4 1 -> 2 0 2 -> 4 0 4 -> 0 4 0 -> 1 0 1
3 3 3   1 2 1   4 5 4    4 6 4    6 2 6    6 3 6    2 5 2    4 1 4    4 2 4    0 4 0    2 0 2    2 1 2

W tym wyzwaniu interesuje nas podzbiór wszystkich możliwych stosów piasków n na n . Ten podzbiór zawiera dowolny stos piasków, który można uzyskać, dodając dowolny stos sandpile do all-3s n przez n sandpile. Na przykład tuż powyżej widzieliśmy, że 212 | 101 | 212jest w podzbiorze, ponieważ otrzymaliśmy to, dodając coś do stosu wszystkich 3.

Teraz ten podzbiór ma interesujący element: element tożsamości . Jeśli weźmiesz ten element i dodasz go do dowolnego innego elementu w podzbiorze , suma nie ulegnie zmianie. Innymi słowy, ten stos piasku działa jak zero tego podzbioru. Tak się składa, że 212 | 101 | 212jest to element zerowy dla podzbioru 3 na 3. Na przykład:

2 2 2   2 1 2   4 3 4    0 5 0    2 1 2    2 2 2
2 2 2 + 1 0 1 = 3 2 3 -> 5 2 5 -> 1 6 1 -> 2 2 2
2 2 2   2 1 2   4 3 4    0 5 0    2 1 2    2 2 2

Teraz jest to twoje wyzwanie: biorąc n , znajdź element tożsamości podzbioru siatki n na n . Wydrukuj go, przypisując każdemu z nich unikalny kolor z wystarczającym kontrastem 0, 1, 2, 3i wysyłając obraz n na n. Twój kod musi być w stanie wyprodukować skrzynkę 50 na 50 w niecałą minutę na rozsądnym nowoczesnym komputerze.

Na przykład element tożsamości 500 na 500:

Oto niebieski = 3, zielony = 2, czerwony = 1, biały = 0. Ale nie musisz używać tego schematu kolorów w swojej odpowiedzi.

Oktawa, 120 113 bajtów

function a=W(a);while nnz(b=a>3);a+=conv2(b,[t=[0 1 0];!t;t],'same')-b*4;end;end;@(n)imagesc(W((x=ones(n)*6)-W(x)))

Podziękowania dla JungHwana Min za udostępnienie linku do dokumentu referencyjnego w jego odpowiedzi Mathematica.
Dzięki Stewie Griffin zaoszczędziłem 7 bajtów[any(any(x)) -> nnz(x)]

Tutaj używane są dwie funkcje:

1 f.: dla stabilizacji macierzy
2. Anonimowa funkcja, która przyjmuje ndane wejściowe i pokazuje macierz tożsamości.

Wypróbuj na rextesterze! do generowania matrycy 50 * 50

Czas, który upłynął do obliczania macierzy: 0.0844409 seconds.

Wyjaśnienie:

Zastanów się nad funkcją f stabilizującą matrycę, a poszukiwanie tożsamości jest proste

f(ones(n)*6 - f(ones(n)*6).

że ones(n)*6 oznacza macierz n * 6.

więc dla n=3:

M = [6 6 6
     6 6 6
     6 6 6];

Wynik będzie f(M-f(M))

Dla funkcji stabilizacji splot 2D używany do przyspieszenia zadania; W każdej iteracji tworzymy macierz binarną bo tym samym rozmiarze matrycy wejściowej i ustawiamy ją na 1, jeśli odpowiadający jej element ma> 3. Następnie stosujemy 2D splot macierzy binarnej za pomocą następującej maski

0 1 0
1 0 1
0 1 0

reprezentujących czterech bezpośrednich sąsiadów.
Wynik splotu jest dodawany do matrycy i odejmowany czterokrotnie matryca binarna.

Pętla była kontynuowana, aż wszystkie elementy macierzy osiągnęły <= 3

Wersja bez golfa :

function a=stabilize(a)
    mask = [t=[0 1 0];!t;t];
    while any(any(b=a>3))
        a+=conv2(b,mask,'same')-b*4;
    end
end
n= 50;
M = ones(n)*6;
result = stabilize(M-stabilize(M));
imagesc(result);

Mathematica, 177 157 135 133 bajtów

Colorize[f=BlockMap[⌊{l={0,1,0},1-l,l}#/4⌋~Total~2+#[[2,2]]~Mod~4&,#~ArrayPad~1,{3,3},1]&~FixedPoint~#&;k=Table[6,#,#];f[k-f@k]]&

Podejmuje liczbę n. Dane wyjściowe to sandpile tożsamości. 0 to czarny, 1 to jasnoszary, 2 to purpurowy, a 3 to niebiesko-szary.

Niestety Mathematica nie ma wbudowanego do tego ...

Wykorzystuje algorytm określony w pracy Scotta Corry'ego i Davida Perkinsona .

Moje 9-letniemu laptopowi zajmuje 91,7 sekundy, aby obliczyć sandpile tożsamości 50x50. Jestem przekonany, że rozsądny nowoczesny komputer stacjonarny jest o ponad 50% szybszy. (Na końcu mam też znacznie szybszy kod).

Wyjaśnienie

f= ...

Zdefiniuj funkcję f(dane wejściowe to macierz piasku): funkcja, która ...

BlockMap[ ... ]~FixedPoint~#&

... powtarza BlockMapoperację, dopóki dane wyjściowe się nie zmienią. BlockMapoperacja: ...

#~ArrayPad~1

... wypełnij tablicę wejściową jedną warstwą 0 ...

{3,3},1

... podziel go na matryce 3x3, z przesunięciem 1 ...

⌊{l={0,1,0},1-l,l}#/4⌋~Total~2+#[[2,2]]~Mod~4&

... i dla każdej partycji dodaj liczbę ziaren piasku zrzuconych na środkową komórkę i wartość środkowej komórki mod 4.

tzn. wyjście fjest ustabilizowaną wersją wejścia.

k=Table[6,#,#]

Zdefiniuj kjako tablica n na n 6s.

f[k-f@k]]

Oblicz f (k - f (k)).

Colorize[ ... ]

Zastosuj kolory do wyniku.

Szybsza wersja (142 bajty)

Colorize[r=RotateLeft;a=ArrayPad;f=a[b=#~a~1;b+r[g=⌊b/4⌋,s={0,1}]+g~r~-s+r[g,1-s]+r[g,s-1]-4g,-1]&~FixedPoint~#&;k=Table[6,#,#];f[k-f@k]]&

Ten sam kod, ale zamiast tego używa wbudowanej rotacji listy BlockMap. Oblicza n = 50 w 4,0 sekundy na moim laptopie.

Python 3 + Numpy + PIL, 385 370 364 bajtów

import numpy as q,PIL.Image as w
n=int(input())
z=n,n
def r(p):
 while len(p[p>3]):
  for x,y in q.ndindex(z):
   if p[x,y]>3:
    p[x,y]-=4;p[x-1,y]+=x>0;p[x,y-1]+=y>0
    if~-n>x:p[x+1,y]+=1
    if~-n>y:p[x,y+1]+=1
s=q.full(z,6)
t=s.copy()
r(t)
i=s-t
r(i)
w.fromarray(q.uint8(q.array(q.vectorize(lambda x:[x//1*65]*3,otypes=[object])(i).tolist()))).save('i.png')

Pobiera dane wejściowe na STDIN. Wysyła obraz w skali szarości do i.png. Czarny odpowiada 0, ciemnoszary do 1, jasnoszary do 2, a biały do ​​0.

Wykorzystuje formułę I = R(S - R(S)), gdzie Ijest elementem tożsamości, Smacierzą wypełnioną szóstkami i Rjest funkcją redukcji.

Prawdopodobnie mógłbym zaoszczędzić trochę bajtów, przechodząc do Python 2 i wykonując to from numpy import* , ale (1) nie mam Numpy zainstalowanego na Pythonie 2 i (2) program się nie kończył from numpy import*.

Nie golfowany:

import numpy as np
from PIL import Image

# Compute the identity element

n = int(input('Size of the sandpile: '))

def reduce_pile(sandpile):
  while any(element >= 4 for element in np.nditer(sandpile)):
    for x, y in np.ndindex((n, n)):
      if sandpile[x, y] >= 4:
        sandpile[x, y] -= 4
        if x > 0: sandpile[x - 1, y] += 1
        if y > 0: sandpile[x, y - 1] += 1
        if x < n - 1: sandpile[x + 1, y] += 1
        if y < n - 1: sandpile[x, y + 1] += 1

s = np.full((n, n), 6, dtype=np.int32)
s_prime = np.copy(s)

reduce_pile(s_prime)

identity = s - s_prime
reduce_pile(identity)

# Output it to identity.png as an image

colours = [[255, 255, 255], [255, 0, 0], [0, 255, 0], [0, 0, 255]]
img_array = np.vectorize(lambda x: colours[x], otypes=[object])(identity)
img_array = np.array(img_array.tolist(), dtype=np.uint8)

img = Image.fromarray(img_array)
img.save('identity.png')