Gambar Tangga Iblis

46

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

masukkan deskripsi gambar di sini

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.

Sp3000
sumber

Jawaban:

7

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.

FryAmTheEggman
sumber
32

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.

FUZxxl
sumber
Di dalam power loop (,],~3^#@~.)@]bukannya (1,[:,1,"0~3*]) menyimpan 1 byte. Dan jika Anda baik-baik saja dengan !output char u:32+bukannya ' #'{~menyimpan yang lain.
randomra
#\ alih-alih i.@#dan Anda menyusul APL! :)
randomra
Solusi kedua Anda tidak berfungsi karena topi akan diperlukan, tetapi saya menemukan cara lain untuk mengalahkan APL.
FUZxxl
Output baru adalah tangga untuk n-1bukan untuk n.
randomra
@randomra Ah ... itu menyebalkan. Biarkan saya melihat apakah itu bisa diperbaiki.
FUZxxl
26

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.

Jalur eksekusi

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:

Tata letak memori

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.

Timwi
sumber
8
Sekarang ini hanyalah kegilaan kuno.
FUZxxl
21

Python 2, 78

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

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.

grc
sumber
20

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 
marinus
sumber
Itu solusi yang bagus.
FUZxxl
20
Saya suka bahwa penjelasan kode terlihat seperti Tangga Iblis.
Alex A.
Saya menemukan solusi APL yang lebih pendek.
FUZxxl
14

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 n ), 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

$ 
Trauma Digital
sumber
7
Ini sangat keren.
FUZxxl
8

Python 2, 81

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

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).

feersum
sumber
8

Python 2, 74

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

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.

Tidak
sumber
6

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.

Martin Ender
sumber
6

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.
FUZxxl
sumber
4

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
Level River St
sumber
3

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
Level River St
sumber
1
Anda bisa menggantinya for m in(0..n-1)do ... enddengan n.times{|m|...}.
Omar
@ Umar Terima kasih, saya akan mencobanya besok. Anda tidak akan percaya berapa banyak upaya yang diperlukan untuk menjalankannya, karena kesalahan sintaks yang konstan. Saya tidak tahu cara mengakses variabel iterasi n.timesdan saya pasti akan mengingatnya. Ini menghilangkan endjuga! Namun pada kesempatan ini saya bertanya - tanya apakah for m in (1..n)mungkin lebih baik, untuk menghindari (m+1). Apakah ada cara penulisan yang lebih pendek?
Level River St
1
forpanjang terutama karena Anda dipaksa untuk menggunakan end(Anda dapat mengganti dodengan baris baru atau dengan ;). Untuk 1..nbisa kamu gunakan 1.upto(n){|m|...}. Saya suka tampilan (1..n).each{|i|...}tetapi sedikit lebih lama daripada menggunakan upto. Dan perhatikan bahwa iterasi dengan menelepon eachatau uptotidak hanya lebih pendek, itu juga mempertimbangkan Ruby yang lebih idiomatis.
Omar
@Terima kasih lagi 1.upto(n)! Dengan itu dan beberapa tanda kurung yang tidak perlu hilang, saya sudah turun ke 120. Saya pikir di bawah 100 adalah mungkin, saya akan memposting kode revisi nanti.
Level River St
3

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
MtnViewMark
sumber
Semua tanda kurung ini! Apakah benar-benar tidak ada cara untuk mendapatkan lebih sedikit?
FUZxxl
Anda bisa kehilangan satu byte dengan menukar persamaan untuk qdan lakukan q x=xdalam case daftar kosong. Juga, tampaknya tanda kurung di sekitar iterate...[1]tidak perlu.
Zgarb
3

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;
}
Lubang hitam
sumber
3**$i-> terasa seperti PHP 5.6. Anda harus menentukannya. Ini tidak kompatibel dengan hampir setiap instalasi PHP. Untuk menghemat beberapa byte, Anda harus mulai dengan $r=str_repeat;dan di mana Anda memiliki fungsi itu, Anda bisa menggantinya dengan $r, menghemat 2 byte. Juga, $r('x',$v)bisa $r(x,$v)dan itu akan berfungsi dengan baik (perhatikan bahwa saya sudah mengganti nama fungsi dengan variabel). Juga, saya percaya bahwa ++$i<=$ndapat ditulis ulang karena $n>++$imenghemat byte lain.
Ismael Miguel
Inilah fungsi Anda, dengan sedikit trik keren: function f($n){$r=str_repeat;$a=[1];while($n>++$i)$a=array_merge($a,[3**$i],$a);foreach($a as$v){$o=$r(' ',$s).$r(x,$v)."\r$o";$s+=$v;}echo$o;}(alih-alih memiliki baris jelek itu, saya telah menambahkan urutan escape \rdi dalam string yang dikutip ganda, dengan variabel $odi dalamnya. Dengan demikian "\r$o"memiliki byte-count yang sama dengan yang ''.$oada, dengan baris baru dihentikan pada yang terakhir dan menghasilkan hasil yang sama
Ismael Miguel
Sebenarnya, kondisi whileharus $n>$i++untuk pengurangan ini untuk bekerja dengan baik.
Ismael Miguel
@IsmaelMiguel PHP 5.6 adalah versi terakhir dari PHP, saya tidak perlu mengatakan apa-apa lagi. Bukan salah saya jika hampir semua orang menggunakan versi lama, dan jika mayoritas menggunakan versi lama. Terima kasih untuk $r=str_repeattriknya. Saya hanya memikirkan $r='str_repeat';, yang tidak menyimpan byte. Konstanta yang tidak terdefinisi juga merupakan trik yang baik, dilakukan dengan baik;). Baris baru lebih kecil satu byte dari pada menulis \n, jadi saya menyimpannya, tetapi saya telah menggunakan tanda kutip ganda untuk menghindari penggabungan dengan $0. Terima kasih lagi !
Blackhole
Itu hanya akan terlihat bagus untukmu. Jika saya tidak menyadari, 3 ** $isaya akan mengatakan bahwa Anda memiliki sintaks yang mengerikan. Anda dapat mengatasi koreksi itu. Saya katakan tentang ini saja dan bukan [1]karena itu berasal dari PHP5.4, yang cukup 'lama'. 1 tahun yang lalu, saya akan meminta Anda untuk menentukannya. Hari ini, saya meminta Anda untuk hanya menentukan (dalam garis yang sangat pendek) yang menentukan ini. Berbicara tentang kode, Anda masih memiliki ++$i<=$nyang dapat diganti $n>$i++. Saya harus mengubah semua kode Anda ke PHP5.3 untuk mengujinya. Itu menyakitkan. Tapi saya melihat Anda makan 7 byte sejauh ini.
Ismael Miguel
3

