The Devil's Staircase adalah fungsi seperti fraktal yang terkait dengan set Cantor.

Tugas Anda adalah mereplikasi fungsi funky ini - dalam seni ASCII!

Memasukkan

Bilangan bulat tunggal n >= 0, menunjukkan ukuran output. Input dapat diberikan melalui STDIN, argumen fungsi atau argumen baris perintah.

Keluaran

Karya ASCII-art dari tangga Iblis ukurannya n, baik dikembalikan sebagai string atau dicetak ke STDOUT. Mengejar spasi di akhir setiap baris tidak apa-apa, tetapi spasi di depan tidak. Anda dapat secara opsional mencetak satu baris baru.

Untuk ukuran 0, outputnya hanya:

x

(Jika diinginkan, Anda dapat menggunakan karakter ASCII lain yang dapat dicetak selain ruang, sebagai ganti x.)

Untuk ukuran n > 0, kami:

• Ambil output ukuran n-1dan regangkan setiap baris dengan faktor tiga
• Riffle di antara barisan single xs
• Geser baris ke kanan sehingga tepat ada satu xdi setiap kolom, dan posisi yang pertama xminimal sambil mengurangi dengan baris

Sebagai contoh, output untuk n = 1adalah:

    x
 xxx
x

Untuk mendapatkan hasil n = 2, kami meregangkan setiap baris dengan faktor tiga:

            xxx
   xxxxxxxxx
xxx

Riffle diantara baris single x:

x
            xxx
x
   xxxxxxxxx
x
xxx
x

Bergeser ke kanan:

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Sebagai contoh lain, di sini adalah n = 3.

Mencetak gol

Ini adalah kode-golf, jadi solusi dalam byte paling sedikit menang.

Pyth, 30

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

Ini adalah program yang mengambil input dari STDIN dan menggunakan metode grc untuk menemukan set Cantor. Gunakan karakter "untuk menampilkan kurva.

Cobalah online di sini.

Penjelasan:

Saya akan menjelaskan kode dalam dua bagian, pertama, generasi set 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)

Dan format output:

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

Perhatikan bahwa dalam pyth N = '"' secara default.

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

Setelah memikirkan masalah selama beberapa waktu, saya menemukan cara yang sama sekali berbeda untuk menghasilkan pola Tangga Iblis. Jawaban lama termasuk penjelasannya telah dihapus, Anda dapat melihat revisi dari jawaban ini untuk mengetahui bagaimana itu.

Jawaban ini mengembalikan array kosong dan benda tajam, mewakili tangga setan.

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

Berikut adalah jawaban yang dibagi menjadi dua bagian dalam notasi eksplisit:

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

Penjelasan

Pendekatannya sedikit berbeda, jadi amati dan kagum.

1. >: 3 - tiga bertambah, yaitu,

   4
   

2. 2 ^ >: 3 - dua pangkat tiga bertambah, yaitu,

   16
   

3. i. 2 ^ >: 3- 2 ^ >: 3bilangan bulat pertama , yaitu,

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

4. }. i. 2 ^ 4- 2 ^ >: 3Bilangan bulat pertama , dipenggal, yaitu,

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

   Mari kita sebut urutan ini s; kita masuk fsekarang.

5. 1 q: s- eksponen 2 dalam dekomposisi utama setiap item s. Secara umum, x q: ymenghasilkan tabel eksponen untuk xbilangan prima pertama dalam dekomposisi utama y. Ini menghasilkan:

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

6. 3 ^ 1 q: s - Tiga pangkat eksponen ini, yaitu,

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

7. , 3 ^ 1 q: s- Ravel (yaitu argumen dengan strukturnya runtuh menjadi vektor) dari hasil sebelumnya. Ini diperlukan karena q:memperkenalkan sumbu trailing yang tidak diinginkan. Ini menghasilkan

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

