ASCII Hilbert Curve

23

Diberikan noutput integer niterasi ke-2 Kurva Hilbert di ASCII menggunakan karakter _dan |.

Berikut adalah 4 iterasi pertama:

n=1
 _ 
| |

n=2
 _   _ 
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _ 
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_ 
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _ 
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_ 
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _ 
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_ 

Klarifikasi

  • Pertanyaan saya mirip dengan Draw Curve Hilbert dan Draw Curve Hilbert menggunakan garis miring .
  • Konversi antara garis bawah ( _) dan bilah vertikal ( |) adalah di u=2*v-1mana ujumlah _s dan vjumlah |s.
  • Untuk menjaga konsistensi dengan posting asli saya, kurva harus dimulai dan diakhiri di bagian bawah.
  • Anda dapat memiliki program atau fungsi lengkap.
  • Output ke stdout (atau yang serupa).
  • Anda dapat memiliki memimpin atau mengekor spasi putih, output hanya perlu berbaris sehingga terlihat seperti contoh.
  • Ini adalah kode-golf sehingga jawaban terpendek dalam byte menang.
Bobas_Pett
sumber
3
Bisakah Anda memasukkan definisi Kurva Hilbert di posting Anda, dan spesifikasi yang tepat untuk bagaimana versi ASCII dibangun?
Loovjo
@Bobas_Pett: Bukan kompleksitas
kolmogorov
@shooqie ada beberapa perdebatan tentang itu di meta
trichoplax
@Loovjo Saya menambahkan di suatu titik tentang panjang garis bawah (_) dan batang vertikal (|) di bawah "Klarifikasi", jika informasi lebih lanjut atau definisi yang ketat masih diperlukan, tolong beri tahu saya.
Bobas_Pett
@shooqie saya menghapus tag
Bobas_Pett

Jawaban:

5

Befunge, 444 368 323 byte

&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

Cobalah online!

Pendekatan khas untuk menggambar Kurva Hilbert adalah mengikuti jalur sebagai serangkaian goresan dan belokan, merender hasilnya menjadi bitmap atau area memori tertentu, dan kemudian menuliskan rendering itu ketika path selesai. Ini tidak layak di Befunge ketika kita hanya memiliki 2000 byte memori untuk bekerja, dan itu termasuk sumber program itu sendiri.

Jadi pendekatan yang kami ambil di sini adalah menghasilkan formula yang memberi tahu kami karakter mana yang akan dihasilkan untuk koordinat x, y. Untuk memahami cara kerja ini, itu paling mudah untuk mengabaikan render ASCII untuk memulai dengan, dan hanya berpikir kurva sebagai terdiri dari karakter kotak: , , , , , dan .

Ketika kita melihat kurva seperti itu, kita dapat segera melihat bahwa tangan kanan adalah cermin yang tepat dari tangan kiri. Karakter di sebelah kanan dapat dengan mudah ditentukan dengan melihat pasangan mereka di sebelah kiri, dan memantulkannya secara horizontal (yaitu kejadian dan ditukar, sebagaimana adanya dan ).

Level 3 Hilbert Curve menunjukkan refleksi melintasi sumbu vertikal

Kemudian melihat sudut kiri bawah, lagi-lagi kita dapat melihat bahwa bagian bawah adalah refleksi dari bagian atas. Jadi karakter di bagian bawah hanya ditentukan dengan melihat pasangan mereka di atas, dan memantulkannya secara vertikal (yaitu kejadian dan ditukar, sebagaimana adanya dan ).

Level 3 Hilbert Curve menunjukkan refleksi melintasi sumbu horizontal di sudut kiri bawah

Setengah dari sudut ini sedikit kurang jelas. Blok tangan kanan dapat diturunkan dari refleksi vertikal blok yang secara diagonal bersebelahan dengannya.

Level 3 Hilbert Curve menunjukkan bagaimana blok kanan atas sudut kiri bawah dapat diturunkan

Dan blok tangan kiri dapat berasal dari refleksi vertikal dari blok di paling kiri atas kurva penuh.

Level 3 Hilbert Curve menunjukkan bagaimana blok kiri atas dari sudut kiri bawah dapat diturunkan

Pada titik ini, yang tersisa adalah sudut kiri atas, yang merupakan salah satu Hilve Curve yang satu lagi lebih rendah. Secara teori, kita seharusnya sekarang hanya perlu mengulangi prosesnya lagi, tetapi ada sedikit tangkapan - pada tingkat ini, bagian kiri dan kanan dari blok itu bukan cermin yang tepat satu sama lain.

Jadi pada apa pun selain tingkat atas, karakter sudut bawah perlu ditangani sebagai kasus khusus, di mana karakter tersebut tercermin , dan karakter tersebut tercermin sebagai .

Level 3 Hilbert Curve menunjukkan bagaimana blok kiri atas dari sudut kiri bawah dapat diturunkan

Tapi selain itu, kita benar-benar bisa mengulangi proses ini secara rekursif. Pada tingkat terakhir, kami membuat hardcode karakter kiri atas , dan karakter di bawahnya sebagai .

Urutan gambar menunjukkan bagaimana bagian kurva yang tersisa diperoleh

Sekarang kita memiliki cara untuk menentukan bentuk kurva pada koordinat x, y, bagaimana kita menerjemahkannya ke rendering ASCII? Ini sebenarnya hanya pemetaan sederhana yang menerjemahkan setiap ubin yang mungkin menjadi dua karakter ASCII.

  • menjadi  _(spasi plus garis bawah)
  • menjadi   (dua spasi)
  • menjadi |_(bilah vertikal plus garis bawah)
  • menjadi (bilah vertikal plus spasi)
  • menjadi (lagi-lagi bilah vertikal plus ruang)
  • menjadi __(dua garis bawah)

Pemetaan ini tidak intuitif pada awalnya, tetapi Anda dapat melihat cara kerjanya saat melihat dua rendering yang sesuai berdampingan.

Level 2 Hilbert Curve diterjemahkan sebagai seni ASCII dan dengan karakter kotak

Dan pada dasarnya itu semua ada untuk itu. Sebenarnya mengimplementasikan algoritme ini di Befunge adalah masalah lain, tetapi saya akan meninggalkan penjelasan itu untuk lain waktu.

James Holderness
sumber
2

C, 267 byte

const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

Cobalah online!

h()menggunakan rekursi untuk menghasilkan goresan kurva hlibert. t()hanya mencetak karakter goresan jika posisi pena psama dengan posisi keluaran saat ini q.

Ini tidak efisien tetapi sederhana.

Jika kurva dimulai di kiri atas, kode dapat dikurangi menjadi 256 byte.

Milo Yip
sumber
Sarankan puts("")bukannya putchar(10)dan "..."+l*8+d*2bukannya &"..."[l*8+d*2]dan n--?h(d+r...-r,n):0bukannyan--&&(h(d+r...-r,n))
ceilingcat