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ódło
0
? Jaki jest zatem wynik?.
puste komórki? Czy możemy mieć0
jako prawidłową pustą komórkę?Odpowiedzi:
R,
378343297291 bajtówJak zwykle użytkownik dostarcza swoje dane wejściowe za pośrednictwem
scan()
(już użyłem zmiennejt
, więc weźmyz
zamiast tego), więc drugą linię należy uruchomić osobno, a następnie resztę:Wyjścia tablicę zawierającą wartości
a
wt
tej generacji (0, 1, 2 lub 3).Przypadki testowe:
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ć!
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
i
tym 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:
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.ind
zwhich
powodu Billywob i zastępującrep(0,n)
ze=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!
źródło
rep()
, biorąc pod uwagę, że używasz go 6 razy. Po drugie, nie sądzę, że musisz wypisaćarr.ind=T
opcję dla tejwhich()
funkcji. Po prostu użyjwhich(...,T)
.n=numeric
Zamiast tego może być bardziej golfowym zdefiniowanie i użycie tego, ponieważn(k)
jest mniej znaków niżr(0,k)
. Jednak lubię te zdjęcia.1%*%0
jest mniej znaków niżarray(0,c(1,1))
. Również drugi argument, któryu <- cbind
może być równy 1,cbind
domyślnie przedłuży go do długości pierwszego argumentu.MATL ,
5553484342 bajtyZainspirowany odpowiedzią @ flawr .
Wyjście graficzne :
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) :
Wypróbuj online!
Wyjaśnienie
źródło
1Y6
.~mod(spiral(3),2)
jest o wiele mądrzejszy :-)Matlab,
160 156148 bajtówNajpierw tworzona jest zbyt duża matryca,
n
gdzieś 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
Jak zawsze:
źródło
v=any(z)
zamiastv=find(sum(z))
(używam tego w mojej odpowiedzi). Ponadto2*~z
zamiast(z<1)*2
n=500
... Przetwarzałn=400
przez kilka sekund. czy robię coś źle?n
tego programu generuje3*n x 3*n
macierz, więc musi przechowywać o9*n^2
liczbach. Jest to również całkowicie nieefektywne, ponieważ mamy również całkowicie niepotrzebną długą iterację od 1 do n. Ale z drugiej strony jest to gra w golfa kodowego , sprawienie, że program jest wydajny, to inna filiżanka herbaty.z=sparse(zeros(2*n+1))
i zmieniając pętlę for nawhile any(z(:)>3)
. Następnie można również może obliczyć jądro splotu tylko raz:kern = 1-mod(spiral(3),2)
.Python 2,
195 +1 +24 = 220217wyjście dla n = 16
jest DUŻO niepotrzebnego wypełniania i iteracji, używając
n
jako „wystarczającej” górnej granicy, ale n = 200 nadal ukończone w ciągu sekundy, a n = 500 w około 12 sekundbez golfa
zastąpienie
return x
przezimshow(x)
dodaje jeden znak i generuje brzydki interpolowany obraz, dodanieimshow(x,'gray',None,1,'nearest')
usuwa rozmytą interpolację, dostosowując dane wyjściowe do specyfikacjiźródło
ImportError: No module named convolve2d
. Zmiana wimport scipy.signal.convolve2d as c
celufrom scipy.signal import convolve2d as c
rozwiązania problemu. Używam scipy wersji 0.16.1, czy potrzebuję starszej czy nowszej wersji? A może problem jest czymś innym?Perl,
157147 bajtówObejmuje +1 dla
-p
Uruchom z liczeniem na STDIN, drukuje mapę używając
0123
do STDOUT:sandpile.pl
:źródło
Python
32,418385362342330 bajtówEdycja: 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.
źródło
a,x,r
do argumentów funkcji.JavaScript,
418416406400393 bajtówTworzy anonimową funkcję, która wyświetla dane wyjściowe na konsoli.
źródło
Nim, 294 znaki
Kompiluj i uruchamiaj:
Uwagi:
x
jako liczba zerowych kolumn na początku środkowego rzędu.x
wiersze i kolumny z każdego końca.Występ
źródło
Scala, 274 bajty
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:
źródło
J, 76 bajtów
Definiuję czasownik,
p
któ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łnieniap
, 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
Obliczenie wyniku dla n = 50000 zajmuje około 46 sekund , a wynik można wyświetlić za pomocą
viewmat
dodatku z monochromatyczną kolorystyką.źródło
C 229 (z dużą ilością ostrzeżeń)
źródło
APL (Dyalog Unicode) , 51 bajtów SBCS
Wypróbuj online!
źródło
PHP, 213 bajtów
rekurencyjnie tworzy stos
$p
, pamiętając rozmiar w$m
; następnie drukuje za pomocą zagnieżdżonych pętli.Uruchom z
-r
.źródło