8. (, 3 ^ 1 q: s) # s- setiap item sdireplikasi sesering item yang sesuai dalam hasil sebelumnya, yaitu,

   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 - Klasifikasi diri dari hasil sebelumnya, ini adalah, matriks di mana setiap baris mewakili salah satu item unik dari argumen, setiap kolom mewakili item yang sesuai dari argumen dan setiap sel mewakili apakah item baris dan kolom sama, itu adalah,

   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 - hasil sebelumnya terbalik di sepanjang sumbu vertikal.

11. (|. = (, 3 ^ 1 q: s) # s) { ' #'- item dari hasil sebelumnya digunakan sebagai indeks ke dalam array ' #', jadi 0digantikan oleh  dan 1digantikan oleh #, yaitu,

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

    hasil yang kita inginkan.

Hexagony , 217 byte

Ini sangat menyenangkan. Terima kasih telah mengirimkan tantangan ini.

Pengungkapan penuh: Bahasa (Hexagony) tidak ada pada saat tantangan ini diposting. Namun, saya tidak menciptakannya, dan bahasanya tidak dirancang untuk tantangan ini (atau tantangan spesifik lainnya).

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

Ditata secara heksagon:

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

Program tidak benar-benar menggunakan #instruksi, jadi saya menggunakan karakter itu untuk menunjukkan sel mana yang benar-benar tidak digunakan.

Bagaimana cara kerja program ini? Itu tergantung. Apakah Anda ingin versi pendek, atau panjang?

Penjelasan singkat

Untuk mengilustrasikan apa yang saya maksud dengan "garis" dan "segmen" dalam penjelasan berikut, pertimbangkan diseksi ini dari output yang dimaksudkan:

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

Dengan penjelasan itu, program berhubungan dengan pseudocode berikut:

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

Penjelasan panjang

Silakan lihat diagram jalur kode kode warna ini.

Eksekusi dimulai di sudut kiri atas. Urutan instruksi ){2'"''3''"2}?)dieksekusi (ditambah beberapa pembatalan yang berlebihan, seperti "{dll.) Dengan mengejar jalur yang cukup berbelit-belit. Kita mulai dengan Instruction Pointer # 0, disorot dalam crimson. Di tengah jalan, kami beralih ke # 1, mulai dari sudut kanan atas dan dicat hijau hutan. Ketika IP # 2 dimulai dengan warna biru jagung (kanan tengah), tata letak memorinya adalah ini:

Sepanjang keseluruhan program, tepi berlabel 2a dan 2b akan selalu memiliki nilai 2(kami menggunakannya untuk menghitung 2ⁿ⁺¹ dan untuk membagi dengan 2, masing-masing) dan tepi berlabel 3 akan selalu 3(kami menggunakannya untuk menghitung 3ⁱ).

Kami mulai berbisnis saat kami memasuki lingkaran pertama kami, disorot dengan warna biru bunga jagung. Loop ini menjalankan instruksi (}*{=&}{=untuk menghitung nilai 2ⁿ⁺¹. Ketika loop keluar, jalur sadel coklat diambil, yang membawa kita ke Instruction Pointer # 3. IP ini hanya berkecimpung di sepanjang tepi bawah ke arah barat dengan warna kuning keemasan dan segera memberikan kontrol ke IP # 4.

Jalur fuchsia menunjukkan bagaimana IP # 4, mulai dari kiri bawah, berjalan dengan cepat ke garis penurunan , set ch ke 32(karakter spasi) dan seg ke (nilai baru dari) baris . Hal ini disebabkan oleh penurunan awal yang sebenarnya kita mulai dengan 2ⁿ⁺¹ − 1 dan akhirnya mengalami iterasi terakhir dengan nilai 0. Kami kemudian memasuki loop bersarang pertama .

Kita mengalihkan perhatian kita ke indigo bercabang, di mana, setelah penurunan singkat dari seg , kita melihat ch diperbarui xhanya jika seg sekarang nol. Setelah itu, n disetel ke garis - seg untuk menentukan jumlah sebenarnya dari segmen yang kita masuki. Segera kita memasuki lingkaran lain, kali ini dalam warna tomat yang adil.

Di sini, kita mencari tahu berapa kali n (jumlah segmen saat ini) dapat dibagi dengan 2. Selama modulo memberi kita nol, kita menambah i dan membagi n dengan 2. Ketika kita puas n tidak lagi dengan demikian dapat dibagi , kita bercabang ke dalam abu-abu batu tulis, yang berisi dua loop: pertama itu meningkatkan 3 pangkat dari i yang kita hitung, dan kemudian menghasilkan ch yang berkali-kali. Perhatikan bahwa loop pertama ini berisi a[instruksi, yang beralih kontrol ke IP # 3 - yang hanya mengambil langkah kecil di sepanjang tepi bawah sebelumnya. Tubuh loop (dikalikan dengan 3 dan decrementing) dieksekusi oleh IP # 3 yang kesepian, dipenjara dalam siklus hijau zaitun gelap tak berujung di sepanjang tepi bawah kode. Demikian pula, yang kedua dari loop abu-abu batu tulis ini berisi ]instruksi, yang mengaktifkan IP # 5 untuk menghasilkan ch dan pengurangan, ditunjukkan di sini dalam warna merah India gelap. Dalam kedua kasus tersebut, Instruksi Pointer yang terjebak dalam perbudakan dengan patuh melaksanakan satu iterasi pada satu waktu dan memberikan kontrol kembali ke IP # 4, hanya untuk menunggu saat layanan mereka dipanggil sekali lagi. Sementara itu, abu-abu batu tulis bergabung kembali dengan saudara-saudaranya yang fuchsia dan nila.

Ketika seg tak terelakkan mencapai nol, loop nila keluar ke jalur hijau halaman, yang hanya menampilkan karakter baris baru dan segera bergabung kembali ke fuchsia untuk melanjutkan loop baris . Di luar iterasi akhir dari loop line, terdapat jalur ebon pendek dari terminasi program akhir.

Python 2, 78

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

Dimulai dengan daftar L=[1], kami menduplikatnya dan menyisipkan kekuatan 3 berikutnya di tengah, menghasilkan [1, 3, 1]. Ini berulang nkali untuk memberi kita panjang baris untuk tangga Iblis. Kemudian kami mencetak setiap baris yang diisi dengan spasi.

APL, 38

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

Contoh:

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

Penjelasan:

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

Bukan jawaban terpendek, tetapi 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

Karena ini adalah sed (bukan aritmatika asli), saya mengambil kebebasan dengan aturan "Bilangan bulat tunggal n> = 0, menunjukkan ukuran output" . Dalam hal ini integer input harus berupa string 1s, yang panjangnya adalah n. Saya pikir ini "menunjukkan" ukuran output, meskipun itu bukan setara numerik langsung dengan n. Jadi untuk n = 2, string input akan menjadi 11:

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

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$ 

Ini tampaknya lengkap dengan kompleksitas waktu eksponensial dari O (c ⁿ ), di mana c adalah sekitar 17. n = 8 membutuhkan waktu sekitar 45 menit untuk saya.

Atau jika diperlukan bahwa n dimasukkan tepat secara numerik, maka kita bisa melakukan ini:

sed, 274 byte

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

Keluaran:

$ 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

Versi program (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)

Jumlah x pada baris nke-1 yang diindeks adalah 3 pangkat (indeks dari bit set pertama n, mulai dari 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)

Pendekatan rekursif. Ukuran- $ n $ tangga setan dibagi menjadi tiga bagian

• Cabang rekursif kiri, tangga ukuran n-1, yang panjangnya3**n - 2**n
• Garis tengah x', panjangnya3**n
• Cabang rekursif yang tepat, tangga ukuran n-1, yang panjangnya3**n - 2**n

Perhatikan bahwa panjang total dari tiga bagian adalah 3*(3**n) - 2*(2**n)atau 3**(n+1) - 2**(n+1), yang mengkonfirmasi induksi.

Variabel opsional smenyimpan offset bagian yang saat ini kami cetak. Pertama-tama kita kambuh ke cabang kiri dengan offset yang lebih besar, lalu cetak garis tengah, lalu lakukan cabang kanan pada offset saat ini.

CJam, 36 35 33 byte

Berikut ini adalah pendekatan CJam lain (saya belum melihat kode Pengoptimal, jadi saya tidak tahu apakah itu sebenarnya jauh berbeda):

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

Ini digunakan 0untuk kurva. Atau, (menggunakan trik grc)

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

yang menggunakan x.

Uji di sini.

Penjelasan

Ide dasarnya adalah untuk pertama-tama membentuk array dengan baris, seperti

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

Dan kemudian untuk pergi melalui daftar ini, mengawali jumlah ruang yang tepat.

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

Versi lain berfungsi sama, tetapi membuat array dengan panjang, seperti

[1 3 1 9 1 3 1]

Dan kemudian mengubahnya menjadi string xs di peta akhir.

Dyalog APL, 34 karakter

Menggunakan pendekatan oleh grc. Gambar tangga dengan ⌹karakter (domino) dan ambil input dari stdin. Solusi ini mengasumsikan ⎕IO←0.

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

• ⎕ - ambil input dari stdin.
• ⌽⍳1+⎕- urutan angka dari ⎕bawah ke 0. (misalnya 3 2 1 0)
• 3*⌽⍳1+⎕- tiga pangkat dari itu (misalnya 27 9 3 1)
• (⊢,,)/3*⌽⍳1+⎕- hasil sebelumnya dilipat dari kanan oleh fungsi diam-diam ⊢,,yang sama dengan dfn {⍵,⍺,⍵}menghasilkan panjang langkah tangga iblis sesuai pendekatan grc.
• {⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ panjang langkah diubah menjadi langkah.
• (∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕itu diklasifikasikan sendiri, seperti dalam solusi J saya . Perhatikan bahwa ⊖sudah membalik hasilnya dengan benar.
• ' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕] angka-angka digantikan oleh blanko dan domino.

Ruby, 99

Jawaban berbeda dari jawaban saya yang lain, terinspirasi oleh jawaban FUZxxl

FUZxxl mencatat bahwa jumlah x sesuai dengan jumlah faktor 2 indeks. misalnya untuk n = 2 kita memiliki faktorisasi berikut:

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

Saya menggunakan cara yang lebih mudah untuk mengekstraksi kekuatan 2 ini: i=m&-myang menghasilkan urutan 1 2 1 4 1 2 1dll. Ini berfungsi sebagai berikut:

m-1adalah sama mdengan bit yang paling signifikan, tetapi bit 1 yang paling signifikan menjadi nol, dan semua nol di sebelah kanan menjadi 1.

Untuk dapat DAN ini dengan yang asli, kita perlu membalik bit. Ada berbagai cara untuk melakukan ini. Salah satu caranya adalah dengan mengurangi -1.

Rumus keseluruhan inilah m& (-1 -(m-1)) yang disederhanakan menjadim&(-m)

Contoh:

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

Inilah kodenya: baris baru dihitung, indentasi tidak perlu dan karenanya tidak dihitung, seperti jawaban saya yang lain. Ini sedikit lebih lama dari jawaban saya yang lain karena konversi yang canggung dari basis 2: 1 2 1 4 1 2 1 etcke basis 3: 1 3 1 9 1 3 1 etc(apakah ada cara untuk menghindari itu 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

Kode Ruby kedua saya, dan penggunaan bahasa saya yang non-privat pertama. Saran dipersilahkan. Jumlah byte tidak termasuk spasi awal untuk indentasi, tetapi termasuk baris baru (tampaknya sebagian besar baris baru tidak dapat dihapus kecuali jika mereka diganti dengan spasi setidaknya.)

Input adalah dengan panggilan fungsi. Output adalah array string, yang ruby ​​dengan mudah dibuang ke stdout sebagai daftar yang dipisahkan dengan baris baru dengan satu puts.

Algoritma ini hanya new iteration= previous iteration+ extra row of n**3 x's+ previous iteration. Namun ada banyak cukup kode hanya untuk mendapatkan ruang terkemuka dalam output yang tepat.

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

Ini menggunakan pendekatan yang sama tetapi berbeda untuk membangun tabel numerik dari semua jumlah x yang diperlukan dalam array adengan cara yang dijelaskan di atas, tetapi kemudian membangun tabel string setelahnya. Tabel string dibangun mundur dalam array cmenggunakan metode yang agak aneh unshiftuntuk menambahkan ke array yang ada.

Saat ini pendekatan ini terlihat lebih baik - tetapi hanya dengan 2 byte :-)

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 karakter

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

Fungsinya adalah d:

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

PHP - 137 byte

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

Di sini saya menggunakan trik yang sama dengan grc . Ini adalah versi yang tidak disunat:

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

Berikut kode yang sama dibongkar dan sedikit dibersihkan:

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

Ini didasarkan pada ide yang sama dengan solusi FUZxxl untuk masalah tersebut, yaitu menggunakan formulir eksplisit dan bukan implisit untuk baris. Deklarasi j menetapkannya menjadi 2 ^ (n + 1), dan loop while pertama menghitung k = 3 ^ (n + 1); maka l = 3 ^ (n + 1) -2 ^ (n + 1) adalah lebar total tangga (ini tidak terlalu sulit untuk dibuktikan). Kami kemudian memeriksa semua angka r dari 1 hingga 2 ^ (n + 1) -1; untuk masing-masing, jika itu habis dibagi (tepat) 2 ^ n maka kami berencana untuk mencetak s = 3 ^ n 'X's. Aku disesuaikan untuk memastikan kita mulai dari tempat yang tepat: kita menulis l spasi dan s 'X, lalu baris baru.

CJam, 46 43 41 39 36 35 byte

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

PEMBARUAN menggunakan pendekatan yang berbeda sekarang.

Pendekatan lama:

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

Cukup naif dan panjang, tetapi sesuatu untuk memulai.

Akan menambahkan penjelasan setelah saya golf itu.

Cobalah online di sini

Java, 271 269 ​​byte

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

Bertakuk:

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

Setiap saran dipersilahkan.

2 byte berkat mbomb007

Perl, 62

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

Pertama hitung hasilnya secara iteratif tanpa spasi terkemuka. Kemudian tambahkan mereka sebelum setiap baris sesuai dengan jumlah xkarakter di sisa string.

JavaScript (ES6) 104 106 118

Edit Menghapus fungsi rekursif, daftar '*' untuk setiap baris diperoleh secara iteratif, mengutak-atik bit dan kekuatan 3 (seperti dalam banyak jawaban lainnya)
Di dalam loop, string multiline dibangun dari bawah ke atas, menjaga hitungan berjalan ruang terkemuka untuk ditambahkan di setiap baris

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
}

Coba Pertama dihapus

Fungsi R rekursif membangun array dengan jumlah '*' untuk setiap baris. Misalnya R (2) adalah [1, 3, 1, 9, 1, 3, 1]
larik ini dipindai untuk membangun string multiline dari bawah ke atas, menjaga agar hitungan spasi terdepan ditambahkan di setiap baris

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 

Uji di Firefox / konsol FireBug

F(3)

Keluaran

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

R - 111 karakter

Implementasi langsung, membangun array berulang dan menghancurkannya perlahan.

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

Pemakaian:

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