A Escadaria do Diabo é uma função semelhante ao fractal relacionada ao conjunto Cantor.

Sua tarefa é replicar essa função descolada - na arte ASCII!

Entrada

Um único inteiro n >= 0, indicando o tamanho da saída. A entrada pode ser fornecida via STDIN, argumento de função ou argumento de linha de comando.

Resultado

A versão em arte ASCII da escada do Diabo em tamanho n, retornou como uma corda ou impressa em STDOUT. Os espaços à direita no final de cada linha são válidos, mas os espaços à esquerda não. Opcionalmente, você pode imprimir uma única nova linha à direita.

Para tamanho 0, a saída é apenas:

x

(Se desejar, você pode usar qualquer outro caractere ASCII imprimível que não seja o espaço, no lugar de x.)

Para o tamanho n > 0, nós:

• Pegue a saída de tamanho n-1e estique cada linha por um fator de três
• Riffle entre linhas de xs
• Desloque as linhas para a direita para que exista exatamente uma xem cada coluna, e a posição da primeira xseja mínima enquanto diminui com as linhas

Por exemplo, a saída para n = 1é:

    x
 xxx
x

Para obter a saída n = 2, esticamos cada linha por um fator de três:

            xxx
   xxxxxxxxx
xxx

Riffle entre linhas de single x:

x
            xxx
x
   xxxxxxxxx
x
xxx
x

Deslocar para a direita:

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Como outro exemplo, aqui está n = 3.

Pontuação

Isso é código-golfe, então a solução com o menor número de bytes vence.

Pyth, 30

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

Este é um programa que recebe informações do STDIN e usa o método do grc para encontrar o conjunto Cantor. Usa o caractere "para exibir a curva.

Experimente online aqui.

Explicação:

Vou explicar o código em duas partes, primeiro, a geração do 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)

E a formatação de saída:

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

Observe que no pyth N = '"' por padrão.

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

Depois de pensar sobre o problema por algum tempo, encontrei uma maneira totalmente diferente de gerar o padrão da Escadaria do Diabo. A resposta antiga, incluindo sua explicação, foi removida. Você pode examinar as revisões desta resposta para descobrir como foi.

Esta resposta retorna uma série de espaços em branco e objectos cortantes, representando a escada do diabo.

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

Aqui está a resposta dividida em duas partes em notação explícita:

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

Explicação

A abordagem é um pouco diferente, então observe e se surpreenda.

1. >: 3 - três incrementados, ou seja,

   4
   

2. 2 ^ >: 3 - dois à potência de três incrementados, ou seja,

   16
   

3. i. 2 ^ >: 3- os primeiros 2 ^ >: 3números inteiros, ou seja,

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

4. }. i. 2 ^ 4- os primeiros 2 ^ >: 3números inteiros decapitados, ou seja,

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

   Vamos chamar essa sequência s; nós entramos fagora.

5. 1 q: s- os expoentes de 2 na decomposição primária de cada item de s. Em geral, x q: yproduz uma tabela dos expoentes para os primeiros xnúmeros primos na decomposição primária de y. Isso produz:

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

6. 3 ^ 1 q: s - três à potência desses expoentes, ou seja,

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

7. , 3 ^ 1 q: s- o deslocamento (isto é, o argumento com sua estrutura colapsado em um vetor) do resultado anterior. Isso é necessário porque q:introduz um eixo final indesejado. Isso gera

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

8. (, 3 ^ 1 q: s) # s- cada item sreplicado com a mesma frequência que o item correspondente no resultado anterior, ou seja,

   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 - a auto-classificação do resultado anterior, isto é, uma matriz em que cada linha representa um dos itens únicos do argumento, cada coluna representa o item correspondente do argumento e cada célula representa se os itens da linha e da coluna são iguais, isso é,

   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 - o resultado anterior virou ao longo do eixo vertical.

