L' escalier du diable est une fonction fractale liée à l'ensemble de Cantor.

Votre tâche consiste à reproduire cette fonction géniale - dans l’art ASCII!

Contribution

Un seul entier n >= 0, indiquant la taille de la sortie. L'entrée peut être donnée via STDIN, un argument de fonction ou un argument de ligne de commande.

Sortie

L'interprétation ASCII-art de l'escalier du diable à la taille n, soit renvoyée sous forme de chaîne, soit imprimée sur STDOUT. Les espaces de fin à la fin de chaque ligne sont corrects, mais pas les espaces de début. Vous pouvez éventuellement imprimer une nouvelle ligne de fin.

Pour la taille 0, la sortie est simplement:

x

(Si vous le souhaitez, vous pouvez utiliser tout autre caractère ASCII imprimable autre que l'espace, à la place de x.)

Pour la taille n > 0, nous:

• Prendre la sortie de la taille n-1et étirer chaque ligne par un facteur de trois
• Riffle entre les rangées de single xs
• Déplacez les lignes vers la droite pour qu’il y en ait exactement une xdans chaque colonne et que la position de la première xsoit minimale tout en diminuant avec les lignes.

Par exemple, la sortie pour n = 1est:

    x
 xxx
x

Pour obtenir le résultat n = 2, nous étendons chaque ligne d'un facteur trois:

            xxx
   xxxxxxxxx
xxx

Riffle entre les rangées de single x:

x
            xxx
x
   xxxxxxxxx
x
xxx
x

Décalage à droite:

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Comme autre exemple, ici est n = 3.

Notation

C'est du code-golf, donc la solution dans le moins d'octets gagne.

Pyth, 30

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

Il s’agit d’un programme qui prend en entrée STDIN et utilise la méthode de grc pour trouver l’ensemble Cantor. Utilise le caractère "pour afficher la courbe.

Essayez-le en ligne ici.

Explication:

Je vais expliquer le code en deux parties, d’abord, la génération de jeux de rôles:

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)

Et le format de sortie:

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 * '"'

Notez que dans python N = '"' par défaut.

J ( 73 68 58 41 39 38 35 34 caractères)

Après avoir réfléchi au problème pendant un certain temps, j'ai trouvé une manière totalement différente de générer le motif Staircase du diable. L'ancienne réponse, y compris son explication, a été supprimée. Vous pouvez consulter les révisions de cette réponse pour savoir comment elle s'est déroulée.

Cette réponse renvoie un tableau de flans et d'objets tranchants représentant l'escalier du diable.

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

Voici la réponse divisée en deux parties en notation explicite:

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

Explication

L'approche est un peu différente, alors observez et soyez surpris.

1. >: 3 - trois incrémentés, c'est-à-dire

   4
   

2. 2 ^ >: 3 - deux à la puissance de trois augmentée, c'est-à-dire

   16
   

3. i. 2 ^ >: 3- les premiers 2 ^ >: 3entiers, c'est-à-dire

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

4. }. i. 2 ^ 4- les premiers 2 ^ >: 3entiers, décapités, c'est-à-dire

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

   Appelons cette séquence s; nous entrons fmaintenant.

5. 1 q: s- les exposants de 2 dans la décomposition principale de chaque élément de s. En général, x q: ydonne un tableau des exposants pour les premiers xnombres premiers dans la décomposition des nombres premiers de y. Cela donne:

   0
   1
   0
   2
   0
   1
   0
   3
   0
   1
   0
   2
   0
   1
   0
   

6. 3 ^ 1 q: s - trois à la puissance de ces exposants, c'est-à-dire

    1
    3
    1
    9
    1
    3
    1
   27
    1
    3
    1
    9
    1
    3
    1
   

7. , 3 ^ 1 q: s- le ravel (c'est-à-dire l'argument avec sa structure réduite en un vecteur) du résultat précédent. Ceci est nécessaire car q:introduit un axe de fuite indésirable. Cela donne

    1 3 1 9 1 3 1 27 1 3 1 9 1 3 1
   

8. (, 3 ^ 1 q: s) # s- chaque élément de srépliqué aussi souvent que l'élément correspondant dans le résultat précédent, c'est-à-dire

   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 - l'auto-classification du résultat précédent, c'est-à-dire une matrice où chaque ligne représente l'un des éléments uniques de l'argument, chaque colonne représente l'élément correspondant de l'argument et chaque cellule indique si les éléments de la ligne et de la colonne sont égaux, C'est,

   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 - le résultat précédent s'est retourné le long de l'axe vertical.

