Ein abelscher Sandhaufen ist für unsere Zwecke ein unendliches Gitter mit ganzzahligen Koordinaten, anfangs ohne Sand. Nach jeder Sekunde wird ein Sandkorn bei (0,0) platziert. Wenn eine Gitterzelle 4 oder mehr Sandkörner enthält, wird gleichzeitig ein Sandkorn auf jeden der vier Nachbarn verschüttet. Die Nachbarn von (x, y) sind (x-1, y), (x + 1, y), (x, y-1) und (x, y + 1).
Wenn eine Zelle verschüttet wird, kann dies dazu führen, dass ihre Nachbarn verschüttet werden. Einige Fakten:
- Diese Kaskade wird irgendwann aufhören.
- Die Reihenfolge, in der die Zellen verschüttet werden, spielt keine Rolle. Das Ergebnis wird dasselbe sein.
Beispiel
Nach 3 Sekunden sieht das Raster so aus
.....
.....
..3..
.....
.....
Nach 4 Sekunden:
.....
..1..
.1.1.
..1..
.....
Nach 15 Sekunden:
.....
..3..
.333.
..3..
.....
Und nach 16 Sekunden:
..1..
.212.
11.11
.212.
..1..
Die Herausforderung
Schreiben Sie in möglichst wenigen Bytes eine Funktion, die eine einzelne positive ganze Zahl t annimmt und nach t Sekunden ein Bild des Sandstapels ausgibt .
Eingang
Eine einzelne positive ganze Zahl t in einem beliebigen Format.
Ausgabe
Ein Bild des Sandhaufens nach t Sekunden unter Verwendung der Zeichen
. 1 2 3
Bearbeiten: Verwenden Sie vier beliebige Zeichen oder zeichnen Sie ein Bild. Wenn Sie nicht ".123" oder "0123" verwenden, geben Sie in Ihrer Antwort an, was die Zeichen bedeuten.
Anders als in den Beispielen sollte Ihre Ausgabe die minimale Anzahl von Zeilen und Spalten enthalten, die erforderlich sind, um den Teil des Sandstapels ungleich Null anzuzeigen.
Das heißt, für Eingang 3 sollte der Ausgang sein
3
Für 4 sollte die Ausgabe sein
.1.
1.1
.1.
Wertung
Es gilt die Standardgolfwertung.
Regeln
Es sind keine Sprachfunktionen oder Bibliotheken erlaubt, die bereits wissen, was ein Sandhaufen ist.
Bearbeiten: Der Ausgabebereich wurde bearbeitet, die Zeichensatzbeschränkung wurde vollständig aufgehoben. Verwenden Sie vier verschiedene Zeichen oder Farben, die Sie mögen.
quelle
0
? Was ist dann die Ausgabe?.
für leere Zellen zu haben ? Können wir0
eine gültige leere Zelle haben?Antworten:
R,
378343297291 BytesWie gewöhnlich gibt der Benutzer seine / ihre Eingabe über ein
scan()
(ich habe die Variable bereits verwendett
, nehmen wirz
stattdessen), sodass die zweite Zeile separat gestartet werden sollte, und dann den Rest:Gibt einen Array, das den Wert enthält ,
a
beit
th Generation (0, 1, 2 oder 3).Testfälle:
Es hilft uns, dass dieses Ding sowohl vertikal als auch horizontal symmetrisch ist, was bedeutet, dass der am weitesten links liegende Punkt eine Höhe von 4 erhält, was bedeutet, dass der am weitesten oben liegende, der am weitesten rechts liegende und der am weitesten unten liegende Punkt ebenfalls 4 sind.
Oh, und habe ich gesagt, dass Sie schöne Visualisierungen machen können?
Nach 1000 Tropfen:
Nach 50000 Tropfen (~ 4 Sekunden):
Nach 333333 Tropfen (~ 15 Minuten):
Sie können es auch zeichnen!
Dies dauerte 4 Sekunden für 10000 Iterationen, verlangsamt sich jedoch erheblich für größere Arrays (z. B. einige Minuten für 100000 Iterationen). Dies ist der Grund, warum es so langsam wird (ich schätze die Wachstumsrate wie in und erhalte τ (i) ≈689 · i ^ 1,08, daher ist die durchschnittliche Zeit pro zusätzlichem Korn, bis sich der gesamte Sandhaufen nach dem
i
Schritt absetzt, etwas größer als eins). , und die Gesamtzeit in Abhängigkeit von der Anzahl der Körner wächst etwas langsamer als quadratisch (T (i) ≈ 0.028 * i ^ 1.74):Und jetzt mit einer vollständigen Erklärung:
Dies ist das erste Mal in meinem Leben, dass das Wachsen von Objekten (wie
a <- c(a, 1)
) so viel schneller geht, als eine große leere Matrix für Werte vorab zuzuweisen und sie allmählich mit einer Tonne nicht verwendeter Nullen zu füllen.Aktualisieren. 18 Bytes golfed durch Entfernen
arr.ind
inwhich
durch Billywob und Ersetzenrep(0,n)
mite=numeric;e(n)
in 5 - Instanzen aufgrund JDL , und 17 weiteren Bytes aufgrund JDL .Update 2. Da es sich bei dem Sandhaufen um einen Abelschen Sandhaufen handelt, kann er mit einem Stapel gewünschter Höhe beginnen. Daher habe ich die redundante Schleife entfernt und die Produktivität erheblich gesteigert!
quelle
rep()
, vorausgesetzt, Sie verwenden es 6 Mal. Zweitens glaube ich nicht, dass Sie diearr.ind=T
Option für diewhich()
Funktion ausschreiben müssen. Einfach benutzenwhich(...,T)
.n=numeric
und zu verwenden, dan(k)
es weniger Zeichen als gibtr(0,k)
. Die Bilder gefallen mir allerdings.1%*%0
ist weniger Zeichen alsarray(0,c(1,1))
. Auch das zweite Argument,u <- cbind
das nur 1 sein darf,cbind
wird standardmäßig auf die Länge des ersten Arguments ausgedehnt.MATL ,
5553484342 BytesInspiriert von @flawrs Antwort .
Grafische Ausgabe :
Probieren Sie es bei MATL Online! . Die Eingabe dauert ca. 10 Sekunden
30
. Möglicherweise müssen Sie die Seite aktualisieren und erneut auf "Ausführen" klicken, wenn dies nicht funktioniert.Hier ist ein Beispielergebnis für die Eingabe
100
:ASCII-Ausgabe (43 Byte) :
Probieren Sie es online!
Erläuterung
quelle
1Y6
.~mod(spiral(3),2)
ist viel schlauer :-)Matlab,
160 156148 BytesZuerst wird eine viel zu große Matrix erstellt, mit der
n
irgendwo in der Mitte. Dann wird die Kaskadierung mit einer sehr praktischen 2D-Faltung berechnet. Am Ende wird der Überschuss abgeschnitten und das Ganze in einen String umgewandelt.Beispielausgabe für
t=100
Wie immer:
quelle
v=any(z)
stattv=find(sum(z))
(ich benutze das in meiner Antwort). Auch2*~z
anstelle von(z<1)*2
n=500
... Es wurde seitn=400
einigen Sekunden verarbeitet. Mache ich etwas falsch?n
generiert dieses Programm eine3*n x 3*n
Matrix, so dass es etwa9*n^2
Zahlen speichern muss . Außerdem ist es völlig ineffizient, weil wir auch eine völlig unnötige lange Iteration von 1 bis n haben. Aber andererseits ist das Code-Golf , ein Programm effizient zu machen, ist eine andere Sache.z=sparse(zeros(2*n+1))
und die for-Schleife auf ändernwhile any(z(:)>3)
. Dann können Sie vielleicht auch die Faltungskern berechnen nur einmal:kern = 1-mod(spiral(3),2)
.Python 2,
195 +1 +24 = 220217Ausgabe für n = 16
Es gibt eine Menge unnötiger Auffüllungen und Iterationen, wenn man
n
als "ausreichend" -Obergrenze verwendet, aber n = 200 ist immer noch in einer Sekunde abgeschlossen und n = 500 in ungefähr 12 Sekundenungolfed
Ersetzen
return x
durchimshow(x)
Fügt ein Zeichen hinzu und gibt ein hässliches interpoliertes Bild aus. Durch Hinzufügenimshow(x,'gray',None,1,'nearest')
wird die unscharfe Interpolation entfernt, wodurch die Ausgabe den Spezifikationen entsprichtquelle
ImportError: No module named convolve2d
. Ändern,import scipy.signal.convolve2d as c
umfrom scipy.signal import convolve2d as c
das Problem zu beheben. Ich verwende scipy Version 0.16.1. Benötige ich eine ältere oder neuere Version? Oder ist das Problem etwas anderes?Perl,
157147 BytesBeinhaltet +1 für
-p
Mit der Zählung auf STDIN ausführen, die Karte mit
0123
auf STDOUT drucken:sandpile.pl
:quelle
Python
32,418385362342330 BytesEdit: 6 Bytes gespart dank @ Qwerp-Derp
Wir danken @ Andreï Kostyrka für die direkte Übersetzung seines R-Codes in Python.
quelle
a,x,r
in die Funktionsargumente verschieben.JavaScript,
418416406400393 BytesErstellt eine anonyme Funktion, die die Ausgabe auf der Konsole anzeigt.
quelle
Nim, 294 Zeichen
Kompilieren und ausführen:
Anmerkungen:
x
wird als Anzahl der Nullspalten am Anfang der mittleren Zeile gerechnet.x
Zeilen und Spalten von jedem Ende getrennt.Performance
quelle
Scala, 274 Bytes
Verwendungszweck:
scala sandpile.scala <iterations>
Ich denke, es gibt nicht viel zu erklären. Im Grunde fügt es nur ein Sandkorn in die Mitte. Dann wird geprüft, ob es größer als 4 ist. Wenn dies der Fall ist, wird überprüft, ob alle Nachbarn, die größer als 4 sind, übergelaufen sind, usw. Es geht recht schnell.
Performance:
quelle
J, 76 Bytes
Ich definiere ein Verb,
p
das einen Rand von Nullen um die Eingabe auffüllt. Das Hauptverb nimmt ein Array als Eingabe. Anschließend wird in der ersten Zeile nach Sandhaufen gesucht, die 4 oder mehr Körner enthalten. Wenn dies der Fall ist, wird dasselbe Array mit Ausnahme von padded using ausgegeben.p
Andernfalls wird eine 2d-Faltung durchgeführt, um fallende Körner zu simulieren. Das Hauptverb wird mit dem Operator power bis zur Konvergenz wiederholt^:_
.Verwendungszweck
Es dauert ungefähr 46 Sekunden, um das Ergebnis für n = 50000 zu berechnen , und das Ergebnis kann unter Verwendung des
viewmat
Addons mit einem monochromen Farbschema angezeigt werden .quelle
C 229 (mit vielen Warnungen)
quelle
APL (Dyalog Unicode) , 51 Byte SBCS
Probieren Sie es online!
quelle
PHP, 213 Bytes
erstellt rekursiv den Stapel in
$p
, wobei die Größe in gespeichert wird$m
; Dann wird mit verschachtelten Schleifen gedruckt.Laufen Sie mit
-r
.quelle