C, 165

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

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.

Steven Stadnicki
sumber
tentukan W to; while dan hapus int untuk menyimpan beberapa karakter.
FUZxxl
juga t = l- = s untuk menghemat.
FUZxxl
@ FuZxxl Saya mencoba keduanya, tetapi sementara C masih memungkinkan jenis implisit pada fungsi itu tidak memungkinkan mereka pada deklarasi variabel bahkan dengan bendera 'klasik' (setidaknya pada GCC). Dan saya mencoba #define W; sementara dan sepertinya tidak mempedulikannya, meskipun saya mungkin telah tergelincir dalam definisi.
Steven Stadnicki
hm ... Saya pikir Anda hanya bisa menghilangkan tipe dalam variabel global. Itu tidak membawa Anda terlalu banyak. Anda dapat mencoba menambahkan (*p)()=putchar;di awal untuk memanggil putcharsebagai p. Saya pikir itu harus berhasil.
FUZxxl
2

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

Pengoptimal
sumber
Tampaknya butuh pekerjaan. Tidak berfungsi dengan baik untuk n = 4, 5, 17. Ditampilkan string riffles berformat kiri dari x's di bagian atas. Dengan n = 17 itu membuang kode ke layar dan mengisi bagian bawah dengan x.
DavidC
1
@ DavidVarraher Untuk 4, 5 Saya pikir itu hanya pembungkus baris. Jika Anda menyalin output ke editor teks tanpa garis pembungkus itu terlihat oke untuk saya.
Sp3000
Baik. Saya tahu lihat.
DavidC
2

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

TheNumberOne
sumber
Anda bisa menggunakan b.size()>0bukannya !b.isEmpty()menghemat 2 byte.
mbomb007
1

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.

nutki
sumber
1

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

                                                                *
                                                             ***
                                                            *
                                                   *********
                                                  *
                                               ***
                                              *
                   ***************************
                  *
               ***
              *
     *********
    *
 ***
*
edc65
sumber
1

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
koekenbakker
sumber
Poin bagus, memodifikasi kode saya sehingga dibutuhkan nargumen dari baris perintah
koekenbakker
1
Anda menghemat 8 byte dengan membaca dari STDIN. n=scan().
Alex A.
Anda tidak perlu menyatakan xuntuk menggunakannya sebagai kursor, Anda juga tidak perlu if(n). Juga, jeda baris dihitung sebagai karakter yang saya pikir.
freekvd
Terima kasih, kamu benar tentang x. Namun tidak yakin if(n). Saya menambahkan bagian itu untuk menangani kasus ini n=0. The if(n)kemudian kembali Fdan karenanya mengembalikan tunggal x. Jika saya menghapusnya, n=0memberikan hasil yang tidak diinginkan. Baru di sini, jadi tidak tahu tentang jeda baris. Termasuk sekarang!
koekenbakker
Jika Anda mengatur a=0dan memulai loop x in 0:nitu juga berfungsi untuk n = 0. Maka Anda dapat menghilangkan if(n).
freekvd