Ada varian dari masalah N-ratu yang terkenal yang melibatkan ratu dan ksatria dan dikatakan "jauh lebih sulit" 1 . Pernyataan masalah adalah sebagai berikut:
Anda harus menempatkan jumlah ksatria yang sama que dan ratu ♛ di papan catur sehingga tidak ada bagian yang menyerang bagian lainnya. Berapa jumlah maksimum potongan yang bisa Anda letakkan di papan tulis, dan berapa banyak cara berbeda yang bisa Anda lakukan?
Dalam tantangan kode-golf ini , Anda akan diberikan input n antara 3 dan 32 (dengan cara yang paling cocok untuk bahasa Anda). Untuk n yang diberikan , mungkin ada nol atau lebih solusi untuk masalah di atas. Jika tidak ada solusi, Anda harus mengeluarkan / mengembalikan apa-apa ( nihil , string kosong , false , ...). Jika tidak, Anda harus memberikan dua hasil:
- Papan solusi (lihat di bawah) untuk ukuran dan di mana tidak mungkin untuk menambahkan ratu atau bidak catur ksatria tanpa ada bagian yang sedang diserang. Harus ada jumlah ratu dan ksatria yang sama .
- Sumber program yang akan dijalankan yang tidak menerima input dan memberikan (i) solusi lain (atau tidak sama sekali ) untuk ukuran yang sama n , dalam format yang sama, serta (ii) program lain untuk solusi berikutnya (dan seterusnya). ...).
Perhatikan bahwa:
- Urutan program tidak boleh mengembalikan papan yang sama dua kali, harus mencakup semua solusi yang mungkin untuk masalah ukuran n dan akhirnya harus diakhiri (tidak menghasilkan output).
- Anda bisa mengembalikan dua nilai, mengembalikan satu dan mencetak yang lain, atau mencetak dua nilai kembali.
- Namun , jika Anda mencetak papan dan program berikutnya, papan tersebut tidak boleh dianggap sebagai bagian dari program berikutnya (saya akan merekomendasikan mencetak papan dalam komentar, atau menggunakan keluaran standar dan aliran kesalahan).
- Program-as-a-return-value harus berupa string, bukan penutupan.
Format papan
- Papan adalah ukuran persegi n .
- Sel papan bisa kosong, ratu atau ksatria.
- Anda harus memilih nilai yang berbeda untuk setiap jenis sel (yaitu Anda dapat menggunakan simbol selain Q, N saat mencetak papan).
- Jika Anda kembali papan non-string, itu harus menjadi memerintahkan koleksi n 2 nilai dewan (misalnya matriks, vektor atau daftar di baris / kolom-besar pesanan, ...).
Jika Anda mencetak papan, Anda dapat mencetaknya dengan kuadrat, atau sebagai garis. Misalnya, papan solusi ukuran 4 dapat dicetak sebagai berikut (spasi tidak diperlukan; simbol sesuai kebijaksanaan Anda):
Q - - - - - - - - - - - - - N -
Jika Anda merasa demikian, Anda juga dapat menampilkan:
♛ · · · · · · · · · · · · · ♞ ·
... tapi ini sudah cukup:
Q-------------N-
Tidak masalah jika Anda beralih melalui sel dalam urutan baris-mayor atau kolom-mayor, karena ada solusi simetris. Sebagai contoh, solusi untuk n = 4 adalah:
Q------N-------- Q----------N---- Q------------N-- Q-------------N- -Q----------N--- -Q------------N- -Q-------------N --Q---------N--- --Q----------N-- --Q------------N ---QN----------- ---Q----N------- ---Q---------N-- ---Q----------N- ---NQ----------- ----Q------N---- ----Q----------N N------Q-------- -------QN------- -------Q----N--- ---N----Q------- -------NQ------- --------Q------N N----------Q---- ----N------Q---- -----------QN--- -N----------Q--- --N---------Q--- -------N----Q--- -----------NQ--- N------------Q-- --N----------Q-- ---N---------Q-- N-------------Q- -N------------Q- ---N----------Q- -N-------------Q --N------------Q ----N----------Q --------N------Q
Anda juga dapat melihat solusi untuk n = 5 sebagai matriks ; papan berisi #
, q
dan n
simbol, yang merupakan sel kosong dari berbagai jenis (lihat jawaban saya di bawah). Saya menghitung 2836 papan untuk n = 6 , seperti pada jawaban Sleafar (saya memperkenalkan bug ketika mengurangi jumlah byte, tetapi sudah diperbaiki sekarang).
Terima kasih banyak kepada Sleafar karena menemukan bukan hanya satu tetapi dua bug dalam kode saya.
Skor
Kode terpendek dalam byte menang.
Kami mengukur ukuran program pertama, yang menerima n .
1 . Ratu dan Ksatria , oleh Roger KW Hui (waspadalah! Mengandung solusi)
-------------------------N--------Q-
tidak valid karena lebih banyak bagian dapat ditambahkan :)Q--------N---------------N--------Q-
.Jawaban:
Groovy, 515 byte
Pengujian
Berikan n sebagai argumen baris perintah:
Baris pertama dari output selalu merupakan solusi sebagai komentar (0 = kosong, 1 = ratu, 2 = ksatria), diikuti oleh kode di baris kedua:
Script berikut dapat digunakan untuk pengujian otomatis (berikan n sebagai argumen lagi):
Karena saya mencoba membuat solusi sekecil mungkin, ini sangat lambat (lihat di bawah untuk detailnya). Saya hanya menguji n = 4 dengan versi ini untuk melihat apakah quineification berfungsi.
Hasil
n = 4: 40 solusi ( format yang dikonversi )
n = 5: 172 solusi ( format yang dikonversi )
n = 6: 2836 solusi ( format yang dikonversi )
Algoritma
Ini adalah versi solusi non-quine yang sedikit tidak disunat:
Quineification
Saya menggunakan pendekatan yang sangat sederhana di sini untuk menjaga ukuran kode tetap rendah.
Variabel X memegang indeks solusi untuk dicetak berikutnya. Y memegang salinan modifikasi dari algoritma di atas, yang digunakan untuk menghitung semua solusi dan kemudian memilih hanya satu dari mereka, yang merupakan alasan untuk itu sangat lambat. Keuntungan dari solusi ini adalah, tidak memerlukan banyak kode tambahan. Kode yang disimpan dalam Y dijalankan dengan bantuan kelas Eval (quine yang sebenarnya tidak diperlukan).
Kode yang dimodifikasi mencetak solusi yang ditunjukkan oleh X , menambah X dan menambahkan salinannya sendiri:
Saya juga mencoba untuk mengeluarkan semua solusi sebagai kode untuk langkah kedua, tetapi untuk n = 6 itu menghasilkan terlalu banyak kode untuk ditangani oleh Groovy.
sumber
Common Lisp, 737
jawaban sendiri
Contoh
Tempel di atas dalam REPL, yang mengembalikan objek fungsi:
Sebut saja (bintang terikat dengan nilai yang dikembalikan terakhir):
Ini mencetak yang berikut ini ke output standar:
Juga, nilai yang dikembalikan oleh fungsi ini adalah:
... yang merupakan array literal. Angka 5 mewakili ratu, 6 untuk ksatria dan yang lainnya berarti sel kosong, kecuali ada lebih banyak informasi yang disimpan secara internal. Jika kami menyalin-tempel fungsi yang dikembalikan ke repl, kami memperoleh fungsi baru.
Dan kita dapat menyebutnya, tanpa argumen:
Panggilan ini mengembalikan solusi baru
#(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0)
dan sumber fungsi lain (tidak ditampilkan di sini). Jika fungsi asli atau yang terakhir dibuat tidak menemukan solusi, tidak ada yang dicetak dan tidak ada yang dikembalikan.Nilai internal
Saya dulu menghasilkan terlalu sedikit solusi. Sekarang, saya menyebarkan sel apa yang aman untuk seorang ratu dan untuk seorang ksatria, secara mandiri. Sebagai contoh, ini adalah output untuk n = 5 dengan pencetakan cantik:
Ketika kami menempatkan ratu
Q
, posisi yang merupakan ksatria-pindah dari ratu ini masih aman untuk ratu dan dilambangkanq
. Demikian juga, ksatria yang hanya bisa dijangkau oleh ratu aman untuk ksatria lain. Nilai bitwise dan -ed untuk mewakili gerakan yang mungkin dan beberapa sel dapat dicapai dengan tidak ada bagian.Lebih tepatnya, di sini adalah urutan papan yang mengarah ke solusi berikut (dari kiri ke kanan), di mana sel bebas secara bertahap dibatasi dengan nilai yang berbeda:
Pendekatan non-quine
Versi komentar yang tidak disatukan
Duplikat dan bug
Solusi pertama saya menghasilkan solusi duplikat. Untuk mengatasinya, saya memperkenalkan dua counter untuk ratu dan ksatria. Penghitung untuk ratu (resp. Ksatria) melacak posisi pertama di papan tempat seorang ratu (resp. Ksatria) ada: Saya menambahkan ratu (resp. Seorang ksatria) hanya pada posisi yang mengikuti posisi minimal itu.
Metode itu mencegah saya mengunjungi kembali solusi yang sudah ditemukan di iterasi sebelumnya, karena saya beralih dengan posisi ratu (resp. Knight) yang semakin meningkat.
Namun, Sleafar memperhatikan bahwa ada solusi yang mungkin ada ruang untuk ratu dan ksatria, yang bertentangan dengan aturan. Untuk sementara saya pikir saya harus kembali ke pencarian normal dan menyimpan semua solusi yang dikenal untuk mencegah duplikat, yang terasa terlalu mahal (baik dalam hal byte dan penggunaan memori).
Alih-alih, inilah yang saya lakukan sekarang: ketika papan solusi potensial ditemukan, saya mencoba menambahkan satu ratu dan satu ksatria, tanpa memperhitungkan penghitung (yaitu untuk semua sel di papan). Jika ini memungkinkan, maka board saat ini adalah duplikat dari yang sebelumnya, dan saya menolak solusinya.
Tes
Quine-ification
Saya punya ide berbeda untuk membuat quines berturut-turut. Yang paling mudah mungkin untuk menghasilkan semua solusi pertama sebagai daftar string dan menulis quines berurutan yang muncul dari daftar itu di setiap generasi. Namun ini tampaknya tidak lebih pendek dari pendekatan saat ini. Atau, saya mencoba untuk menulis ulang kode rekursif dengan tumpukan kustom dan membuang semua variabel keadaan setiap kali saya menemukan solusi; tujuannya adalah bahwa langkah selanjutnya dapat diproses sebagai kelanjutan dari langkah saat ini. Mungkin ini akan lebih cocok untuk bahasa berbasis stack. Yang saat ini cukup sederhana dan mengandalkan variabel Common Lisp reader, yang selalu menyenangkan untuk digunakan.
sumber