Zeichne die Treppe des Teufels

46

Das Treppenhaus des Teufels ist eine fraktale Funktion, die mit dem Cantor-Set verwandt ist.

Bildbeschreibung hier eingeben

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- nartige 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 0ist 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-1und dehnen Sie jede Zeile um den Faktor drei
  • Riffel zwischen Reihen einzelner xs
  • Verschieben Sie die Zeilen nach rechts, sodass sich xin jeder Spalte genau eine befindet und die Position der ersten xminimal ist, während sie mit den Zeilen abnimmt

Die Ausgabe für n = 1lautet 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 xSingles:

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.

Sp3000
quelle

Antworten:

7

Pyth, 30

jb_u+G+*leGd*HNu+N+^3hTNUQ]1]k

Dies ist ein Programm, das Eingaben von STDIN entgegennimmt und die Methode von grc verwendet, um die Cantor-Menge zu finden. Verwendet das Zeichen ", um die Kurve anzuzeigen.

Probieren Sie es hier online aus.

Erläuterung:

Ich werde den Code in zwei Teilen erklären:

u+N+^3hTNUQ]1
u        UQ]1         : reduce( ... , over range(input), starting with [1])
 +N                   : lambda N,T: N + ...
   +^3hTN             : 3 ** (T+1) + N   (int + list in pyth is interpreted as [int] + list)

Und die Ausgabeformatierung:

jb_u+G+*leGd*HN    ]k
jb_                    : "\n".join(reversed(...)
   u               ]k  : reduce(lambda G,H: ... , over cantor set, starting with [""])
    +G+*leGd           : G + len(G[-1]) * " " + ...
            *HN        : H * '"'

Beachten Sie, dass in Pyth N = "" standardmäßig.

FryAmTheEggman
quelle
32

J ( 73 68 58 41 39 38 35 34 Zeichen)

Nachdem ich einige Zeit über das Problem nachgedacht hatte, fand ich einen völlig anderen Weg, um das Muster der Teufeltreppe zu erzeugen. Die alte Antwort einschließlich ihrer Erklärung wurde entfernt. Sie können in den Überarbeitungen dieser Antwort nachlesen, wie sie war.

Diese Antwort gibt eine Reihe von Leerzeichen und Scharfen zurück, die die Treppe des Teufels darstellen.

