La escalera del diablo es una función de tipo fractal relacionada con el conjunto de Cantor.

Su tarea es replicar esta funky función, ¡en el arte ASCII!

Entrada

Un solo entero n >= 0, que indica el tamaño de la salida. La entrada puede darse a través de STDIN, argumento de función o argumento de línea de comandos.

Salida

La versión de arte ASCII de la escalera del Diablo en tamaño n, ya sea devuelta como una cadena o impresa en STDOUT. Los espacios finales al final de cada fila están bien, pero los espacios iniciales no. Opcionalmente, puede imprimir una nueva línea final.

Para el tamaño 0, la salida es solo:

x

(Si lo desea, puede usar cualquier otro carácter ASCII imprimible que no sea espacio, en lugar de x).

Para el tamaño n > 0, nosotros:

• Tome la salida del tamaño n-1y estire cada fila por un factor de tres
• Riffle entre filas de xs individuales
• Desplace las filas hacia la derecha para que haya exactamente una xen cada columna, y la posición de la primera xsea ​​mínima mientras disminuye con las filas.

Por ejemplo, la salida para n = 1es:

    x
 xxx
x

Para obtener la salida n = 2, estiramos cada fila por un factor de tres:

            xxx
   xxxxxxxxx
xxx

Riffle entre filas de solteros x:

x
            xxx
x
   xxxxxxxxx
x
xxx
x

Desplazar hacia la derecha:

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Como otro ejemplo, aquí está n = 3.

Puntuación

Este es el código de golf, por lo que gana la solución en la menor cantidad de bytes.

Pyth, 30

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

Este es un programa que toma información de STDIN y utiliza el método de grc para encontrar el conjunto de Cantor. Utiliza el carácter "para mostrar la curva.

Pruébelo en línea aquí.

Explicación:

Explicaré el código en dos partes, primero, la generación del conjunto cantor:

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)

Y el formato de salida:

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

Tenga en cuenta que en pyth N = '"' por defecto.

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

Después de pensar en el problema por un tiempo, encontré una forma completamente diferente de generar el patrón Escalera del Diablo. Se eliminó la respuesta anterior, incluida su explicación, puede consultar las revisiones de esta respuesta para averiguar cómo fue.

Esta respuesta devuelve una serie de espacios en blanco y objetos punzantes, que representan la escalera del diablo.

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

Aquí está la respuesta dividida en sus dos partes en notación explícita:

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

Explicación

El enfoque es un poco diferente, así que observa y sorpréndete.

1. >: 3 - tres incrementales, es decir,

   4
   

2. 2 ^ >: 3 - dos a la potencia de tres incrementados, es decir,

   16
   

3. i. 2 ^ >: 3- los primeros 2 ^ >: 3enteros, es decir,

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

4. }. i. 2 ^ 4- los primeros 2 ^ >: 3enteros, decapitados, es decir,

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

   Llamemos a esta secuencia s; Entramos fahora.

5. 1 q: s- los exponentes de 2 en la descomposición primaria de cada elemento de s. En general, se x q: yobtiene una tabla de exponentes para los primeros xprimos en la descomposición de primos de y. Esto produce:

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

6. 3 ^ 1 q: s - tres al poder de estos exponentes, es decir,

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

7. , 3 ^ 1 q: s- el enredo (es decir, el argumento con su estructura colapsó en un vector) del resultado anterior. Esto es necesario porque q:introduce un eje final no deseado. Esto produce

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

8. (, 3 ^ 1 q: s) # s- cada elemento de sreplicado con tanta frecuencia como el elemento correspondiente en el resultado anterior, es decir,

   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 - la auto clasificación del resultado anterior, esto es, una matriz donde cada fila representa uno de los elementos únicos del argumento, cada columna representa el elemento correspondiente del argumento y cada celda representa si los elementos de la fila y la columna son iguales, es decir,

   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 - el resultado anterior volteado a lo largo del eje vertical.

