Tulis sebuah program untuk menggambar diagram 2-D dari sebuah simpul berdasarkan pada struktur simpul tersebut. Simpul persis seperti apa itu: simpul yang diikat. Dalam matematika, diagram simpul menunjukkan di mana seutas tali menyilang atau membentuk simpul. Beberapa contoh diagram simpul ditunjukkan di bawah ini:
Ada jeda di garis di mana tali menyilang.
Input: input yang menggambarkan simpul adalah array bilangan bulat. Sebuah simpul mana tali menyilang sendiri n kali dapat direpresentasikan sebagai array dari n bilangan bulat, masing-masing dengan nilai dalam rentang [0, n-1]. Mari kita sebut array ini K .
Untuk mendapatkan array yang menggambarkan simpul, beri nomor setiap segmen 0 hingga n-1. Segmen 0 harus mengarah ke segmen 1, yang harus mengarah ke segmen 2, yang harus mengarah ke segmen 3, dan seterusnya sampai segmen n-1 berputar kembali dan mengarah ke segmen 0. Segmen berakhir ketika segmen lain dari tali melintasinya ( diwakili oleh sebuah break di baris dalam diagram). Mari kita ambil simpul yang paling sederhana - simpul trefoil. Setelah kami menomori segmen, segmen 0 berakhir ketika segmen 2 melintasinya; segmen 1 berakhir ketika segmen 0 melintasinya; dan segmen 2 berakhir ketika segmen 1 melewatinya. Dengan demikian, array yang menggambarkan simpul adalah [2, 0, 1]. Secara umum, segmen x dimulai ketika segmen x-1 mod n tinggalkan, dan berakhir di mana segmen K [x] melintasinya.
Gambar di bawah ini menunjukkan diagram simpul, dengan segmen berlabel dan array yang sesuai yang menggambarkan simpul tersebut.
Tiga diagram teratas adalah simpul sejati, sedangkan tiga diagram bawah adalah simpul tali yang melintang di atas dirinya sendiri tetapi sebenarnya tidak diikat (tetapi masih memiliki kode yang sesuai).
Tugas Anda adalah menulis fungsi yang mengambil array bilangan bulat K (Anda bisa menyebutnya sesuatu yang berbeda) yang menggambarkan simpul (atau simpul tali yang sebenarnya tidak diikat), dan yang menghasilkan diagram simpul yang sesuai, seperti dijelaskan di atas contoh. Jika Anda bisa, berikan versi kode Anda atau penjelasan yang tidak diklik, dan berikan juga sampel hasil kode Anda. Simpul yang sama sering dapat direpresentasikan dalam berbagai cara yang berbeda, tetapi jika diagram simpul yang dihasilkan fungsi Anda mendapat input sebagai salah satu kemungkinan representasi, solusi Anda valid.
Ini adalah kode-golf, jadi kode terpendek dalam byte menang. Garis yang mewakili tali dapat memiliki ketebalan 1 piksel, namun di bawah dan perlintasan-lebih harus dapat dibedakan dengan jelas (ukuran putus tali harus lebih besar dari ketebalan tali dengan setidaknya satu piksel di kedua sisi) .
Saya akan memilih jawaban yang bergantung pada kemampuan teori simpul bawaan, tetapi jawaban yang dipilih pada akhirnya tidak bisa mengandalkan kemampuan teori simpul bawaan.
Semua yang saya tahu tentang notasi saya: Saya percaya bahwa ada urutan nilai yang tampaknya tidak sesuai dengan simpul atau tidak. Misalnya, urutan [2, 3, 4, 0, 1] tampaknya tidak mungkin untuk digambar.
Selain itu, anggaplah Anda mengambil persimpangan dan, mulai dari persimpangan itu, ikuti jalan tali dalam satu arah dan beri label setiap persimpangan yang tidak berlabel yang Anda temui dengan nilai integral yang lebih besar secara berturut-turut. Untuk simpul bolak-balik, ada algoritma sederhana untuk mengubah notasi saya menjadi pelabelan seperti itu, dan untuk simpul bolak-balik itu sepele untuk mengubah pelabelan ini menjadi Kode Gauss:
template<size_t n> array<int, 2*n> LabelAlternatingKnot(array<int, n> end_at)
{
array<int, n> end_of;
for(int i=0;i<n;++i) end_of[end_at[i]] = i;
array<int, 2*n> p;
for(int& i : p) i = -1;
int unique = 0;
for(int i=0;i<n;i++)
{
if(p[2*i] < 0)
{
p[2*i] = unique;
p[2*end_of[i] + 1] = unique;
++unique;
}
if(p[2*i+1] < 0)
{
p[2*i+1] = unique;
p[2*end_at[i]] = unique;
++unique;
}
}
return p;
}
template<size_t n> auto GetGaussCode(array<int, n> end_at)
{
auto crossings = LabelAlternatingKnot(end_at);
for(int& i : crossings) ++i;
for(int i=1;i<2*n;i+=2) crossings[i] = -crossings[i];
return crossings;
}
sumber
KnotData
di Mathematica ...: '(Knot
builtin! Contoh penggunaan:<< Units`; Convert[Knot, Mile/Hour]
hasil1.1507794480235425 Mile/Hour
. (Saya pikir ini lucu terlepas dari apakah itu benar atau salah; tetapi sebenarnya benar.)Jawaban:
GNU Prolog,
622634668 byte di halaman kode 850Pembaruan : Versi sebelumnya dari program kadang-kadang membuat penyeberangan yang sangat ketat sehingga tidak akan ditampilkan dengan benar, yang melanggar spesifikasi. Saya telah menambahkan beberapa kode tambahan untuk mencegahnya.
Pembaruan : Rupanya aturan PPCG memerlukan kode tambahan untuk membuat program keluar dan mengembalikan status persis seperti di awal. Hal ini membuat program agak lama dan tidak menambahkan minat algoritmik untuknya, tetapi demi kepentingan kepatuhan terhadap peraturan, saya telah mengubahnya.
Program golf
Menggunakan GNU Prolog karena memiliki sintaks solver pemecah yang sedikit lebih pendek dari sintaks aritmatika Prolog portabel, menghemat beberapa byte.
Algoritma
Ini adalah salah satu masalah di mana sulit untuk mengetahui bagaimana memulainya. Tidaklah jelas bagaimana cara mengetahui bentuk simpul dari notasi yang diberikan, karena itu tidak memberi tahu Anda apakah Anda harus menekuk garis ke kiri atau ke kanan di lokasi tertentu (dan dengan demikian, notasi mungkin ambigu). Solusi saya adalah, secara efektif, menggunakan siaga golf lama: menulis sebuah program yang sangat tidak efisien yang menghasilkan semua output yang mungkin dan kemudian melihat apakah cocok dengan input. (Algoritma yang digunakan di sini sedikit lebih efisien, karena Prolog dapat membuang jalan buntu sesekali, tetapi tidak memiliki informasi yang cukup untuk meningkatkan kompleksitas komputasi.)
Outputnya adalah melalui seni terminal. GNU Prolog tampaknya menginginkan set karakter byte tunggal yang konsisten dengan ASCII, tetapi tidak peduli yang mana yang digunakan (karena memperlakukan karakter dengan bit set tinggi sebagai buram). Akibatnya, saya menggunakan IBM850, yang didukung secara luas dan memiliki karakter menggambar garis yang kami butuhkan.
Keluaran
Program mencari semua gambar simpul yang mungkin, sesuai dengan ukuran kotak pembatasnya, kemudian keluar ketika menemukan yang pertama. Seperti apa hasilnya
m([0]).
:Ini membutuhkan waktu 290,528 detik untuk berjalan di komputer saya; program ini tidak terlalu efisien. Saya membiarkannya berjalan selama dua jam
m([0,1])
, dan berakhir dengan ini:Versi tidak dikoleksi dengan komentar
Highlighter sintaksis Stack Exchange tampaknya memiliki simbol komentar yang salah untuk Prolog, jadi alih-alih
%
komentar (yang sebenarnya digunakan Prolog), penjelasan ini menggunakan% #
komentar (yang tentu saja setara karena dimulai dengan%
, tetapi sorot dengan benar).sumber