' #'{~1(]|.@=@#~[:,3^q:)2}.@i.@^>:

Hier ist die Antwort explizit in zwei Teile geteilt:

f =: 3 : '|. = (, 3 ^ 1 q: y) # y'
g =: 3 : '(f }. i. 2 ^ >: y) { '' #'''

Erläuterung

Der Ansatz ist ein bisschen anders, also beobachten und staunen.

  1. >: 3 - drei inkrementiert, das heißt,

    4
    
  2. 2 ^ >: 3 - zwei hoch drei inkrementiert, das heißt,

    16
    
  3. i. 2 ^ >: 3- die ersten 2 ^ >: 3ganzen Zahlen, das heißt

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    
  4. }. i. 2 ^ 4- die ersten 2 ^ >: 3Ganzzahlen, enthauptet, das heißt,

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    

    Nennen wir diese Sequenz s; wir treten fjetzt ein.

  5. 1 q: s- die Exponenten von 2 in der Primzerlegung jedes Gegenstandes von s. Im Allgemeinen x q: yergibt sich eine Tabelle der Exponenten für die ersten xPrimzahlen in der Primzerlegung von y. Dies ergibt:

    0
    1
    0
    2
    0
    1
    0
    3
    0
    1
    0
    2
    0
    1
    0
    
  6. 3 ^ 1 q: s - drei hoch diese Exponenten, das heißt,

     1
     3
     1
     9
     1
     3
     1
    27
     1
     3
     1
     9
     1
     3
     1
    
  7. , 3 ^ 1 q: s- der Ravel (dh das Argument mit seiner zu einem Vektor zusammengefassten Struktur) des vorherigen Ergebnisses. Dies ist erforderlich, da q:eine unerwünschte Nachlaufachse eingeführt wird. Dies ergibt

     1 3 1 9 1 3 1 27 1 3 1 9 1 3 1
    
  8. (, 3 ^ 1 q: s) # s- jedes Element swird so oft repliziert wie das entsprechende Element im vorherigen Ergebnis, d. H.

    1 2 2 2 3 4 4 4 4 4 4 4 4 4 5 6 6 6 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 10 10 10 11 12 12 12 12 12 12 12 12 12 13 14 14 14 15
    
  9. = (, 3 ^ 1 q: s) # s - die Selbsteinstufung des vorherigen Ergebnisses, dh eine Matrix, in der jede Zeile eines der eindeutigen Elemente des Arguments darstellt, jede Spalte das entsprechende Element des Arguments darstellt und jede Zelle angibt, ob die Elemente von Zeile und Spalte gleich sind, das ist,

    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
    
  10. |. = (, 3 ^ 1 q: s) # s - Das vorherige Ergebnis wurde entlang der vertikalen Achse gespiegelt.

  11. (|. = (, 3 ^ 1 q: s) # s) { ' #'- Die Elemente des vorherigen Ergebnisses, die als Indizes im Array verwendet werden ' #', werden 0durch ersetzt  und 1durch ersetzt #, d. H.

                                                                    #
                                                                 ### 
                                                                #    
                                                       #########     
                                                      #              
                                                   ###               
                                                  #                  
                       ###########################                   
                      #                                              
                   ###                                               
                  #                                                  
         #########                                                   
        #                                                            
     ###                                                             
    #      
    

    das ergebnis wollen wir.

FUZxxl
quelle
Innerhalb des Leistungsschleife (,],~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.
Randomra
#\ statt i.@#und du überholst APL! :)
Randomra
Ihre zweite Lösung funktioniert nicht, weil eine Obergrenze erforderlich wäre, aber ich habe einen anderen Weg gefunden, um APL zu schlagen.
FUZxxl,
Die neue Ausgabe ist die Treppe für die n-1nicht für n.
Randomra
@randomra Ah ... das ist beschissen. Lassen Sie mich sehen, ob es reparabel ist.
FUZxxl
26

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.

){_2"_{\"{{""}"{'2//_.\><*\"\/_><[\]/3\'\_;|#__/(\2\'3_'}(#:|{$#{>_\//(#={/;01*&"\\_|[##={|}$_#></)]$_##|){*_.>.(/?#//~-="{}<_"=#/\}.>"%<.{#{x\"<#_/=&{./1#_#>__<_'\/"#|@_|/{=/'|\"".{/>}]#]>(_<\'{\&#|>=&{{(\=/\{*'"]<$_

Sechseckig angeordnet:

        ) { _ 2 " _ { \ "
       { { " " } " { ' 2 /
      / _ . \ > < * \ " \ /
     _ > < [ \ ] / 3 \ ' \ _
    ; | # _ _ / ( \ 2 \ ' 3 _
   ' } ( # : | { $ # { > _ \ /
  / ( # = { / ; 0 1 * & " \ \ _
 | [ # # = { | } $ _ # > < / ) ]
$ _ # # | ) { * _ . > . ( / ? # /
 / ~ - = " { } < _ " = # / \ } .
  > " % < . { # { x \ " < # _ /
   = & { . / 1 # _ # > _ _ < _
    ' \ / " # | @ _ | / { = /
     ' | \ " " . { / > } ] #
      ] > ( _ < \ ' { \ & #
       | > = & { { ( \ = /
        \ { * ' " ] < $ _

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:

segments →
 │   │ │         │ │   │x   lines
─┼───┼─┼─────────┼─┼───┼─     ↓
 │   │ │         │ │xxx│
─┼───┼─┼─────────┼─┼───┘
 │   │ │         │x│
─┼───┼─┼─────────┼─┘
 │   │ │xxxxxxxxx│
─┼───┼─┼─────────┘
 │   │x│
─┼───┼─┘
 │xxx│
─┼───┘
x│

Damit entspricht das Programm dem folgenden Pseudocode:

n = get integer from stdin

# Calculate the number of lines we need to output.
line = pow(2, n+1)

while line > 0:
    line = line - 1

    # For all segments except the last, the character to use is spaces.
    ch = ' ' (space, ASCII 32)

    # The number of segments in each line is
    # equal to the line number, counting down.
    seg = line

    while seg > 0:
        seg = seg - 1

        # For the last segment, use x’s.
        if seg = 0:
            ch = 'x' (ASCII 120)

        # Calculate the actual segment number, where the leftmost is 1
        n = line - seg

        # Output the segment
        i = pow(3, number of times n can be divided by 2)
        i times: output ch

    output '\n' (newline, ASCII 10)

end program

Lange Erklärung

Bitte beziehen Sie sich auf dieses farbcodierte Codepfaddiagramm.

Ausführungspfad

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:

Speicherlayout

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 immer 3(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 xnur , 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.

Timwi
quelle
8
Das ist einfach altmodischer Wahnsinn.
FUZxxl,
21

Python 2, 78

L=[1]
i=3
exec"L+=[i]+L;i*=3;"*input()
while L:x=L.pop();print' '*sum(L)+'x'*x

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 wiederholt n, um die Zeilenlängen für die Treppe des Teufels zu ermitteln. Dann drucken wir jede Zeile mit Leerzeichen.

grc
quelle
20

APL, 38

⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1

Beispiel:

      ⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1
⎕:
      2
                  x
               xxx 
              x    
     xxxxxxxxx     
    x              
 xxx               
x   

Erläuterung:

⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1

                                     ⎕       ⍝ read a number from the keyboard
                       {           }⍣ ,1      ⍝ apply this function N times to [1]
                               3×⍵           ⍝ multiply each value by 3
                           ∊1,⍪               ⍝ add an 1 in front of each value
                        1,⍨                  ⍝ add an 1 to the end
                     D←                      ⍝ store values in D (lengths of rows)
                   +\                        ⍝ get running sum of D
                  -                          ⍝ negate (negative values on / give spaces)
             0,¯1↓                           ⍝ remove last item and add a 0 to the beginning
                                             ⍝ (each row needs offset of total length of preceding rows)   
         D,⍨¨                                ⍝ join each offset with each row length
   'x'/⍨¨                                    ⍝ get the right number of x-es and spaces for each row
 ↑                                           ⍝ make a matrix out of the rows
⊖                                            ⍝ mirror horizontally 
Marinus
quelle
Das ist eine schöne Lösung.
FUZxxl,
20
Ich finde es toll, dass die Erklärung des Codes wie eine Teufeltreppe aussieht.
Alex A.
Ich habe eine noch kürzere APL-Lösung gefunden.
FUZxxl
14

GNU sed, 142

Nicht die kürzeste Antwort, aber es ist sed !:

s/$/:/
:l
s/x/xxx/g
s/:/:x:/g
tb
:b
s/^1//
tl
s/:x/X/g
s/^/:/
:m
s/.*:([Xx]+)Xx*:$/&\1:/
tm
:n
s/([ :])[Xx](x*Xx*)/\1 \2/g
tn
s/:/\n/g
s/X/x/g

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 1s 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 also 11:

$ echo 11 | sed -rf devils-staircase.sed

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

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

s/[0-9]/<&/g
s/9/8Z/g
s/8/7Z/g
s/7/6Z/g
s/6/5Z/g
s/5/4Z/g
s/4/3Z/g
s/3/2Z/g
s/2/1Z/g
s/1/Z/g
s/0//g
:t
s/Z</<ZZZZZZZZZZ/g
tt
s/<//g
s/$/:/
:l
s/x/xxx/g
s/:/:x:/g
tb
:b
s/^Z//
tl
s/:x/X/g
s/^/:/
:m
s/.*:([Xx]+)Xx*:$/&\1:/
tm
:n
s/([ :])[Xx](x*Xx*)/\1 \2/g
tn
s/:/\n/g
s/X/x/g

Ausgabe:

$ echo 2 | sed -rf devils-staircase.sed

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 
Digitales Trauma
quelle
7
Das ist wirklich cool.
FUZxxl
8

Python 2, 81

def f(n,i=1,s=0):
 if i<2<<n:q=3**len(bin(i&-i))/27;f(n,i+1,s+q);print' '*s+'x'*q

Programmversion (88)

def f(n,s=0):
 if n:q=3**len(bin(n&-n))/27;f(n-1,s+q);print' '*s+'x'*q
f((2<<input())-1)

Die Anzahl der x in der n1-indizierten Zeile ist 3 hoch (der Index des ersten gesetzten Bits in n, beginnend mit lsb).

Feersum
quelle
8

Python 2, 74

def f(n,s=0):
 if~n:B=3**n;A=s+B-2**n;f(n-1,A+B);print' '*A+'x'*B;f(n-1,s)

Ein rekursiver Ansatz. Die Treppe des großen Teufels ist in drei Teile geteilt

  • Der linke rekursive Ast, eine Treppe von der Größe n-1, deren Länge ist3**n - 2**n
  • Die Mittellinie von x', der Länge3**n
  • Der rechte rekursive Ast, eine Treppe der Größe 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 ist 3**(n+1) - 2**(n+1), was die Induktion bestätigt.

Die optionale Variable sspeichert 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.

xnor
quelle
6

CJam, 36 35 33 Bytes

Hier 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):

L0sl~{{3*0s}%0s\+}*{1$,S*\+}%W%N*

Dies wird 0für die Kurve verwendet. Alternativ (mit grcs Trick)

LLl~){3\#a1$++}/{1$,S*\'x*+}%W%N*

welche verwendet x.

Teste es hier.

Erläuterung

Die Grundidee ist, zuerst ein Array mit den Zeilen zu bilden, wie

["0" "000" "0" "000000000" "0" "000" "0"]

Um diese Liste durchzugehen, müssen Sie die richtige Anzahl von Leerzeichen voranstellen.

L0sl~{{3*0s}%0s\+}*{1$,S*\+}%W%N*
L                                 "Push an empty string for later.";
 0s                               "Push the array containing '0. This is the base case.";
   l~                             "Read and evaluate input.";
     {           }*               "Repeat the block that many times.";
      {    }%                     "Map this block onto the array.";
       3*                         "Triple the current string.";
         0s                       "Push a new zero string.";
             0s\+                 "Prepend another zero string.";
                   {       }%     "Map this block onto the result.";
                    1$            "Copy the last line.";
                      ,S*         "Get its length and make a string with that many spaces.";
                         \+       "Prepend the spaces to the current row.";
                             W%   "Reverse the rows.";
                               N* "Join them with newlines.";

Die andere Version funktioniert ähnlich, erzeugt jedoch eine Reihe von Längen, wie z

[1 3 1 9 1 3 1]

Und verwandelt das dann in Zeichenfolgen von xs in der endgültigen Map.

Martin Ender
quelle
6

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.

' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕]
  • - Eingaben von stdin nehmen.
  • ⌽⍳1+⎕- die Reihenfolge der Zahlen von unten bis 0. (zB 3 2 1 0)
  • 3*⌽⍳1+⎕- drei hoch genug (zB 27 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.
FUZxxl
quelle
4

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:

1 =1
2 =1 * 2
3 =3
4 =1 * 2 * 2
5 =5
6 =3 * 2
7 =7

Ich benutze eine einfachere Methode, um diese Potenzen von 2 zu extrahieren: Dies i=m&-mergibt die Folge 1 2 1 4 1 2 1usw. Dies funktioniert wie folgt:

m-1ist dasselbe wie min 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:

          100   01100100
100-1=     99   01100011
-1-99=   -100   10011100
100&-100=   4   00000100

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 etczu Basis 3 umständlich 1 3 1 9 1 3 1 etcist : (Gibt es eine Möglichkeit, dies zu vermeiden Math::?)

def s(n)
  a=[]
  t=0
  1.upto(2*2**n-1){|m|i=3**Math::log(m&-m,2)
    a.unshift" "*t+"x"*i 
    t+=i}
  puts a
end
Level River St
quelle
3

Rubin, 140 99

Mein 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 jedoch eine Menge Code, nur um die führenden Leerzeichen in der Ausgabe richtig zu machen.

def s(n)
  a=["x"]
  1.upto(n){|m|t=" "*a[0].length
    a=a.map{|i|t+" "*3**m+i}+[t+"x"*3**m]+a}
  puts a
end

Bearbeiten: Ruby, 97

Dies verwendet den ähnlichen, aber unterschiedlichen Ansatz, eine numerische Tabelle mit allen im Array erforderlichen x-Zahlen aauf die oben beschriebene Weise zu erstellen, anschließend jedoch eine Tabelle mit Zeichenfolgen zu erstellen. Die Tabelle der Zeichenfolgen wird in Array cmit der seltsam benannten unshiftMethode rückwärts erstellt , um dem vorhandenen Array voran zu stellen.

Derzeit sieht dieser Ansatz besser aus - aber nur um 2 Bytes :-)

def s(n)
  a=c=[]
  (n+1).times{|m|a=a+[3**m]+a}
  t=0
  a.each{|i|c.unshift" "*t+"x"*i
    t+=i}
  puts c
end
Level River St
quelle
1
Sie können ersetzen for m in(0..n-1)do ... endmit n.times{|m|...}.
Omar
@Omar Danke, das versuche ich morgen. Aufgrund der ständigen Syntaxfehler würde man kaum glauben, wie viel Aufwand nötig ist, um das zum Laufen zu bringen. Ich wusste nicht, wie ich auf die iterierende Variable zugreifen sollte, n.timesund das werde ich mir sicher merken. Es beseitigt auch eine end! Allerdings habe ich mich bei dieser Gelegenheit gefragt, ob for m in (1..n)es besser sein könnte, das zu vermeiden (m+1). Gibt es eine kürzere Schreibweise dafür?
Level River St
1
forist vor allem deshalb lang, weil Sie gezwungen sind zu verwenden end(Sie können die dodurch eine neue Zeile oder durch ersetzen ;). Denn 1..ndu kannst verwenden 1.upto(n){|m|...}. Ich mag das Aussehen, (1..n).each{|i|...}aber es ist etwas länger als mit upto. Beachten Sie außerdem, dass das Iterieren durch Aufrufen eachoder uptonicht nur kürzer ist, sondern auch idiomatischeres Ruby berücksichtigt.
Omar
@ Nochmals vielen Dank, 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.
Level River St
3

Haskell, 99 Zeichen

d=q.((iterate((1:).(>>=(:[1]).(*3)))[1])!!)
q[]=[];q(a:r)=sum r&' '++a&'x'++'\n':q r
(&)=replicate

Die Funktion ist d:

λ: putStr $ d 3
                                                                x
                                                             xxx
                                                            x
                                                   xxxxxxxxx
                                                  x
                                               xxx
                                              x
                   xxxxxxxxxxxxxxxxxxxxxxxxxxx
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x
MtnViewMark
quelle
Alle diese Klammern! Gibt es wirklich keine Möglichkeit, mit weniger umzugehen?
FUZxxl,
Sie können durch Vertauschen der Gleichungen für ein Byte verlieren qund dabei q x=xin dem leeren Liste Fall. Außerdem scheinen die Klammern iterate...[1]unnötig zu sein.
Zgarb
3

PHP - 137 Bytes

function f($n){for($a=[];$i<=$n;array_push($a,3**$i++,...$a))$r=str_repeat;foreach($a as$v){$o=$r(' ',$s).$r(x,$v)."
$o";$s+=$v;}echo$o;}

Ich benutze hier den gleichen Trick wie grc . Hier ist die ungolfed Version:

function staircase($n)
{
    $lengthsList = [];
    for ($i = 0; $i <= $n; ++$i) {
        array_push($lengthsList, 3 ** $i, ...$lengthsList);
    }

    $output = '';
    $cumulatedLength = 0;
    foreach ($lengthsList as $length)
    {
        $output = str_repeat(' ', $cumulatedLength) . str_repeat('x', $length) . "\n" . $output;
        $cumulatedLength += $length;
    }

    echo $output;
}
Schwarzes Loch
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<=$ndies so umgeschrieben werden kann , dass $n>++$iSie ein weiteres Byte sparen.
Ismael Miguel
Hier ist Ihre Funktion, mit einem kleinen coolen Trick: 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 \rin 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 ''.$oeine.) mit newline ommited auf das letzte und das gleiche Ergebnis.
Ismael Miguel
Eigentlich ist der Zustand der whilemuss sein , $n>$i++für diese Reduktion an der Arbeit richtig.
Ismael Miguel
@IsmaelMiguel PHP 5.6 ist die letzte Version von PHP, mehr muss ich nicht sagen. Es ist nicht meine Schuld, wenn fast jeder eine alte Version verwendet und wenn die Mehrheit eine veraltete verwendet. Danke für den $r=str_repeatTrick. 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 !
Blackhole
Es würde nur gut für dich aussehen. Wenn mir das nicht bewusst 3 ** $iwä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<=$ndie 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.
Ismael Miguel
3

C 165

#define W while
f(n){int i=n+1,j=1<<i,k=1,l,r,s,t;W(i--)k*=3;l=k-j;W(--j){r=j,s=1;W(!(r%2))r/=2,s*=3;l-=s;t=l;W(t--)putchar(32);W(++t<s)putchar(88);putchar('\n');}}

Hier ist der gleiche Code entpackt und leicht aufgeräumt:

int f(int n) {
    int i=n+1, j=1<<i, k=1;
    while (i--) k*=3;
    int l=k-j;
    while (--j) {
        int r=j,s=1;
        while (!(r%2))
            r/=2, s*=3;
        l-=s;
        int t=l;
        while (t--) putchar(' ');
        while (++t<s) putchar('X');
        putchar('\n');
    }
}

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.

Steven Stadnicki
quelle
definieren Sie W bis; while und lassen Sie int weg, um einige Zeichen zu speichern.
FUZxxl,
auch t = l- = s zum Sparen.
FUZxxl,
@FUZxxl Ich habe beide ausprobiert, aber während C noch implizite Typen für Funktionen zulässt, erlaubte es sie nicht für Variablendeklarationen, selbst mit den "klassischen" Flags (zumindest auf GCC). Und ich versuchte es mit #define W; while, und es schien mir egal zu sein, obwohl ich in der Definition möglicherweise daneben gegangen bin.
Steven Stadnicki
hm ... ich denke man kann den typ nur in einer globalen variablen weglassen. Es bringt dir nicht viel. Sie können versuchen, (*p)()=putchar;am Anfang hinzuzufügen , um putcharals aufzurufen p. Ich denke es sollte funktionieren.
FUZxxl
2

CJam, 46 43 41 39 36 35 Bytes

L0ri),(a*+_W%(;+{3\#'x*+_,S*}%$1>N*

UPDATE jetzt mit einem anderen Ansatz.


Alter Ansatz:

]ri){3f*_,)"x"a*\]z:+}*_s,f{1$,U+:U-S*\N}

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

Optimierer
quelle
Scheint Arbeit zu brauchen. Funktionierte nicht richtig für n = 4, 5, 17. Angezeigte links formatierte Riffles-Zeichenfolgen von x im oberen Teil. Mit n = 17 wurde der Code auf den Bildschirm ausgegeben und der Boden mit x gefüllt.
DavidC
1
@ DavidCarraher Für 4, 5 denke ich, das ist nur der Zeilenumbruch. Wenn Sie die Ausgabe in einen Texteditor ohne Zeilenumbruch kopieren, ist das für mich in Ordnung.
Sp3000,
Okay. Ich weiß, sehen.
DavidC
2

Java, 271 269 ​​Bytes

Verwendet die Methode von grc.

import java.util.*;String a(int a){List<Integer>b=new ArrayList<>();int c=-1,d=1;for(;c++<a;b.add(d),b.addAll(b),b.remove(b.size()-1),d*=3);String f="";for(;b.size()>0;f+="\n"){d=b.remove(b.size()-1);for(int g:b)for(c=0;c<g;c++)f+=' ';for(c=0;c<d;c++)f+='x';}return f;}

Eingerückt:

import java.util.*;
String a(int a){
    List<Integer>b=new ArrayList<>();
    int c=-1,d=1;
    for(;c++<a;b.add(d),b.addAll(b),b.remove(b.size()-1),d*=3);
    String f="";
    for(;b.size()>0;f+="\n"){
        d=b.remove(b.size()-1);
        for(int g:b)
            for(c=0;c<g;c++)
                f+=' ';
        for(c=0;c<d;c++)
            f+='x';
    }
    return f;
}

Anregungen sind willkommen.

2 Bytes dank mbomb007

Die Nummer eins
quelle
Sie könnten b.size()>0stattdessen !b.isEmpty()2 Bytes sparen.
mbomb007
1

Perl, 62

#!perl -p
eval's/x+/$&$&$&
x/g,s/\d*/x
/;'x++$_;s/x+/$"x$'=~y!x!!.$&/ge

Zuerst wird das Ergebnis iterativ ohne die führenden Leerzeichen berechnet. Fügen Sie sie dann vor jeder Zeile entsprechend der Anzahl der xZeichen im Rest der Zeichenfolge hinzu.

nutki
quelle
1

JavaScript (ES6) 104 106 118

Bearbeiten 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

F=n=>{
  for(i=a=s='';++i<2<<n;a=s+'*'.repeat(t)+'\n'+a,s+=' '.repeat(t))
    for(t=u=1;~i&u;u*=2)t*=3;
  return a
}

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

F=n=>
(R=n=>[1].concat(...n?R(n-1).map(n=>[n*3,1]):[]))(n)
.map(n=>a=' '.repeat(s,s-=-n)+'*'.repeat(n)+'\n'+a,a=s='')
&&a 

Test In der Firefox / FireBug-Konsole

F(3)

Ausgabe

                                                                *
                                                             ***
                                                            *
                                                   *********
                                                  *
                                               ***
                                              *
                   ***************************
                  *
               ***
              *
     *********
    *
 ***
*
edc65
quelle
1

R - 111 Zeichen

Einfache Implementierung, iterativer Aufbau und langsame Zerstörung des Arrays.

n=scan()
a=1
if(n)for(x in 1:n)a=c(a,3^x,a)
for(A in a){cat(rep(' ',sum(a)-A),rep('x',A),'\n',sep='');a=a[-1]}

Verwendungszweck:

> source('devil.r')
1: 2
2: 
Read 1 item
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x
koekenbakker
quelle
Guter Punkt, habe meinen Code so geändert, dass er das nArgument von der Kommandozeile übernimmt
koekenbakker
1
Sie sparen 8 Bytes durch Lesen von STDIN. n=scan().
Alex A.
Sie müssen weder deklarieren x, dass Sie es als Cursor verwenden möchten, noch müssen Sie dies tun if(n). Außerdem zählen Zeilenumbrüche meiner Meinung nach als Zeichen.
Freekvd
Danke, da hast du recht x. Bin mir if(n)aber nicht sicher . Ich habe diesen Teil hinzugefügt, um den Fall zu behandeln n=0. Das if(n)dann kehrt zurück Fund gibt daher eine einzelne zurück x. Wenn ich es entferne, entstehen n=0unerwünschte Ergebnisse. Neu hier, wusste also nichts über Zeilenumbrüche. Jetzt inklusive!
Koekenbakker
Wenn Sie a=0die Schleife bei setzen und starten, x in 0:nfunktioniert dies auch für n = 0. Dann können Sie das weglassen if(n).
Freekvd
0

Rubin, 93

f=->n{s,p,k=[1],1;n.times{s=s+[p=p*3]+s};k=s.dup;k.each{m=s.pop;puts' '*s.reduce(0,:+)+?x*m}}

Dies verwendet den gleichen Ansatz wie grc.

Nax
quelle