11. (|. = (, 3 ^ 1 q: s) # s) { ' #'- les éléments du résultat précédent utilisés comme index dans le tableau ' #', sont donc 0remplacés par  et 1sont remplacés par #, c'est-à-dire,

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

    le résultat que nous voulons.

Hexagonie , 217 octets

C'était extrêmement amusant. Merci d'avoir posté ce défi.

Divulgation complète: la langue (Hexagony) n'existait pas au moment où ce défi a été publié. Cependant, je ne l'ai pas inventé, et le langage n'a pas été conçu pour ce défi (ou tout autre défi spécifique).

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

Disposé en hexagone:

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

Le programme n'utilise pas réellement l' #instruction. J'ai donc utilisé ce caractère pour indiquer quelles cellules sont réellement inutilisées.

Comment fonctionne ce programme? Ça dépend. Voulez-vous la version courte ou la version longue?

Courte explication

Pour illustrer ce que j'entends par «ligne» et «segment» dans l'explication suivante, considérons cette dissection de la sortie souhaitée:

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

Avec cela expliqué, le programme correspond au pseudocode suivant:

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

Longue explication

Veuillez vous référer à ce diagramme de chemin de code codé par couleur.

L'exécution commence dans le coin supérieur gauche. La séquence d'instructions ){2'"''3''"2}?)est exécutée (plus quelques annulations redondantes, comme, "{etc.) en suivant un chemin relativement compliqué. Nous commençons avec le pointeur d’instruction n ° 0, surligné en rouge. À mi-parcours, nous passons au n ° 1, en partant du coin supérieur droit et peints en vert forêt. Quand IP # 2 commence en bleu bleuet (au centre à droite), la disposition de la mémoire est la suivante:

Tout au long du programme, les arêtes étiquetées 2a et 2b auront toujours la valeur 2(nous les utilisons pour calculer 2ⁿ⁺¹ et pour diviser par 2, respectivement) et l'arête étiquetée 3 sera toujours 3(nous l'utilisons pour calculer 3).

Nous entrons dans les affaires en entrant dans notre première boucle, surlignée en bleu bleuet. Cette boucle exécute les instructions (}*{=&}{=pour calculer la valeur 2ⁿ⁺¹. Lorsque la boucle se termine, le chemin brun de selle est emprunté, ce qui nous conduit au pointeur d’instruction n ° 3. Cette IP ne fait que barboter le long du bord inférieur à l’ouest en verge d’or jaune et passe rapidement sous le contrôle de l’IP # 4.

Le chemin fuchsia indique comment l’IP n ° 4, en commençant par le coin inférieur gauche, procède rapidement pour décrémenter la ligne , régler ch sur 32(le caractère espace) et seg sur la (nouvelle valeur de) ligne . C’est en raison de la décrémentation précoce que nous commençons réellement par 2ⁿ⁺¹ − 1 et finissons par subir une dernière itération avec la valeur 0. Nous entrons ensuite dans la première boucle imbriquée .

Nous tournons notre attention vers l'indigo ramifié, où, après un bref décrément de seg , nous voyons que chx n'est mis à jour que si seg est maintenant à zéro. Ensuite, n est réglé sur line-seg pour déterminer le numéro réel du segment dans lequel nous sommes. Immédiatement, nous entrons dans une autre boucle, cette fois dans la couleur claire de la tomate.

Ici, nous calculons combien de fois n (le numéro de segment actuel) peut être divisé par 2. Tant que le modulo nous donne zéro, nous incrémentons i et divisons n par 2. Lorsque nous sommes satisfaits, n n'est plus divisible de la sorte , nous passons au gris ardoise, qui contient deux boucles: premièrement, il élève 3 à la puissance du i calculé, puis il émet ch le nombre de fois. Notez que la première de ces boucles contient un[instruction, qui bascule le contrôle sur IP # 3 - celui qui ne prenait que des pas le long du bord inférieur plus tôt. Le corps de la boucle (multipliant par 3 et décrémentant) est exécuté par un IP solitaire n ° 3, emprisonné dans un cercle vert olive sans fin le long du bord inférieur du code. De même, la seconde de ces boucles gris ardoise contient une ]instruction qui active l’IP n ° 5 pour la sortie des canaux et des décrémentations, représentée ici en rouge indien foncé. Dans les deux cas, les pointeurs d’instruction pris au piège de la servitude exécutent docilement une itération à la fois et cèdent le contrôle à l’IP 4, pour attendre que leur service soit de nouveau appelé. Le gris ardoise, quant à lui, rejoint ses frères fuchsia et indigo.

Lorsque seg atteint inévitablement zéro, la boucle indigo se termine dans le chemin vert de la pelouse, qui ne fait que sortir le caractère de nouvelle ligne et se fond rapidement dans le fuchsia pour continuer la boucle de ligne . Au-delà de l'itération finale de la boucle de ligne , se trouve le court chemin ebon de la fin du programme.

Python 2, 78

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

En commençant par la liste L=[1], nous la dupliquons et insérons la prochaine puissance de 3 au milieu, ce qui donne [1, 3, 1]. C'est répété plusieurs nfois pour nous donner les longueurs de rangées pour l'escalier du diable. Ensuite, nous imprimons chaque ligne avec des espaces.

APL, 38

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

Exemple:

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

Explication:

⊖↑'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 

GNU sed, 142

Pas la réponse la plus courte, mais c'est séduit !:

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

Parce que c'est sed (pas d'arithmétique native), je prends des libertés avec la règle "Un seul entier n> = 0, indiquant la taille de la sortie" . Dans ce cas, l'entier en entrée doit être une chaîne de 1s, de longueur n. Je pense que cela "indique" la taille de la sortie, même si ce n'est pas un équivalent numérique direct à n. Ainsi pour n = 2, la chaîne en entrée sera 11:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

