Tujuan dari teka-teki ini adalah untuk mengambil setumpuk 52 kartu dan mengocoknya sehingga setiap kartu berada dalam posisi acak.
Diberikan:
- Array,,
deck
dari 52 bilangan bulat berbeda yang mewakili kartu. Ketika Anda mulai,deck
berisi persis satu dari setiap kartu dalam urutan yang tidak diketahui. - Fungsi,,
int rand(min, max)
yang mengembalikan bilangan bulat acak antara intmin
danmax
, inklusif. Anda dapat mengasumsikan bahwa fungsi ini benar-benar acak. - Suatu fungsi,
void swap(x, y)
yang menukar dua kartu di dek. Jika Anda meneleponswap(x, y)
, kartu di posisix
dany
akan berpindah tempat.
Kapan:
- Program panggilan
shuffle()
(ataushuffle(deck)
ataudeck.shuffle()
atau Namun implementasi Anda suka untuk menjalankan),
Kemudian:
deck
harus berisi tepat satu dari setiap kartu dalam urutan acak sempurna.
Tangkapan:
Anda tidak dapat mendeklarasikan variabel apa pun. Panggil swap
dan rand
sebanyak yang Anda suka, tetapi Anda tidak dapat mendeklarasikan variabel Anda sendiri. Ini termasuk for
penghitung lingkaran - bahkan yang tersirat seperti dalam a foreach
.
Klarifikasi:
- Anda dapat mengubah detail kecil agar sesuai dengan bahasa pilihan Anda. Misalnya, Anda dapat menulis
swap
untuk mengganti dua bilangan bulat dengan referensi. Perubahan seharusnya membuat ini berfungsi dengan bahasa Anda, bukan untuk membuat teka-teki lebih mudah. deck
bisa menjadi variabel global, atau Anda bisa menganggapnya sebagai parameter.- Anda dapat melakukan apa saja yang Anda inginkan
deck
, tetapi Anda tidak dapat mengubah panjangnya. - Kartu Anda dapat diberi nomor 0-51, 1-52, atau apa pun yang Anda suka.
- Anda dapat menulis ini dalam bahasa apa pun, tetapi jangan curang dengan
shuffle
fungsi bawaan bahasa Anda . - Ya, Anda bisa menulis baris yang sama 52 kali. Tidak ada yang akan terkesan.
- Waktu eksekusi tidak penting, tetapi keacakan yang sebenarnya tidak penting.
- Ini bukan kode golf, tapi jangan ragu untuk memperkecil / mengaburkan kode Anda.
Sunting: Kode dan visualizer Boilerplate
Jika Anda menggunakan .NET atau JavaScript, berikut ini beberapa kode uji yang mungkin berguna bagi Anda:
JavaScript:
- Visualizer JavaScript cepat-dan-kotor, dengan sumber CoffeeScript: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
- Versi runnable (cukup tempelkan pada
shuffle()
fungsi Anda ): http://jsfiddle.net/4zxjmy42/
C #:
- Visualisasi ASP.NET dengan C # codebehind: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
- Stub hanya dengan metode utilitas
swap
danrand
: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41
Kode ini mengurutkan dan mengocok deck beberapa ribu kali dan melakukan beberapa pengujian kewarasan dasar: Untuk setiap shuffle, kode ini memverifikasi bahwa ada tepat 52 kartu di dalam deck tanpa pengulangan. Kemudian visualizer memplot frekuensi setiap kartu berakhir di setiap tempat di geladak, menampilkan peta panas skala abu-abu.
Output visualizer akan terlihat seperti salju tanpa pola yang jelas. Jelas itu tidak dapat membuktikan keacakan yang sebenarnya, tetapi ini adalah cara yang cepat dan mudah untuk melakukan pemeriksaan spot. Saya sarankan menggunakannya atau sesuatu seperti itu, karena kesalahan tertentu dalam algoritma pengocokan menyebabkan pola yang sangat dikenali dalam output. Berikut adalah contoh dari output dari dua implementasi, satu dengan kelemahan umum:
Versi cacat sebagian mengocok dek, jadi mungkin terlihat baik jika Anda memeriksa array dengan tangan. Visualizer memudahkan untuk melihat suatu pola.
sumber
deck
itu sendiri.swap
Anda suka, asalkan memenuhi tujuan dasarnya. Bagian dari alasan sayaswap
memberikan sesuatu adalah agar orang-orang dapat memperlakukannya sebagai 'sihir' dan berkonsentrasi pada masalah utama tanpa harus khawatir itu berfungsi dalam bahasa pilihan mereka. Anda dapat melakukannya atau menulis sendiriswap
, terserah Anda.Jawaban:
JavaScript
Saya percaya ini adalah bentuk solusi yang dimaksudkan, saya menggunakan kartu pada posisi 0 untuk melacak kemajuan, hanya mengocok kartu yang telah digunakan sebagai penghitung, ini mencapai standar 52! permutasi dengan distribusi sama sempurna. Prosedurnya rumit oleh XOR swap yang tidak memungkinkan elemen ditukar dengan sendirinya.
Sunting: Saya membuat penyortiran yang menyortir setiap elemen ke tempatnya tepat sebelum digunakan, sehingga memungkinkan ini bekerja dengan array yang tidak disortir. Saya juga menjatuhkan panggilan rekursif yang mendukung loop sementara.
sumber
Haskell
Berikut ini adalah implementasi bebas poin. Tidak ada variabel, parameter formal, atau rekursi eksplisit. Aku digunakan lambdabot 's
@pl
( 'sia-sia') refactoring fitur cukup sedikit.Inilah prosedur pengujian saya untuk memastikan angka-angka itu terdistribusi secara seragam:
Berikut adalah algoritma aslinya:
sumber
((.) .) . (. (++))
dan ini(((.) . (,)) .)
adalah favorit saya. Wow, lambdabot. Cuma wow.J
Mengabaikan dek itu variabel, ada yang jelas ...
Tentu saja, jika Anda benar-benar menginginkan suatu fungsi, ada ini, yang akan berfungsi bahkan jika Anda lupa menghapus pelawak (atau mencoba mengocok sesuatu selain kartu).
Yang seperti itu...
Ini mungkin di luar maksud pertanyaan, yang akan mengimplementasikan shuffle diri Anda dari rand (
?
). Saya mungkin melakukannya nanti ketika saya tidak seharusnya bekerja.Penjelasan
Penjelasan tentang
52 ? 52
:x ? y
adalah x item unik acak dari y.Penjelasan
{~ (# ? #)
lebih sulit karena garpu dan kait . Pada dasarnya, ini sama denganshuffle =: 3 : '((# y) ? (# y)) { y'
, yang memiliki satu argumen implisit (y
).# y
memberi panjang yx { y
adalah item y dalam indeks x, atau (dalam hal ini) item dalam indeks dalam x.Lihat J Vocabulary untuk perincian operator, meskipun sintaks dan semantiknya agak rumit karena pemrograman peringkat dan diam-diam.
sumber
{52?⍵}
adalah fungsi anonim yang mengambil 52 item acak dari argumennya, yang di sini akan menjadi daftar 52 bilangan bulat)Python
sumber
[1:]
artinya? Apakah itu berulang pada sub-arraydeck
?a, b = b, a
triknya.Menggunakan representasi faktoradik
Dalam representasi faktoradik permutasi, elemen i mengambil nilai dari 0 hingga Ni. Jadi permutasi acak hanya
rand(0,i)
untuk setiap Ni.Dalam J:
di mana
? x
adalahrand(0,x-1)
dan|.>:i.52
adalah52 51 ... 1
Lalu, jika
a
nilai ith factoradic, kita lakukan swap:swap(deck[i], deck[i+a])
. Daftar pasangan yang akan ditukar adalah:Swap kami akan menggunakan karya seperti ini:
Ini tidak benar-benar "dengan referensi" tetapi tidak ada fungsi nyata di J.
Kami akan menggunakan panjang dek (
#deck
) untuk menghindari penggunaan konstanta.Program lengkap dalam J:
sumber
C #
Ini jawaban saya sendiri berdasarkan algoritma Fisher-Yates . Seharusnya memberi Anda shuffle sempurna jika generator angka acak Anda cukup baik.
Versi bahasa Inggris:
deck[0]
dengan yang ada dideck[v]
, di manav
nilai nominal kartu tersebut beradadeck[0]
. Ulangi sampaiv == 0
. Ini akan mengurutkan sebagian deck, tetapi itu tidak masalah. Anda sekarang tahu bahwa Kartu 0 ada di bagian depan geladak, yang berarti Anda dapat mencuri ruang itu dalam array dan menggunakannya sebagai penghitung lingkaran. Ini adalah kunci "cheat" untuk masalah variabel lokal.i
dengan yang dirand(i, 51)
. Perhatikan bahwa Anda perlurand(i, 51)
, BUKANrand(1, 51)
. Itu tidak akan memastikan bahwa setiap kartu diacak.deck[0]
kembali ke 0. Sekarang seluruh dek dikocok kecuali untuk kartu pertama, jadi tukardeck[0]
dengandeck[rand(0, 51)]
dan Anda selesai.Versi C #:
Versi Javascript:
... di mana
swap(a, b)
bertukardeck[a]
dengandeck[b]
.sumber
Ruby, satu baris
Apakah ini dianggap curang? Itu harus acak seperti yang didapat.
(
rand
Metode Ruby hanya membutuhkan satu argumen dan kemudian menghasilkan angka n sehingga 0 <= angka <argumen.)Selain itu - mirip dengan solusi Perl sogart, tetapi sejauh yang saya tahu itu tidak menderita masalah:
Sort_by Ruby berbeda dari sort - Ruby pertama-tama menghasilkan daftar nilai untuk mengurutkan array, dan hanya kemudian mengurutkannya. Lebih cepat ketika mahal untuk mengetahui properti yang kami sortir, agak lambat dalam semua kasus lainnya. Ini juga berguna dalam kode golf: P
sumber
deck[0..51]
tidak mengesampingkan aturan "no variable" dengan menggunakan fitur bahasa. Itu adil, saya hanya berpikir itu kehilangan beberapa tantangan. :) Saya tidak tahu Ruby; dapatkah Anda menjelaskan(0..51).map{deck.delete_at(rand deck.length)}
bagian itu? Apakah itu menghapus kartudeck
?deck
dan menambahkannya ke daftar internal hasil yangmap
terakumulasi. Kemudian ketika ada yang tersisa dideck
dalammap
hasil akan disalin ke dalamdeck
. Pada dasarnya ada sementara, tetapi ini adalah fitur bahasa daripada variabel eksplisit :)deck.sort_by!{rand}
lebih pendek.JavaScript
CATATAN: Solusi ini secara teknis tidak benar karena menggunakan parameter kedua
i
,, dalam panggilan keshuffle
, yang dianggap sebagai variabel eksternal.Telepon dengan
shuffle(deck,52)
Contoh kerja yang lengkap (harus memodifikasi
swap
sedikit karena tidak ada pass-by-referensi ints di JavaScript):sumber
shuffle
sebagai variabel, tapi saya tidak menentukan itu jadi +1. Penggunaan rekursi yang bagus juga.deck[rand(0,i-1)]
alih-alihdeck[rand(0,i-2)]
. Juga bertukar semua carai=0
daripada berhentii=1
. Apakah itu membantu?C ++
Hindari bertukar elemen dengan diri mereka sendiri, jadi harus memanggil dua kali untuk menjadi acak.
sumber
swap(deck[rand(1, 51)], (deck[0] - 51) / 100);
Bagaimanaswap
tahu di mana harus meletakkan nilai kedua? Anda juga kehilangan a)
.deck[0]
, tetapi tidak dengan cara yang Anda miliki.D
sumber
Solusi Perl lainnya, yang benar-benar menghasilkan keluaran yang terdistribusi secara merata:
Solusi ini menggunakan Perl
rand
, yang mengembalikan angka acak x dalam kisaran 0 ≤ x <1. Ia menambahkan bilangan acak ke setiap bilangan bulat dalam input, mengurutkan angka sesuai dengan bagian fraksinya, dan akhirnya menghilangkan bagian fraksional itu lagi. .(Saya percaya penggunaan variabel khusus
$_
,$a
dan$b
berada dalam semangat tantangan, karena itu adalah bagaimana perl melewati input kemap
dansort
, dan mereka tidak digunakan untuk tujuan lain dalam kode. Dalam kasus apa pun, saya percaya mereka sebenarnya alias dengan nilai input, bukan salinan independen. Ini sebenarnya bukan in-place shuffle; keduanyamap
dansort
membuat salinan input pada stack.)sumber
Jawa
Saya terkejut tidak ada yang menyatakan yang jelas: (Saya akan menganggap swap (x, x) tidak melakukan apa-apa.
OKE, OKE, bisa lebih pendek:
sumber
Bahan tertawaan
Apa yang sebenarnya Anda minta adalah permutasi acak dari daftar bilangan bulat?
r@
akan memberi kita semua permutasi, dan kami hanya memilih yang acak.Karena kita membutuhkan keacakan yang sebenarnya, sesuatu yang Burlesque tidak mampu lakukan karena Burlesque tidak memiliki fungsi I / O Anda perlu menyediakan beberapa sumber keacakan melalui STDIN.
Itu mungkin sesuatu yang akan saya perbaiki dalam versi yang lebih baru (yaitu menghasilkan seed acak saat startup dan mendorongnya ke tumpukan sekunder atau sesuatu seperti itu, tetapi Burlesque Interpreter sendiri tidak memiliki I / O).
sumber
Javascript
Saya tidak yakin apakah itu "curang" tetapi solusi saya menggunakan array lokal asli dari argumen fungsi. Saya menyertakan fungsi buatan saya sendiri
rand()
swap()
danfilldeck()
. Dari catatan yang menarik, ini harus bekerja dengan setumpuk ukuran apa pun.sumber
Tcl , 32 byte
Menyalahgunakan
time
Fungsi yang berfungsi untuk mengukur berapa banyak waktu yang dihabiskan skrip berjalan, tetapi juga dapat berfungsi sebagai mekanisme pengulangan tanpa mendeklarasikan variabel apa pun.Cobalah online!
sumber
perl - ini bukan shuffle yang tepat seperti dijelaskan dalam komentar!
Saya pikir saya tidak menggunakan apa pun sebagai swap dll. Apakah itu diperlukan sebagai bagian dari masalah?
sumber
JavaScript 4 baris
Jawaban asli yang tidak cukup acak. Swap tidak dijamin untuk menyentuh setiap item di geladak.
sumber
shuffle
kode Anda sedikit agar sesuai denganswap
implementasi saya , tetapi ini dia kata demi kata: jsfiddle.net/m7km4u6g