Tentang Seri
Pertama, Anda dapat memperlakukan ini seperti tantangan golf kode lainnya, dan menjawabnya tanpa khawatir tentang seri sama sekali. Namun, ada papan peringkat di semua tantangan. Anda dapat menemukan papan peringkat bersama dengan beberapa informasi lebih lanjut tentang seri di posting pertama .
Meskipun saya memiliki banyak ide untuk seri ini, tantangan di masa depan belum ditetapkan. Jika Anda memiliki saran, beri tahu saya di pos kotak pasir yang relevan .
Lubang 6: Gulung d20
Die yang sangat umum dalam RPG table-top adalah die dua sisi ( icosahedron , umumnya dikenal sebagai d20 ). Adalah tugas Anda untuk melempar dadu seperti itu. Namun, jika Anda baru saja mengembalikan angka acak antara 1 dan 20, itu akan sedikit sepele. Jadi tugas Anda adalah menghasilkan jaring acak untuk cetakan tertentu.
Kami akan menggunakan jaring berikut:
Ini adalah strip segitiga, sehingga dapat dengan mudah direpresentasikan sebagai daftar bilangan bulat. Misal jika Anda diberi input:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Itu akan sesuai dengan mati berikut (fakta menyenangkan: ini adalah jaring yang digunakan oleh Sihir: penghitung hidup Pengumpul / dadu spin-down).
Namun, ini bukan satu-satunya jaring yang mewakili dadu ini. Tergantung pada bagaimana kita membuka gulungan wajah, ada 60 jaring yang berbeda. Inilah dua lagi:
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
Atau secara grafis (saya tidak memutar label wajah untuk kesederhanaan):
Tantangan
Diberikan daftar bilangan bulat yang mewakili cetakan (seperti dijelaskan di atas) dan bilangan bulat N
, keluaran N
secara mandiri, jaring d20 acak seragam yang sesuai dengan cetakan yang diberikan. (Yaitu, masing-masing dari 60 kemungkinan jaring harus memiliki probabilitas yang sama untuk dihasilkan.)
Tentu saja, karena keterbatasan teknis PRNG, keseragaman yang sempurna tidak mungkin terjadi. Untuk tujuan menilai keseragaman kiriman Anda, operasi berikut akan dianggap menghasilkan distribusi seragam sempurna:
- Memperoleh nomor dari PRNG (pada rentang berapa pun), yang didokumentasikan sebagai (kurang-lebih) seragam.
- Memetakan distribusi seragam pada set angka yang lebih besar ke set yang lebih kecil melalui modulo atau multiplikasi (atau operasi lain yang mendistribusikan nilai secara merata). Set yang lebih besar harus mengandung setidaknya 1024 kali lebih banyak nilai yang mungkin dari set yang lebih kecil.
Dengan asumsi ini, algoritma Anda harus menghasilkan distribusi yang seragam sempurna.
Program Anda harus dapat menghasilkan 100 jaring dalam waktu kurang dari satu detik (jadi jangan coba-coba membuat jaring acak sampai ada yang sesuai dengan cetakan yang diberikan di atas).
Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).
Input dan output mungkin dalam format daftar datar yang nyaman, tidak ambigu. Anda dapat mengasumsikan bahwa nilai wajah dari d20 adalah bilangan bulat positif dan berbeda, yang cocok dengan tipe bilangan bulat alami bahasa Anda.
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang. Dan tentu saja, pengiriman terpendek per pengguna juga akan masuk ke papan peringkat keseluruhan seri.
Output Sampel
Untuk input
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
60 kemungkinan jaring (asalkan saya tidak melakukan kesalahan), tanpa urutan tertentu, adalah:
[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]
Untuk i
jaringan lain, cukup ganti setiap kemunculan dengan i
nomor ke-dalam input (di mana i
berbasis 1).
Tantangan Terkait
Papan peringkat
Posting pertama dari seri menghasilkan leaderboard.
Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:
## Language Name, N bytes
di mana N
ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
## Ruby, <s>104</s> <s>101</s> 96 bytes
(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)
sumber
Jawaban:
Ruby, 160 byte (rev B)
17 byte disimpan berkat saran dari Martin Büttner.
Ruby, 177 byte (rev A)
Penjelasan
Dimungkinkan untuk menghasilkan semua orientasi yang mungkin dengan rotasi sekitar satu wajah (3 kali lipat), satu simpul (5 kali lipat) dan dua tepi (2 kali lipat). Tapi bukan sembarang wajah dan ujungnya. Kapak harus memiliki hubungan yang benar dan rotasi harus dilakukan dalam urutan yang benar, atau hal-hal aneh dapat terjadi.
Ini adalah cara saya melakukannya (walaupun saya mengerti Martin melakukannya secara berbeda.)
Semua orientasi tetrahedron dapat dihasilkan oleh kombinasi dari tiga operasi simetri berikut:
a) Rotasi sekitar dua sumbu 2 kali lipat di kanan melalui titik tengah tepi (ini adalah sudut kanan satu sama lain. Jika kita mengalikannya bersama-sama, kita menemukan sumbu 2 kali lipat ketiga melalui sepasang tepi yang tersisa.)
b) Rotasi sekitar sumbu 3 kali lipat diagonal ke sumbu 2 kali lipat, melewati titik dan wajah.
Simetri icosahedron adalah superset dari tetrahedron. Pada gambar di bawah ini dari https://en.wikipedia.org/wiki/Icosahedron , wajah kuning dan wajah merah menentukan dua tetrahedra yang berbeda (atau sebagai alternatif satu oktahedron tunggal), sedangkan tepi yang umum untuk dua wajah biru berada dalam tiga pasangan pada sudut kanan (dan berbaring di wajah kubus.)
Semua orientasi icosahedron dapat dihasilkan oleh operasi simetri yang disebutkan di atas ditambah operasi 5 kali lipat tambahan.
Rotasi sekitar tiga dari empat sumbu yang disebutkan di atas diwakili oleh string sihir antara
''
tanda. Rotasi tentang sumbu 2 kali lipat kedua berbeda, dan dapat dilakukan hanya dengan membalikkan arraya[]
.Tidak tergabung dalam program uji:
Solusi alternatif 131 byte (Tidak valid karena pendekatan biner acak berjalan, hanya memberikan distribusi yang kira-kira benar.)
Ini adalah perebutan (sangat mirip dengan program yang digunakan untuk mengacak kubus rubik.)
Rotasi spesifik yang saya gunakan adalah dua yang paling jelas:
-Sebuah rotasi 120 derajat (sekitar wajah 1 dan 20 per diagram pertama)
-Sebuah rotasi 72 derajat (tentang simpul-simpulnya yang umum hingga 1,2,3,4,5 dan 16,17,18,19,20 per diagram pertama.)
kita membalik koin 99 kali, dan setiap kali kita melakukan salah satu dari dua rotasi ini tergantung apakah itu kepala atau ekor.
Perhatikan bahwa bergantian secara deterministik mengarah ke urutan yang cukup singkat. Misalnya, dengan indra rotasi yang benar, rotasi 180 derajat dapat diproduksi dengan periode hanya 2.
sumber
b.map
tidak bekerja secara langsung, saya harusb.chars.map
membuatnya bekerja (BTW yang tidak bekerja di mesin saya karena saya memiliki Ruby 1.9.3 tetapi bekerja pada Ideone.) Ini adalah penghematan yang adil. Saya tidak berpikir mengubah string ajaib untuk karakter yang tidak dapat dicetak untuk menyimpan surat-64
wasiat akan berfungsi:%w{}
interprets\n
(dan juga spasi) sebagai pemisah antara string dalam array yang dihasilkan. Saya tidak tahu apa yang akan dilakukan dengan karakter ASCII lainnya yang tidak dapat dicetak.Kode mesin IA-32, 118 byte
Hexdump:
Agak panjang, jadi beberapa penjelasan masuk dulu. Aku digunakan hampir algoritma yang sama seperti yang ada jawaban dengan Tingkat Sungai St . Untuk membuat jawaban saya berbeda, saya mengambil permutasi dasar lainnya, yang tidak selalu memiliki makna geometris intuitif, tetapi entah bagaimana lebih nyaman.
Kode pada dasarnya harus menghasilkan permutasi, yang merupakan aplikasi berurutan dari yang berikut:
p3
, diterapkan 0 ... 2 kaliq2
, diterapkan 0 atau 1 kalip5
, diterapkan 0 ... 4 kalip2
, diterapkan 0 atau 1 kaliAda banyak pilihan yang memungkinkan untuk permutasi ini. Salah satunya adalah sebagai berikut:
Pilihan ini lebih baik daripada yang lain karena permutasi di sini memiliki jangka panjang indeks berurutan, yang dapat dikompresi dengan pengkodean run-length - hanya 29 byte untuk 4 permutasi.
Untuk menyederhanakan generasi bilangan acak, saya memilih kekuatan (berapa kali setiap permutasi diterapkan) dalam kisaran 1 ... 30 untuk semuanya. Hal ini menyebabkan banyak pekerjaan tambahan dalam kode, karena misalnya
p3
menjadi permutasi identitas setiap kali dikalikan dengan sendirinya 3 kali. Namun, kode lebih kecil seperti itu, dan selama rentang dibagi 30, output akan memiliki distribusi yang seragam.Juga, kekuatan harus positif sehingga operasi pendekodean run-length dilakukan setidaknya sekali.
Kode ini memiliki 4 loop bersarang; garis besarnya seperti ini:
Saya harap kode semu ini lebih jelas daripada kode inline-assembly di bawah ini.
Beberapa detail implementasi yang menyenangkan:
call
dan selanjutnyapop
untuk mengakses data (permutasi yang dikodekan) yang disimpan dalam kodejecxz
instruksi nyaman memungkinkan saya menggunakan byte nol sebagai terminasi untuk proses decoding run-lengthUntungnya, angka 30 (2 * 3 * 5) hampir merupakan kekuatan 2. Ini memungkinkan saya menggunakan kode pendek untuk menghasilkan angka dalam kisaran 1 ... 30:
Saya menggunakan instruksi "pembagian tujuan umum" (
aam
) untuk memisahkan byte ke dalam bidang bit (panjang 3-bit dan indeks 5-bit); oleh keberuntungan, pada posisi itu dalam kodecl = 0
,, jadi saya mendapat manfaat dari kedua "sisi" darixchg
sumber