Cela semble compléter avec la complexité temporelle exponentielle de O (c ⁿ ), où c est environ 17. n = 8 a pris environ 45 minutes pour moi.

Alternativement, s'il est nécessaire que n soit entré numériquement exactement, alors nous pouvons le faire:

sed, 274 octets

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

Sortie:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

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

Version du programme (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)

Le nombre de x dans la nrangée 1 indexée est 3 à la puissance de (l'indice du premier bit nentré, à partir du lsb).

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)

Une approche récursive. L'escalier size- $ n $ devil est divisé en trois parties

• La branche récursive gauche, un escalier de taille n-1, dont la longueur est3**n - 2**n
• La ligne médiane de x', de longueur3**n
• La branche récursive droite, un escalier de taille n-1, dont la longueur est3**n - 2**n

Notez que la longueur totale des trois parties est 3*(3**n) - 2*(2**n)ou 3**(n+1) - 2**(n+1), ce qui confirme l'induction.

La variable facultative sstocke le décalage des pièces actuelles que nous imprimons. Nous recourrons d’abord vers la branche gauche avec un offset plus grand, puis nous imprimons la ligne centrale, puis nous faisons la branche de droite avec l’offset actuel.

CJam, 36 35 33 octets

Voici une autre approche de CJam (je n'ai pas regardé le code d'Optimizer, donc je ne sais pas si c'est vraiment très différent):

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

Ceci utilise 0pour la courbe. Alternativement, (en utilisant le truc de grc)

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

qui utilise x.

Testez-le ici.

Explication

L’idée de base est de commencer par former un tableau avec les lignes, comme

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

Et ensuite, parcourez cette liste en ajoutant le nombre d’espaces requis.

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.";

L'autre version fonctionne de manière similaire, mais crée un tableau de longueurs, comme

[1 3 1 9 1 3 1]

Et puis transforme cela en chaînes de xs dans la carte finale.

Dyalog APL, 34 caractères

En utilisant l'approche de grc. Dessine l'escalier avec des caractères ⌹(domino) et prend les entrées de stdin. Cette solution suppose ⎕IO←0.

' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕]

• ⎕ - Prendre l’entrée de stdin.
• ⌽⍳1+⎕- la séquence des nombres allant ⎕de 0 à 0. (par exemple 3 2 1 0)
• 3*⌽⍳1+⎕- trois à la puissance de cela (par exemple 27 9 3 1)
• (⊢,,)/3*⌽⍳1+⎕- le résultat précédent plié à droite par la fonction tacite ⊢,,qui est égale au dfn {⍵,⍺,⍵}donnant les longueurs de marche de l'escalier du diable selon l'approche de la grc.
• {⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ les longueurs d'étape converties en étapes.
• (∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕que l' auto-classés, comme dans ma solution J . Notez que ⊖le résultat est déjà retourné correctement.
• ' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕] les numéros remplacés par des blancs et des dominos.

Ruby, 99

Une réponse différente à mon autre, inspirée de la réponse de FUZxxl

FUZxxl note que les nombres de x correspondent au nombre de facteurs de 2 de l'indice. Par exemple, pour n = 2, nous avons la factorisation suivante:

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

J'utilise un moyen plus simple d'extraire ces puissances de 2: i=m&-mce qui donne la séquence, 1 2 1 4 1 2 1etc. Cela fonctionne comme suit:

m-1est le même que mdans ses bits les plus significatifs, mais le bit le moins significatif devient un zéro et tous les zéros à droite deviennent des 1.

Pour pouvoir utiliser AND avec l'original, nous devons retourner les bits. Il y a différentes façons de le faire. Une façon consiste à le soustraire -1.

La formule globale est alors m& (-1 -(m-1)) ce qui simplifie àm&(-m)

Exemple:

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

Voici le code: les nouvelles lignes sont comptées, les retraits sont inutiles et ne sont donc pas comptés, comme mon autre réponse. Il est légèrement plus long que mon autre réponse en raison de la conversion maladroite de la base 2: 1 2 1 4 1 2 1 etcà la base 3: 1 3 1 9 1 3 1 etc(y a-t-il un moyen d'éviter cela 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

Rubis, 140 99

Mon deuxième code Ruby, et ma première utilisation non triviale de ce langage. Les suggestions sont les bienvenues. Le nombre d'octets exclut les espaces de début de ligne, mais inclut les nouvelles lignes (il semble que la plupart des nouvelles lignes ne puissent être supprimées que si elles sont remplacées par au moins une espace.)

La saisie se fait par appel de fonction. La sortie est un tableau de chaînes, que ruby ​​vide facilement sur stdout en tant que liste séparée par une nouvelle ligne avec une seule puts.

L'algorithme est simplement new iteration= previous iteration+ extra row of n**3 x's+ previous iteration. Cependant , il y a beaucoup une quantité juste de code juste pour obtenir les espaces de premier plan dans le droit de sortie.

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

Edit: Ruby, 97

Ceci utilise l'approche similaire mais différente de la construction d'une table numérique de tous les nombres de x nécessaires dans le tableau ade la manière décrite ci-dessus, mais en construisant ensuite une table de chaînes. La table de chaînes est construite à l’arrière dans un tableau en cutilisant la unshiftméthode assez étrange pour ajouter un préfixe au tableau existant.

Actuellement, cette approche semble meilleure - mais seulement de 2 octets :-)

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

Haskell, 99 caractères

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

La fonction est d:

λ: putStr $ d 3
                                                                x
                                                             xxx
                                                            x
                                                   xxxxxxxxx
                                                  x
                                               xxx
                                              x
                   xxxxxxxxxxxxxxxxxxxxxxxxxxx
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

PHP - 137 octets

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;}

J'utilise ici le même truc que grc . Voici la version non-golfée:

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;
}

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');}}

Voici le même code non emballé et légèrement nettoyé:

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');
    }
}

