Das Treppenhaus des Teufels ist eine fraktale Funktion, die mit dem Cantor-Set verwandt ist.
Ihre Aufgabe ist es, diese funky Funktion zu replizieren - in ASCII-Kunst!
Eingang
Eine einzelne Ganzzahl n >= 0
, die die Größe der Ausgabe angibt. Die Eingabe kann über STDIN, Funktionsargument oder Befehlszeilenargument erfolgen.
Ausgabe
Die ASCII- n
artige Wiedergabe der Treppe des Teufels in Originalgröße, die entweder als Zeichenfolge zurückgegeben oder auf STDOUT gedruckt wurde. Nachgestellte Leerzeichen am Ende jeder Zeile sind in Ordnung, führende Leerzeichen jedoch nicht. Sie können optional eine einzelne nachgestellte Zeile drucken.
Für die Größe 0
ist die Ausgabe nur:
x
(Wenn Sie möchten, können Sie anstelle von x
. Ein anderes druckbares ASCII-Zeichen als Leerzeichen verwenden .)
Für die Größe n > 0
, wir:
- Nehmen Sie die Ausgabe von size
n-1
und dehnen Sie jede Zeile um den Faktor drei - Riffel zwischen Reihen einzelner
x
s - Verschieben Sie die Zeilen nach rechts, sodass sich
x
in jeder Spalte genau eine befindet und die Position der erstenx
minimal ist, während sie mit den Zeilen abnimmt
Die Ausgabe für n = 1
lautet beispielsweise:
x
xxx
x
Um die Ausgabe für zu erhalten n = 2
, dehnen wir jede Zeile um den Faktor drei:
xxx
xxxxxxxxx
xxx
Riffel zwischen Reihen von x
Singles:
x
xxx
x
xxxxxxxxx
x
xxx
x
Nach rechts verschieben:
x
xxx
x
xxxxxxxxx
x
xxx
x
Als ein weiteres Beispiel hier ist n = 3
.
Wertung
Das ist Code-Golf, also gewinnt die Lösung mit den wenigsten Bytes.
(,],~3^#@~.)@]
statt(1,[:,1,"0~3*])
spart 1 Byte. Und wenn Sie mit!
als Ausgabezeichen in Ordnung sind,u:32+
anstatt ein' #'{~
anderes zu speichern.#\
statti.@#
und du überholst APL! :)n-1
nicht fürn
.Hexagony , 217 Bytes
Das hat unglaublich viel Spaß gemacht. Vielen Dank, dass Sie diese Challenge gepostet haben.
Vollständige Offenlegung: Die Sprache (Hexagony) war zum Zeitpunkt der Veröffentlichung dieser Challenge noch nicht vorhanden. Ich habe es jedoch nicht erfunden und die Sprache wurde nicht für diese Herausforderung (oder irgendeine andere spezielle Herausforderung) entwickelt.
Sechseckig angeordnet:
Das Programm verwendet die
#
Anweisung nicht wirklich , also habe ich dieses Zeichen verwendet, um zu zeigen, welche Zellen wirklich nicht verwendet werden.Wie funktioniert dieses Programm? Das hängt davon ab. Willst du die kurze oder die lange Version?
Kurze Erklärung
Um zu veranschaulichen, was ich in der folgenden Erläuterung mit "Linie" und "Segment" meine, betrachten Sie diese Aufteilung der beabsichtigten Ausgabe:
Damit entspricht das Programm dem folgenden Pseudocode:
Lange Erklärung
Bitte beziehen Sie sich auf dieses farbcodierte Codepfaddiagramm.
Die Ausführung beginnt in der oberen linken Ecke. Die
){2'"''3''"2}?)
Befehlsfolge wird ausgeführt (plus einige redundante Löschvorgänge"{
usw.), indem ein ziemlich verschlungener Pfad verfolgt wird. Wir beginnen mit dem Anweisungszeiger # 0, der hochrot hervorgehoben ist. Auf halbem Weg wechseln wir zu Nummer 1, beginnend in der oberen rechten Ecke und in Waldgrün. Wenn IP Nr. 2 in Kornblumenblau (Mitte rechts) beginnt, sieht das Speicherlayout folgendermaßen aus:Während des gesamten Programms haben die mit 2a und 2b bezeichneten Kanten immer den Wert
2
(wir verwenden sie, um 2ⁿ⁺¹ zu berechnen und durch 2 zu teilen), und die mit 3 bezeichnete Kante ist immer3
(wir verwenden sie, um 3ⁱ zu berechnen).Wir machen uns an die Arbeit, als wir unsere erste Schleife betreten, die in Kornblumenblau hervorgehoben ist. Diese Schleife führt die Anweisungen
(}*{=&}{=
zur Berechnung des Wertes 2ⁿ⁺¹ aus. Wenn die Schleife endet, wird der sattelbraune Pfad genommen, der uns zum Anweisungszeiger Nr. 3 führt. Diese IP plantscht lediglich in Goldrutengelb am unteren Rand nach Westen und übergibt die Kontrolle bald an IP # 4.Der pinkfarbene Pfad gibt an, wie IP # 4, beginnend links unten, schnell zur Dekrementierung der Zeile voranschreitet , ch auf
32
(das Leerzeichen) und seg auf (den neuen Wert von) Zeile setzt . Aufgrund des frühen Dekrements beginnen wir tatsächlich mit 2ⁿ⁺¹ − 1 und erleben schließlich eine letzte Iteration mit dem Wert 0. Dann geben wir die erste verschachtelte Schleife ein.Wir wenden unsere Aufmerksamkeit auf die Verzweigung Indigo, wo nach einer kurzen Abnahme der seg , sehen wir ch aktualisiert
x
nur , wenn seg ist jetzt Null. Danach wird n auf line - seg gesetzt , um die tatsächliche Nummer des Segments zu bestimmen, in dem wir uns befinden. Sofort treten wir in eine weitere Schleife ein, diesmal in der hellen Farbe von Tomate.Hier stellen wir fest, wie oft n (die aktuelle Segmentnummer) durch 2 dividiert werden kann. Solange das Modulo Null ergibt, inkrementieren wir i und dividieren n durch 2. Wenn wir zufrieden sind, ist n nicht mehr so teilbar , verzweigen wir uns in das Schiefergrau, das zwei Schleifen enthält: Zuerst erhöht es 3 zur Potenz des von uns berechneten i , und dann gibt es ch so oft aus. Beachten Sie, dass die erste dieser Schleifen a enthält
[
Befehl, der die Steuerung auf IP # 3 umschaltet - diejenige, die zuvor nur kleine Schritte entlang der unteren Kante unternommen hat. Der Körper der Schleife (multipliziert mit 3 und dekrementiert) wird von einer einsamen IP # 3 ausgeführt, die in einem endlosen dunkelolivgrünen Zyklus am unteren Rand des Codes eingeschlossen ist. In ähnlicher Weise enthält die zweite dieser schiefergrauen Schleifen eine]
Anweisung, die IP # 5 aktiviert, um Kanal und Dekrement auszugeben , die hier in dunklem Indischrot dargestellt sind. In beiden Fällen führen die in der Knechtschaft gefangenen Anweisungszeiger gehorsam eine Iteration nach der anderen aus und geben die Kontrolle an IP # 4 zurück, nur um den Zeitpunkt abzuwarten, an dem ihr Dienst erneut aufgerufen werden soll. Das Schiefergrau verbindet sich unterdessen wieder mit seinen Fuchsia- und Indigo-Brüdern.Wenn seg zwangsläufig Null erreicht, tritt die Indigoschleife in den grünen Rasenpfad ein, der lediglich das Zeilenumbruchzeichen ausgibt und sofort wieder in die Fuchsie übergeht, um die Linienschleife fortzusetzen . Jenseits der letzten Iteration der Leitungsschleife liegt der kurze schwarze Pfad der endgültigen Programmbeendigung.
quelle
Python 2, 78
Beginnen
L=[1]
wir mit der Liste , duplizieren wir sie und fügen die nächste Potenz von 3 in die Mitte ein[1, 3, 1]
. Dies wird mehrmals wiederholtn
, um die Zeilenlängen für die Treppe des Teufels zu ermitteln. Dann drucken wir jede Zeile mit Leerzeichen.quelle
APL, 38
Beispiel:
Erläuterung:
quelle
GNU sed, 142
Nicht die kürzeste Antwort, aber es ist sed !:
Da dies sed ist (keine native Arithmetik), nehme ich mir Freiheiten mit der Regel "Eine einzelne Ganzzahl n> = 0, die die Größe der Ausgabe angibt" . In diesem Fall muss die Eingabe-Ganzzahl eine Zeichenfolge von
1
s sein, deren Länge n ist. Ich denke, dies "zeigt" die Größe der Ausgabe an, obwohl es kein direktes numerisches Äquivalent zu n ist. Für n = 2 lautet die Eingabezeichenfolge also11
:Dies scheint mit der exponentiellen zeitlichen Komplexität von O (c n ) zu vervollständigen , wobei c ungefähr 17 ist. N = 8 hat für mich ungefähr 45 Minuten gedauert.
Alternativ können wir dies tun, wenn es erforderlich ist, dass n genau numerisch eingegeben wird:
sed, 274 bytes
Ausgabe:
quelle
Python 2, 81
Programmversion (88)
Die Anzahl der x in der
n
1-indizierten Zeile ist 3 hoch (der Index des ersten gesetzten Bits inn
, beginnend mit lsb).quelle
Python 2, 74
Ein rekursiver Ansatz. Die Treppe des großen Teufels ist in drei Teile geteilt
n-1
, deren Länge ist3**n - 2**n
x
', der Länge3**n
n-1
, deren Länge ist3**n - 2**n
Beachten Sie, dass die Gesamtlänge der drei Teile
3*(3**n) - 2*(2**n)
oder ist3**(n+1) - 2**(n+1)
, was die Induktion bestätigt.Die optionale Variable
s
speichert den Versatz der aktuellen Teile, die wir drucken. Wir gehen zuerst mit größerem Versatz zum linken Zweig zurück, drucken dann die Mittellinie und machen dann den rechten Zweig mit dem aktuellen Versatz.quelle
CJam,
363533 BytesHier ist ein weiterer CJam-Ansatz (ich habe mir den Code des Optimierers nicht angesehen, daher weiß ich nicht, ob er sich tatsächlich stark unterscheidet):
Dies wird
0
für die Kurve verwendet. Alternativ (mit grcs Trick)welche verwendet
x
.Teste es hier.
Erläuterung
Die Grundidee ist, zuerst ein Array mit den Zeilen zu bilden, wie
Um diese Liste durchzugehen, müssen Sie die richtige Anzahl von Leerzeichen voranstellen.
Die andere Version funktioniert ähnlich, erzeugt jedoch eine Reihe von Längen, wie z
Und verwandelt das dann in Zeichenfolgen von
x
s in der endgültigen Map.quelle
Dyalog APL, 34 Zeichen
Verwendung des Ansatzes von grc. Zeichnet die Treppe mit
⌹
(Domino-) Zeichen und nimmt Eingaben von stdin entgegen. Diese Lösung geht davon aus⎕IO←0
.⎕
- Eingaben von stdin nehmen.⌽⍳1+⎕
- die Reihenfolge der Zahlen von⎕
unten bis 0. (zB3 2 1 0
)3*⌽⍳1+⎕
- drei hoch genug (zB27 9 3 1
)(⊢,,)/3*⌽⍳1+⎕
- Das vorherige Ergebnis wird von rechts durch die stillschweigende Funktion gefaltet,⊢,,
die gleich dem dfn ist und die Stufenlängen der Teufeltreppe{⍵,⍺,⍵}
gemäß der Annäherung von grc ergibt.{⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕
Die Schrittlängen werden in Schritte umgerechnet.(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕
das selbst eingestuft, wie in meiner J-Lösung . Beachten Sie, dass⊖
das Ergebnis bereits richtig gekippt wird.' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕]
Die Zahlen werden durch Leerzeichen und Dominosteine ersetzt.quelle
Rubin, 99
Eine andere Antwort als meine andere, inspiriert von der Antwort von FUZxxl
FUZxxl stellt fest, dass die Zahlen von x der Anzahl der Faktoren von 2 des Index entsprechen. Zum Beispiel haben wir für n = 2 die folgende Faktorisierung:
Ich benutze eine einfachere Methode, um diese Potenzen von 2 zu extrahieren: Dies
i=m&-m
ergibt die Folge1 2 1 4 1 2 1
usw. Dies funktioniert wie folgt:m-1
ist dasselbe wiem
in seinen höchstwertigen Bits, aber das niedrigstwertige 1-Bit wird zu einer Null, und alle Nullen rechts werden zu Einsen.Um dies mit dem Original UND zu können, müssen wir die Bits umdrehen. Hierfür gibt es verschiedene Möglichkeiten. Eine Möglichkeit besteht darin, es von zu subtrahieren
-1
.Die Gesamtformel ist dann
m& (-1 -(m-1))
die zu vereinfachendem&(-m)
Beispiel:
Hier ist der Code: Zeilenumbrüche werden gezählt, Einrückungen sind unnötig und werden daher nicht gezählt, wie meine andere Antwort. Es ist etwas länger als meine andere Antwort, da die Konvertierung von Basis 2
1 2 1 4 1 2 1 etc
zu Basis 3 umständlich1 3 1 9 1 3 1 etc
ist : (Gibt es eine Möglichkeit, dies zu vermeidenMath::
?)quelle
Rubin,
14099Mein zweiter Ruby-Code und mein erster nicht-trivialer Gebrauch der Sprache. Vorschläge sind herzlich willkommen. Die Byteanzahl schließt führende Leerzeichen für Einrückungen aus, schließt jedoch Zeilenumbrüche ein (die meisten Zeilenumbrüche können anscheinend nur gelöscht werden, wenn sie durch mindestens ein Leerzeichen ersetzt werden.)
Die Eingabe erfolgt per Funktionsaufruf. Die Ausgabe ist ein Array von Zeichenfolgen, die Ruby bequem als durch Zeilenumbrüche getrennte Liste mit einer einzigen Ausgabe an stdout ausgibt
puts
.Der Algorithmus ist einfach
new iteration
=previous iteration
+extra row of n**3 x's
+previous iteration
. Es gibt jedocheineMenge Code, nur um die führenden Leerzeichen in der Ausgabe richtig zu machen.Bearbeiten: Ruby, 97
Dies verwendet den ähnlichen, aber unterschiedlichen Ansatz, eine numerische Tabelle mit allen im Array erforderlichen x-Zahlen
a
auf die oben beschriebene Weise zu erstellen, anschließend jedoch eine Tabelle mit Zeichenfolgen zu erstellen. Die Tabelle der Zeichenfolgen wird in Arrayc
mit der seltsam benanntenunshift
Methode rückwärts erstellt , um dem vorhandenen Array voran zu stellen.Derzeit sieht dieser Ansatz besser aus - aber nur um 2 Bytes :-)
quelle
for m in(0..n-1)do ... end
mitn.times{|m|...}
.n.times
und das werde ich mir sicher merken. Es beseitigt auch eineend
! Allerdings habe ich mich bei dieser Gelegenheit gefragt, obfor m in (1..n)
es besser sein könnte, das zu vermeiden(m+1)
. Gibt es eine kürzere Schreibweise dafür?for
ist vor allem deshalb lang, weil Sie gezwungen sind zu verwendenend
(Sie können diedo
durch eine neue Zeile oder durch ersetzen;
). Denn1..n
du kannst verwenden1.upto(n){|m|...}
. Ich mag das Aussehen,(1..n).each{|i|...}
aber es ist etwas länger als mitupto
. Beachten Sie außerdem, dass das Iterieren durch Aufrufeneach
oderupto
nicht nur kürzer ist, sondern auch idiomatischeres Ruby berücksichtigt.1.upto(n)
es ist! Wenn das und ein paar unnötige Klammern weg sind, bin ich schon auf 120 gesunken. Ich denke, unter 100 ist möglich, ich werde den überarbeiteten Code später posten.Haskell, 99 Zeichen
Die Funktion ist
d
:quelle
q
und dabeiq x=x
in dem leeren Liste Fall. Außerdem scheinen die Klammerniterate...[1]
unnötig zu sein.PHP - 137 Bytes
Ich benutze hier den gleichen Trick wie grc . Hier ist die ungolfed Version:
quelle
3**$i
-> fühlt sich an wie PHP 5.6. Sie sollten es angeben. Dies ist mit fast jeder Installation von PHP nicht kompatibel. Um Ihnen ein paar Bytes zu ersparen, sollten Sie mit beginnen$r=str_repeat;
und dort, wo Sie diese Funktion haben, mit ersetzen$r
, wodurch Sie 2 Bytes sparen. Auch$r('x',$v)
kann sein$r(x,$v)
und es wird funktionieren ( man beachte , dass ich schon den Namen der Funktion mit den Variablen ersetzt habe). Ich glaube auch, dass++$i<=$n
dies so umgeschrieben werden kann , dass$n>++$i
Sie ein weiteres Byte sparen.function f($n){$r=str_repeat;$a=[1];while($n>++$i)$a=array_merge($a,[3**$i],$a);foreach($a as$v){$o=$r(' ',$s).$r(x,$v)."\r$o";$s+=$v;}echo$o;}
(Anstatt diese hässliche Newline zu haben, habe ich die Escape-Sequenz\r
in eine Zeichenkette mit doppelten Anführungszeichen eingefügt, in der sich die Variable befindet$o
. Sie"\r$o"
hat also die gleiche Byte-Anzahl wie die''.$o
eine.) mit newline ommited auf das letzte und das gleiche Ergebnis.while
muss sein ,$n>$i++
für diese Reduktion an der Arbeit richtig.$r=str_repeat
Trick. Ich habe nur darüber nachgedacht$r='str_repeat';
, was kein Byte spart. Die undefinierte Konstante ist auch ein guter Trick, gut gemacht;). Eine Newline ist ein Byte kleiner als das Schreiben\n
, daher habe ich sie beibehalten, aber doppelte Anführungszeichen verwendet, um eine Verkettung mit zu vermeiden$0
. Danke noch einmal !3 ** $i
wäre, würde ich sagen, dass Sie eine schreckliche Syntax haben. Sie können diese Korrektur ansprechen. Ich sage nur über dieses und nicht über das,[1]
weil das von PHP5.4 kam, das ziemlich "alt" ist. Vor 1 Jahr würde ich Sie bitten, dies zu spezifizieren. Heute bitte ich Sie, dies einfach (in einer sehr kurzen Zeile) anzugeben. Apropos Code, Sie haben immer noch die,++$i<=$n
die durch ersetzt werden können$n>$i++
. Ich musste Ihren gesamten Code in PHP5.3 konvertieren, um ihn zu testen. Welches war schmerzhaft. Aber ich sehe, Sie haben bisher 7 Bytes gegessen.C 165
Hier ist der gleiche Code entpackt und leicht aufgeräumt:
Dies basiert auf der gleichen Idee wie die Lösung des Problems durch FUZxxl, eine explizite und keine implizite Form für die Zeilen zu verwenden. Die Deklaration von j setzt es auf 2 ^ (n + 1) und die erste while-Schleife berechnet k = 3 ^ (n + 1); dann ist l = 3 ^ (n + 1) -2 ^ (n + 1) die Gesamtbreite der Treppe (dies ist nicht zu schwer zu beweisen). Wir gehen dann alle Zahlen r von 1 bis 2 ^ (n + 1) -1 durch; Wenn es durch (genau) 2 ^ n teilbar ist, planen wir für jedes s = 3 ^ n 'X zu drucken. Ich werde angepasst, um sicherzustellen, dass wir an der richtigen Stelle beginnen: Wir schreiben l Leerzeichen und s 'X, dann eine neue Zeile.
quelle
(*p)()=putchar;
am Anfang hinzuzufügen , umputchar
als aufzurufenp
. Ich denke es sollte funktionieren.CJam,
46 43 41 39 3635 BytesUPDATE jetzt mit einem anderen Ansatz.
Alter Ansatz:
Ziemlich naiv und lang, aber etwas für den Anfang.
Füge eine Erklärung hinzu, sobald ich Golf spiele.
Probieren Sie es hier online aus
quelle
Java,
271269 BytesVerwendet die Methode von grc.
Eingerückt:
Anregungen sind willkommen.
2 Bytes dank mbomb007
quelle
b.size()>0
stattdessen!b.isEmpty()
2 Bytes sparen.Perl, 62
Zuerst wird das Ergebnis iterativ ohne die führenden Leerzeichen berechnet. Fügen Sie sie dann vor jeder Zeile entsprechend der Anzahl der
x
Zeichen im Rest der Zeichenfolge hinzu.quelle
JavaScript (ES6) 104
106 118Bearbeiten Entfernt die rekursive Funktion, die Liste der ‚*‘ für jede Zeile wird iterativ erhalten, mit Bits und Potenzen von 3 Hantieren (wie in vielen anderen Antworten)
Innerhalb der Schleife eine mehrzeilige Zeichenfolge ist buuilt von unten nach oben, eine laufende Zählung zu halten von führenden Leerzeichen in jeder Zeile hinzuzufügen
Erster Versuch entfernt
Die rekursive R-Funktion erstellt für jede Zeile ein Array mit der Nummer '*'. Zum Beispiel ist R (2)
[1, 3, 1, 9, 1, 3, 1]
Dieses Array wird gescannt, um eine mehrzeilige Zeichenfolge von unten nach oben zu erstellen. Dabei wird die laufende Anzahl der führenden Leerzeichen beibehalten, die in jeder Zeile hinzugefügt werden sollen
Test In der Firefox / FireBug-Konsole
Ausgabe
quelle
R - 111 Zeichen
Einfache Implementierung, iterativer Aufbau und langsame Zerstörung des Arrays.
Verwendungszweck:
quelle
n
Argument von der Kommandozeile übernimmtn=scan()
.x
, dass Sie es als Cursor verwenden möchten, noch müssen Sie dies tunif(n)
. Außerdem zählen Zeilenumbrüche meiner Meinung nach als Zeichen.x
. Bin mirif(n)
aber nicht sicher . Ich habe diesen Teil hinzugefügt, um den Fall zu behandelnn=0
. Dasif(n)
dann kehrt zurückF
und gibt daher eine einzelne zurückx
. Wenn ich es entferne, entstehenn=0
unerwünschte Ergebnisse. Neu hier, wusste also nichts über Zeilenumbrüche. Jetzt inklusive!a=0
die Schleife bei setzen und starten,x in 0:n
funktioniert dies auch für n = 0. Dann können Sie das weglassenif(n)
.Rubin, 93
Dies verwendet den gleichen Ansatz wie grc.
quelle