11. (|. = (, 3 ^ 1 q: s) # s) { ' #'- los elementos del resultado anterior utilizados como índices en la matriz ' #', por lo que 0se reemplaza por  y 1se reemplaza por #, es decir,

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

    El resultado que queremos.

Hexagonía , 217 bytes.

Esto fue inmensamente divertido. Gracias por publicar este desafío.

Divulgación completa: el idioma (Hexagony) no existía en el momento en que se publicó este desafío. Sin embargo, no lo inventé, y el lenguaje no fue diseñado para este desafío (o cualquier otro desafío específico).

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

Presentado hexagonalmente:

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

El programa en realidad no usa las #instrucciones, así que usé ese carácter para mostrar qué celdas están realmente sin usar.

¿Cómo funciona este programa? Eso depende. ¿Quieres la versión corta o la larga?

Explicación breve

Para ilustrar lo que quiero decir con "línea" y "segmento" en la siguiente explicación, considere esta disección del resultado previsto:

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

Con eso explicado, el programa corresponde al siguiente pseudocódigo:

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

Larga explicación

Consulte este diagrama de ruta de código codificado por color.

La ejecución comienza en la esquina superior izquierda. La secuencia de instrucciones ){2'"''3''"2}?)se ejecuta (más algunas cancelaciones redundantes, como "{etc.) siguiendo una ruta bastante complicada. Comenzamos con el puntero de instrucción # 0, resaltado en carmesí. A mitad de camino, cambiamos al # 1, comenzando en la esquina superior derecha y pintados en verde bosque. Cuando IP # 2 comienza en azul aciano (centro derecha), el diseño de la memoria es el siguiente:

A lo largo de todo el programa, los bordes etiquetados como 2a y 2b siempre tendrán el valor 2(los usamos para calcular 2ⁿ⁺¹ y para dividir entre 2, respectivamente) y el borde etiquetado como 3 siempre será 3(lo usamos para calcular 3ⁱ).

Llegamos a los negocios cuando entramos en nuestro primer bucle, resaltado en azul aciano. Este bucle ejecuta las instrucciones (}*{=&}{=para calcular el valor 2ⁿ⁺¹. Cuando sale el bucle, se toma el camino marrón de la silla de montar, que nos lleva al Puntero de instrucción n. ° 3. Esta IP simplemente se mueve a lo largo del borde inferior hacia el oeste en amarillo dorado y pronto pasa el control a la IP # 4.

La ruta fucsia indica cómo IP # 4, comenzando en la parte inferior izquierda, avanza rápidamente a la línea de disminución , establece ch en 32(el carácter de espacio) y seg en (el nuevo valor de) la línea . Es debido al decremento temprano que en realidad comenzamos con 2ⁿ⁺¹ − 1 y eventualmente experimentamos una última iteración con el valor 0. Luego ingresamos al primer bucle anidado .

Dirigimos nuestra atención al índigo ramificado, donde, después de una breve disminución de seg , vemos que ch se actualiza a xsolo si seg ahora es cero. Luego, n se establece en línea - seg para determinar el número real del segmento en el que estamos. Inmediatamente entramos en otro bucle, esta vez en el color justo del tomate.

Aquí, calculamos cuántas veces se puede dividir n (el número de segmento actual) por 2. Mientras el módulo nos dé cero, incrementaremos i y dividiremos n por 2. Cuando estemos satisfechos, n ya no es divisible. , nos ramificamos en el gris pizarra, que contiene dos bucles: primero eleva 3 a la potencia del i que calculamos, y luego genera ch muchas veces. Observe que el primero de estos bucles contiene un[instrucción, que cambia el control a IP # 3, el que solo estaba dando pequeños pasos a lo largo del borde inferior anteriormente. El cuerpo del bucle (multiplicando por 3 y decrementando) es ejecutado por un solitario IP # 3, encarcelado en un ciclo interminable de color verde oliva oscuro a lo largo del borde inferior del código. Del mismo modo, el segundo de estos bucles de color gris pizarra contiene una ]instrucción que activa IP # 5 para generar ch y decrementar, que se muestra aquí en rojo indio oscuro. En ambos casos, los punteros de instrucción atrapados en la servidumbre ejecutan obedientemente una iteración a la vez y ceden el control de nuevo a IP # 4, solo para esperar el momento en que se solicite su servicio una vez más. El gris pizarra, mientras tanto, se une a sus hermanos fucsia e índigo.

Como seg inevitablemente llega a cero, el bucle índigo sale al camino verde del césped, que simplemente genera el carácter de nueva línea y se fusiona rápidamente con el fucsia para continuar el bucle de línea . Más allá de la iteración final del bucle de línea, se encuentra el corto camino sabon ebon de la finalización final del programa.

Pitón 2, 78

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

Comenzando con la lista L=[1], la duplicamos e insertamos la siguiente potencia de 3 en el medio, lo que resulta en [1, 3, 1]. Esto se repite varias nveces para darnos las longitudes de fila para la escalera del Diablo. Luego imprimimos cada fila rellenada con espacios.

APL, 38

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

Ejemplo:

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

Explicación:

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

No es la respuesta más corta, ¡pero es 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

Debido a que esto es sed (sin aritmética nativa), me estoy tomando libertades con la regla "Un solo entero n> = 0, que indica el tamaño de la salida" . En este caso, el entero de entrada debe ser una cadena de 1s, cuya longitud es n. Creo que esto "indica" el tamaño de la salida, a pesar de que no es un equivalente numérico directo a n. Por lo tanto, para n = 2, la cadena de entrada será 11:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

Esto parece completarse con una complejidad de tiempo exponencial de O (c ⁿ ), donde c es aproximadamente 17. n = 8 me tomó aproximadamente 45 minutos.

Alternativamente, si se requiere que n se ingrese numéricamente exactamente, entonces podemos hacer esto:

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

Salida:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

Pitón 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

Versión del programa (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)

El número de x en la nfila indexada 1 es 3 a la potencia de (el índice del primer bit establecido n, comenzando desde lsb).

Pitón 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)

Un enfoque recursivo. El tamaño- $ n $ escalera del diablo se divide en tres partes

• La rama recursiva izquierda, una escalera de tamaño n-1, cuya longitud es3**n - 2**n
• La línea central de x', de longitud3**n
• La rama recursiva derecha, una escalera de tamaño n-1, cuya longitud es3**n - 2**n

Tenga en cuenta que la longitud total de las tres partes es 3*(3**n) - 2*(2**n)o 3**(n+1) - 2**(n+1), lo que confirma la inducción.

La variable opcional salmacena el desplazamiento de las partes actuales que estamos imprimiendo. Primero recurrimos a la rama izquierda con un desplazamiento más grande, luego imprimimos la línea central, luego hacemos la rama derecha en el desplazamiento actual.

CJam, 36 35 33 bytes

Aquí hay otro enfoque de CJam (no he mirado el código del Optimizador, así que no sé si en realidad es muy diferente):

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

Esto se usa 0para la curva. Alternativamente, (usando el truco de grc)

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

que usos x.

Pruébalo aquí.

Explicación

La idea básica es formar primero una matriz con las filas, como

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

Y luego para ir a través de esta lista, anteponiendo la cantidad correcta de espacios.

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

La otra versión funciona de manera similar, pero crea una variedad de longitudes, como

[1 3 1 9 1 3 1]

Y luego convierte eso en cadenas de xs en el mapa final.

Dyalog APL, 34 caracteres

Usando el enfoque de grc. Dibuja la escalera con caracteres ⌹(dominó) y toma datos de stdin. Esta solución asume ⎕IO←0.

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

• ⎕ - tomar entrada de stdin.
• ⌽⍳1+⎕- la secuencia de los números de ⎕abajo a 0. (por ejemplo 3 2 1 0)
• 3*⌽⍳1+⎕- tres al poder de eso (por ejemplo 27 9 3 1)
• (⊢,,)/3*⌽⍳1+⎕- el resultado anterior doblado desde la derecha por la función tácita ⊢,,que es igual a la dfn {⍵,⍺,⍵}produciendo las longitudes de escalón de la escalera del diablo según el enfoque de grc.
• {⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ las longitudes de paso convertidas en pasos.
• (∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕que la auto-clasificada, como en mi solución J . Tenga en cuenta que ⊖ya voltea el resultado correctamente.
• ' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕] los números reemplazados por espacios en blanco y dominó.

Rubí, 99

Una respuesta diferente a la otra, inspirada en la respuesta de FUZxxl

FUZxxl señala que los números de x corresponden al número de factores de 2 del índice. por ejemplo para n = 2 tenemos la siguiente factorización:

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

Utilizo una forma bastante más directa de extraer estos poderes de 2: i=m&-mque produce la secuencia, 1 2 1 4 1 2 1etc. Esto funciona de la siguiente manera:

m-1es lo mismo que men sus bits más significativos, pero el bit menos significativo de 1 se convierte en cero, y todos los ceros a la derecha se convierten en 1.

Para poder Y esto con el original, necesitamos voltear los bits. Hay varias formas de hacer esto. Una forma es restarlo de -1.

La fórmula general es entonces m& (-1 -(m-1)) que se simplifica am&(-m)

Ejemplo:

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

Aquí está el código: las nuevas líneas se cuentan, las sangrías son innecesarias y, por lo tanto, no se cuentan, como mi otra respuesta. Es un poco más largo que mi otra respuesta debido a la torpe conversión de la base 2: 1 2 1 4 1 2 1 etca la base 3: 1 3 1 9 1 3 1 etc(¿hay alguna manera de evitar eso 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

Rubí, 140 99

Mi segundo código Ruby, y mi primer uso no trivial del lenguaje. Las sugerencias son bienvenidas. El recuento de bytes excluye los espacios iniciales para las sangrías, pero incluye nuevas líneas (parece que la mayoría de las nuevas líneas no se pueden eliminar a menos que se reemplacen por un espacio al menos).

La entrada es por llamada de función. La salida es una matriz de cadenas, que Ruby volca convenientemente en stdout como una lista separada por una nueva línea con una sola puts.

El algoritmo es simplemente new iteration= previous iteration+ extra row of n**3 x's+ previous iteration. Sin embargo, hay una gran cantidad de código solo para obtener los espacios iniciales en la salida correcta.

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

Editar: Ruby, 97

Esto utiliza el enfoque similar pero diferente de construir una tabla numérica de todos los números de x requeridos en la matriz ade la manera descrita anteriormente, pero luego construir una tabla de cadenas después. La tabla de cadenas se construye hacia atrás en una matriz cutilizando el unshiftmétodo con un nombre bastante extraño para anteponer a la matriz existente.

Actualmente este enfoque se ve mejor, pero solo por 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

Haskell, 99 caracteres

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

La función es d:

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

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

Estoy usando aquí el mismo truco que grc . Aquí está la versión sin golf:

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

Aquí está el mismo código desempaquetado y ligeramente limpiado:

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

Esto se basa en la misma idea que la solución de FUZxxl al problema, de usar una forma explícita en lugar de implícita para las filas. La declaración de j lo establece en 2 ^ (n + 1), y el primer ciclo while calcula k = 3 ^ (n + 1); entonces l = 3 ^ (n + 1) -2 ^ (n + 1) es el ancho total de la escalera (esto no es demasiado difícil de probar). Luego pasamos por todos los números r del 1 al 2 ^ (n + 1) -1; para cada uno, si es divisible por (exactamente) 2 ^ n, entonces planeamos imprimir s = 3 ^ n 'X's. l se ajusta para garantizar que comencemos desde el lugar correcto: escribimos l espacios y s 'X's, luego una nueva línea.

CJam, 46 43 41 39 36 35 bytes

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

ACTUALIZAR usando un enfoque diferente ahora.

Viejo enfoque:

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

Bastante ingenuo y largo, pero algo para comenzar.

Agregaré una explicación una vez que lo juegue.

Pruébalo en línea aquí

Java, 271 269 ​​bytes

Utiliza el método 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;}

Sangrado:

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

Cualquier sugerencia es bienvenida.

2 bytes gracias a mbomb007

Perl, 62

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

Primero calcula el resultado iterativamente sin los espacios iniciales. Luego los agrega antes de cada línea de acuerdo con el número de xcaracteres en el resto de la cadena.

JavaScript (ES6) 104 106 118

Editar Se eliminó la función recursiva, la lista de '*' para cada línea se obtiene de forma iterativa, jugando con bits y potencias de 3 (como en muchas otras respuestas)
Dentro del bucle, una cadena multilínea se construye de abajo hacia arriba, manteniendo un recuento continuo de espacios iniciales para agregar en cada línea

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
}

Primer intento eliminado

La función R recursiva crea una matriz con el número de '*' para cada línea. Por ejemplo, R (2) es [1, 3, 1, 9, 1, 3, 1]
Esta matriz se escanea para construir una cadena de varias líneas de abajo hacia arriba, manteniendo un recuento continuo de espacios iniciales para agregar en cada línea

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 

Prueba en la consola Firefox / FireBug

F(3)

Salida

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

R - 111 caracteres

Implementación directa, construyendo la matriz de forma iterativa y destruyéndola lentamente.

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

Uso:

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