Ceci est basé sur la même idée que la solution de FUZxxl au problème, consistant à utiliser une forme explicite plutôt que implicite pour les lignes. La déclaration de j la met à 2 ^ (n + 1) et la première boucle while calcule k = 3 ^ (n + 1); alors l = 3 ^ (n + 1) -2 ^ (n + 1) est la largeur totale de l'escalier (ce n'est pas trop difficile à prouver). Nous parcourons ensuite tous les nombres r de 1 à 2 ^ (n + 1) -1; pour chacun d'eux, si c'est divisible par (exactement) 2 ^ n, alors nous avons l'intention d'imprimer s = 3 ^ n 'X. l est ajusté pour nous assurer de partir du bon endroit: nous écrivons l espaces et s 'X's, puis une nouvelle ligne.

CJam, 46 43 41 39 36 35 octets

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

MISE À JOUR en utilisant une approche différente maintenant.

Ancienne approche:

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

Assez naïf et long, mais quelque chose à commencer.

Ajoutera une explication une fois que je joue au golf.

Essayez-le en ligne ici

Java, 271 269 ​​octets

Utilise la méthode de 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;}

Dentelé:

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;
}

Toutes les suggestions sont les bienvenues.

2 octets grâce à mbomb007

Perl, 62

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

First calcule le résultat de manière itérative sans les espaces de début. Puis les ajoute avant chaque ligne en fonction du nombre de xcaractères dans le reste de la chaîne.

JavaScript (ES6) 104 106 118

Modifier Suppression de la fonction récursive, la liste des « * » pour chaque ligne , on obtient de manière itérative, de jouer avec les bits et les pouvoirs de 3 (comme dans beaucoup d' autres réponses)
dans la boucle, une chaîne de caractères multiligne est buuilt de haut en bas, en maintenant un compte courant des espaces de début à ajouter sur chaque ligne

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
}

First Try enlevé

La fonction R récursive construit un tableau avec le nombre de '*' pour chaque ligne. Par exemple, R (2) est [1, 3, 1, 9, 1, 3, 1]
Ce tableau est analysé pour créer une chaîne multiligne de bas en haut, en conservant un nombre permanent d'espaces de début à ajouter à chaque ligne.

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 

Testez dans la console Firefox / FireBug

F(3)

Sortie

                                                                *
                                                             ***
                                                            *
                                                   *********
                                                  *
                                               ***
                                              *
                   ***************************
                  *
               ***
              *
     *********
    *
 ***
*

R - 111 caractères

Mise en œuvre simple, en construisant le tableau de manière itérative et en le détruisant lentement.

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]}

Usage:

> source('devil.r')
1: 2
2: 
Read 1 item
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x