11. (|. = (, 3 ^ 1 q: s) # s) { ' #'- os itens do resultado anterior usados ​​como índices na matriz ' #', 0sendo substituídos por  e 1substituídos por #, ou seja,

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

    o resultado que queremos.

Hexagonia , 217 bytes

Isso foi imensamente divertido. Obrigado por postar este desafio.

Divulgação completa: o idioma (Hexagony) não existia no momento em que este desafio foi lançado. No entanto, eu não o inventei e a linguagem não foi projetada para esse desafio (ou qualquer outro desafio específico).

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

Dispostas hexagonalmente:

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

Na verdade, o programa não usa as #instruções, então usei esse caractere para mostrar quais células são genuinamente não utilizadas.

Como é que este programa funciona? Depende. Você quer a versão curta ou a longa?

Breve explicação

Para ilustrar o que quero dizer com "linha" e "segmento" na explicação a seguir, considere esta dissecação da saída pretendida:

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

Com isso explicado, o programa corresponde ao seguinte 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

Explicação longa

Consulte este diagrama de caminho de código com código de cores.

A execução começa no canto superior esquerdo. A sequência de instruções ){2'"''3''"2}?)é executada (mais alguns cancelamentos redundantes, como "{etc.), seguindo um caminho bastante complicado. Começamos com o ponteiro de instrução # 0, destacado em vermelho. No meio, passamos para o número 1, começando no canto superior direito e pintado em verde floresta. Quando o IP 2 inicia em azul centáurea (meio à direita), o layout da memória é o seguinte:

Durante todo o programa, as arestas rotuladas 2a e 2b sempre terão o valor 2(as usamos para calcular 2ⁿ⁺¹ e dividir por 2, respectivamente) e a aresta rotulada 3 sempre será 3(usamos isso para calcular 3ⁱ).

Chegamos aos negócios quando entramos em nosso primeiro ciclo, destacado em azul centáurea. Este loop executa as instruções (}*{=&}{=para calcular o valor 2ⁿ⁺¹. Quando o loop sai, o caminho de sela marrom é percorrido, o que nos leva ao Ponteiro de Instrução # 3. Esse IP apenas se move ao longo da borda inferior para o oeste em amarelo dourado e logo passa o controle para o IP # 4.

O caminho fúcsia indica como o IP # 4, começando no canto inferior esquerdo, prossegue rapidamente para diminuir a linha , defina ch como 32(o caractere de espaço) e seg como (o novo valor de) linha . É devido ao decréscimo inicial que realmente começamos com 2 start-1 e, finalmente, experimentamos uma última iteração com o valor 0. Em seguida, inserimos o primeiro loop aninhado .

Voltamos nossa atenção para o índigo ramificado, onde, após um breve decréscimo de seg , vemos ch atualizado para xapenas se seg agora for zero. Depois, n é definido como line - seg para determinar o número real do segmento em que estamos. Imediatamente entramos em outro loop, desta vez na cor clara do tomate.

Aqui, calculamos quantas vezes n (o número do segmento atual) pode ser dividido por 2. Enquanto o módulo nos der zero, incrementamos ie dividimos n por 2. Quando estivermos satisfeitos, n não será mais assim divisível , ramificamos para o cinza ardósia, que contém dois loops: primeiro, aumenta 3 à potência do i calculada e, em seguida, gera ch isso muitas vezes. Observe que o primeiro desses loops contém um[instrução, que alterna o controle para o IP nº 3 - aquele que estava apenas dando pequenos passos ao longo da borda inferior anteriormente. O corpo do loop (multiplicando por 3 e decrementando) é executado por um IP solitário nº 3, preso em um ciclo interminável de verde azeitona escuro ao longo da borda inferior do código. Da mesma forma, o segundo desses loops em cinza ardósia contém uma ]instrução que ativa o IP # 5 para gerar ch e decrement, mostrados aqui em vermelho indiano escuro. Nos dois casos, os Indicadores de Instrução presos em servidão obedientemente executam uma iteração de cada vez e devolvem o controle ao IP # 4, apenas para aguardar o momento em que seu serviço seja chamado novamente. Enquanto isso, o cinza ardósia se une a seus irmãos fúcsia e índigo.

Como seg inevitavelmente chega a zero, o loop índigo sai para o caminho verde do gramado, que apenas gera o caractere de nova linha e imediatamente se funde novamente no fúcsia para continuar o loop de linha . Além da iteração final do loop de linha, encontra-se o caminho de ébano curto possível de finalizar o programa.

Python 2, 78

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

Começando com a lista L=[1], duplicamos e inserimos a próxima potência de 3 no meio, resultando em [1, 3, 1]. Isso é repetido várias nvezes para nos dar o comprimento da linha da escada do diabo. Em seguida, imprimimos cada linha preenchida com espaços.

APL, 38

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

Exemplo:

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

Explicação:

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

Não é a resposta mais curta, mas é 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

Como isso é sed (sem aritmética nativa), estou assumindo liberdades com a regra "Um único número inteiro n> = 0, indicando o tamanho da saída" . Nesse caso, o número inteiro de entrada deve ser uma sequência de 1s, cujo comprimento é n. Eu acho que isso está "indicando" o tamanho da saída, mesmo que não seja um equivalente numérico direto a n. Assim, para n = 2, a sequência de entrada será 11:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

Isso parece completo com a complexidade de tempo exponencial de O (c ⁿ ), onde c é de cerca de 17. n = 8 levou cerca de 45 minutos para mim.

Como alternativa, se for necessário que n seja digitado exatamente numericamente, podemos fazer o seguinte:

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

Resultado:

$ 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

Versão do 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)

O número de x na n1ª linha indexada é 3 à potência de (o índice do primeiro bit definido n, iniciando no 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)

Uma abordagem recursiva. A escada do tamanho de $ n $ diabo é dividida em três partes

• O ramo recursivo esquerdo, uma escada de tamanho n-1, cujo comprimento é3**n - 2**n
• A linha central de x', de comprimento3**n
• O ramo recursivo direito, uma escada de tamanho n-1, cujo comprimento é3**n - 2**n

Observe que o comprimento total das três partes é 3*(3**n) - 2*(2**n)ou 3**(n+1) - 2**(n+1), o que confirma a indução.

A variável opcional sarmazena o deslocamento das peças atuais que estamos imprimindo. Primeiro recuamos para o ramo esquerdo com deslocamento maior, depois imprimimos a linha central e, em seguida, fazemos o ramo direito no deslocamento atual.

CJam, 36 35 33 bytes

Aqui está outra abordagem CJam (eu não olhei para o código do Optimizer, então não sei se é realmente muito diferente):

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

Isso usa 0para a curva. Alternativamente, (usando o truque do grc)

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

qual usa x.

Teste aqui.

Explicação

A idéia básica é primeiro formar uma matriz com as linhas, como

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

E então, percorrer esta lista, acrescentando a quantidade certa de espaços.

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

A outra versão funciona da mesma forma, mas cria uma variedade de comprimentos, como

[1 3 1 9 1 3 1]

E depois transforma isso em sequências de xs no mapa final.

Dyalog APL, 34 caracteres

Usando a abordagem do grc. Desenha a escada com ⌹caracteres (dominó) e recebe a entrada de stdin. Esta solução assume ⎕IO←0.

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

• ⎕ - pegue a entrada de stdin.
• ⌽⍳1+⎕- a sequência dos números de ⎕baixo a 0. (por exemplo 3 2 1 0)
• 3*⌽⍳1+⎕- três ao poder disso (por exemplo 27 9 3 1)
• (⊢,,)/3*⌽⍳1+⎕- o resultado anterior dobrado da direita pela função tácita, ⊢,,que é igual ao dfn, {⍵,⍺,⍵}produzindo os comprimentos dos degraus da escada do diabo de acordo com a abordagem do grc.
• {⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ os comprimentos das etapas convertidos em etapas.
• (∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕que a auto-classificada, como na minha solução J . Observe que ⊖já vira o resultado corretamente.
• ' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕] os números substituídos por espaços em branco e dominó.

Ruby, 99

Uma resposta diferente da minha outra, inspirada na resposta de FUZxxl

FUZxxl observa que os números de x correspondem ao número de fatores de 2 do índice. por exemplo para n = 2, temos a seguinte fatoração:

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

Eu uso uma maneira bastante mais direta de extrair esses poderes de 2: o i=m&-mque produz a sequência 1 2 1 4 1 2 1etc. Isso funciona da seguinte maneira:

m-1é o mesmo que mnos bits mais significativos, mas o bit 1 menos significativo se torna zero e todos os zeros à direita se tornam 1s.

Para poder E com o original, precisamos inverter os bits. Existem várias maneiras de fazer isso. Uma maneira é subtraí-lo -1.

A fórmula geral é então m& (-1 -(m-1)) que simplifica am&(-m)

Exemplo:

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

Aqui está o código: novas linhas são contadas, os recuos são desnecessários e, portanto, não são contados, como minha outra resposta. É um pouco mais longo do que minha outra resposta devido à conversão desajeitada da base 2: 1 2 1 4 1 2 1 etcpara a base 3: 1 3 1 9 1 3 1 etc(existe uma maneira de evitar isso 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

Ruby, 140 99

Meu segundo código Ruby, e meu primeiro uso não trivial da linguagem. Sugestões são bem-vindas. A contagem de bytes exclui espaços iniciais para recuos, mas inclui novas linhas (parece que a maioria das novas linhas não pode ser excluída, a menos que sejam substituídas por um espaço, pelo menos).

A entrada é por chamada de função. A saída é uma matriz de strings, que o ruby ​​despeja convenientemente no stdout como uma lista separada por nova linha com uma única puts.

O algoritmo é simplesmente new iteration= previous iteration+ extra row of n**3 x's+ previous iteration. No entanto, existe uma quantidade razoável de código apenas para obter os espaços iniciais na saída correta.

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

Edição: Ruby, 97

Isso usa a abordagem semelhante, porém diferente, de criar uma tabela numérica com todos os números de x exigidos na matriz ada maneira descrita acima, mas depois construir uma tabela de seqüências de caracteres posteriormente. A tabela de seqüências de caracteres é construída de trás para a frente na matriz cusando o unshiftmétodo de nome bastante estranho para preceder a matriz existente.

Atualmente, essa abordagem está melhor - mas apenas 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

A função é 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;}

Estou usando aqui o mesmo truque do grc . Aqui está a versão não destruída:

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

Aqui está o mesmo código descompactado e ligeiramente limpo:

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

Isso se baseia na mesma idéia que a solução da FUZxxl para o problema, de usar um formulário explícito, e não implícito, para as linhas. A declaração de j define-a como 2 ^ (n + 1), e o primeiro loop while calcula k = 3 ^ (n + 1); então l = 3 ^ (n + 1) -2 ^ (n + 1) é a largura total da escada (não é tão difícil de provar). Passamos então por todos os números r de 1 a 2 ^ (n + 1) -1; para cada um, se é divisível por (exatamente) 2 ^ n, planejamos imprimir s = 3 ^ n 'X' s. l é ajustado para garantir que comecemos do ponto certo: escrevemos l espaços e s 'X's, depois uma nova linha.

CJam, 46 43 41 39 36 35 bytes

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

ATUALIZE agora usando uma abordagem diferente.

Abordagem antiga:

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

Bastante ingênuo e longo, mas algo para começar.

Adicionará uma explicação assim que eu jogar.

Experimente online aqui

Java, 271 269 ​​bytes

Usa o método do 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;}

Recuado:

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

Todas as sugestões são bem-vindas.

2 bytes graças a mbomb007

Perl, 62

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

Primeiro calcula o resultado iterativamente sem os espaços à esquerda. Em seguida, adicione-os antes de cada linha, de acordo com o número de xcaracteres no restante da string.

JavaScript (ES6) 104 106 118

Editar Removida a função recursiva, a lista de '*' para cada linha é obtido de forma iterativa, brincando com pedaços e poderes de 3 (como em muitas outras respostas)
Dentro do loop, uma string de múltiplas linhas é buuilt de até inferior, mantendo uma contagem de espaços à esquerda para adicionar em cada linha

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
}

Primeira tentativa removida

A função R recursiva cria uma matriz com o número de '*' para cada linha. Por exemplo, R (2) é [1, 3, 1, 9, 1, 3, 1]
Esta matriz é varrida para criar uma cadeia de linhas múltiplas de baixo para cima, mantendo uma contagem contínua de espaços à esquerda para adicionar em cada linha

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 

Teste no console Firefox / FireBug

F(3)

Resultado

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

R - 111 caracteres

Implementação direta, construindo a matriz iterativamente e destruindo-a 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