Pengantar:
Kubus Rubik 3x3x3 memiliki kemungkinan permutasi, yaitu sekitar 43 triliun . Anda mungkin pernah mendengar tentang nomor ini sebelumnya, tetapi bagaimana cara menghitungnya?
Kubus Rubik 3x3x3 memiliki enam sisi, masing-masing dengan sembilan stiker. Melihat pada potongan (eksternal) alih-alih stiker, kami memiliki enam bagian tengah; potongan delapan sudut; dan dua belas potongan tepi. Karena pusat tidak dapat dipindahkan, kami dapat mengabaikannya dalam perhitungan. Adapun sudut dan tepi:
- Ada( ) cara untuk mengatur delapan sudut. Setiap sudut memiliki tiga kemungkinan orientasi, walaupun hanya tujuh (dari delapan) yang dapat diorientasikan secara independen; orientasi sudut delapan / final tergantung pada tujuh sebelumnya, diberikan ( ) kemungkinan.
- Ada ( ) cara untuk mengatur dua belas tepi. Dibelah dua dariadalah karena ujung harus selalu dalam permutasi genap persis ketika sudut-sudutnya. Sebelas tepi dapat dibalik secara independen, dengan flip kedua belas / tepi akhir tergantung pada sebelas sebelumnya, diberikan ( ) kemungkinan.
Menyatukan ini, kami memiliki rumus berikut:
Sumber: Wikipedia - Permutasi Kubus Rubik
Meskipun ini mungkin sudah terlihat cukup kompleks, itu masih agak lurus ke depan untuk 3x3x3 Cube. Bahkan untuk kubus rumusnya sedikit berbeda; ini adalah rumus untuk Cube 4x4x4 misalnya:
Yaitu sekitar 7,40 quattuordecillion pada skala pendek .
Dan untuk NxNxN Cubes yang lebih besar (yaitu Rekor Dunia 33x33x33 saat ini) formula akan diperpanjang sedikit. Untuk tidak membuat pengantar ini terlalu lama, saya meletakkan tautan ini di sini, di mana permutasi dari 4x4x4 Cube dan beberapa NxNxN Cubes berukuran lain dijelaskan dengan rumus yang dihasilkan:
Anda mungkin bertanya-tanya sekarang: apakah ada rumus umum berdasarkan untuk setiap x x Cube? Pasti ada. Berikut adalah tiga algoritma yang sangat berbeda, semuanya memberikan hasil yang sama persis berdasarkan :
1: Formula Chris Hardwick:
2: Formula trigonometri Christopher Mowla:
3: Formula dasar Christopher Mowla:
di mana adalah .
Sumber: Cubers-reddit - Rumus Penghitungan Matematika dari Jumlah Posisi, Nomor Tuhan, dll.
Tantangan:
Pilih dan terapkan salah satu dari tiga rumus ini (atau turunan Anda sendiri), yang diberi bilangan bulat input dalam kisaran , menghasilkan hasil yang benar.
Aturan tantangan:
- Anda bebas menggunakan formula lain di samping ketiganya, tetapi perlu diingat bahwa ketiganya terbukti benar. Jika Anda menggunakan formula lain, silakan tambahkan tautan dari mana Anda mendapatkannya (atau jika Anda datang sendiri, tambahkan penjelasan mendalam). Dan saya akan memeriksa semua bilangan bulat dalam kisaran jika outputnya benar. Mungkin inspirasi dapat ditemukan di oeis untuk urutan ini: A075152 .
- Jika bahasa Anda secara otomatis menampilkan keluaran ilmiah (yaitu alih-alih angka setelah rumus 4x4x4) ini diperbolehkan. Tetapi tolong tambahkan kode tambahan untuk jawaban Anda untuk mengonversi pembulatan ilmiah ini menjadi keluaran yang tepat sehingga hasilnya dapat diverifikasi, karena kesalahan pembulatan karena presisi titik mengambang selama pelaksanaan rumus dalam kode Anda tidak diperbolehkan - hasil yang sebenarnya harus tepat.
- Program / fungsi Anda harus benar untuk setidaknya input dalam kisaran (walaupun, karena sudah menghasilkan angka yang sangat besar, lebih besar mungkin akan bekerja juga jika Anda dapat menampilkan ini satu dengan benar).
- Anda tidak diizinkan untuk mengulang semua permutasi yang mungkin dengan penghitung, karena itu tidak akan pernah menghasilkan apa pun dalam jumlah waktu yang wajar. Hanya penerapan formula (salah satu dari tiga yang disediakan, turunan dari salah satu dari itu, atau formula yang sama sekali baru), atau metode lain yang akan memberikan hasil yang benar dalam jumlah waktu yang wajar (tanpa tentu saja hard-coding tentu saja ) Diperbolehkan. Saya berpikir tentang menambahkan waktu terbatas untuk memberlakukan ini, tapi saya pribadi menentang waktu terbatas dalam kombinasi dengan kode-golf , jadi saya tidak akan melakukannya. Tetap saja, pastikan program Anda memberikan jawaban, dan jika terlalu lambat untuk TIO karena alasan tertentu, tambahkan beberapa tangkapan layar dengan output dari mesin lokal Anda sebagai verifikasi.
Aturan umum:
- Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa yang bukan kode. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa saja'. - Aturan standar berlaku untuk jawaban Anda dengan aturan I / O default , sehingga Anda diizinkan untuk menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program penuh. Panggilanmu.
- Celah default tidak diperbolehkan.
- Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda (yaitu TIO ).
- Juga, menambahkan penjelasan untuk jawaban Anda sangat dianjurkan.
Kasus uji:
Di sini kasus uji untuk dalam kisaran (jangan ragu untuk menggunakan tautan WolframAlpha di atas untuk kasus uji yang lebih besar):
n=2
3674160
n=3
43252003274489856000
n=4
7401196841564901869874093974498574336000000000
n=5
282870942277741856536180333107150328293127731985672134721536000000000000000
n=6
157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000
n=7
19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000
n=8
35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000
n=9
14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000
n=10
82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000
CATATAN: Karena ini adalah tantangan kode-golf , pada dasarnya bermuara pada: mengimplementasikan salah satu dari tiga rumus ini (atau turunan / metode Anda sendiri yang masih menghasilkan hasil yang benar) sesingkat mungkin.
sumber
floor
Jawaban:
Bahasa Wolfram (Mathematica) , 59 byte
Cobalah online!
menggunakan algoritma Herbert Kociemba yang ditemukan di halaman OEIS
di sini adalah rumus rekursif:
a(1)=1; a(2)=7!*3^6; a(3)=8!*3^7*12!*2^10; a(n)=a(n-2)*24^6*(24!/24^6)^(n-2)
6 byte disimpan oleh @Peter Taylor
satu byte lagi disimpan oleh @Expired Data
sumber
f@1
, sehingga Anda dapat menghemat 6 byte. Tentunya Anda juga ingin menyesuaikan kerangka pengujian untuk digunakanRange[2,10]
.kode mesin x86, 119 byte
Hexdump:
Fungsi menerima jumlah
n
dalamecx
, dan pointer ke string untuk mengisiedx
(yaitufastcall
konvensi).Sebelum saya menunjukkan kode sumber, beberapa penjelasan tentang bagaimana melakukan hal itu. Ini menggunakan rumus rekursif, yang saya tulis dengan cara berikut:
Jadi semua kode yang harus dilakukan adalah perkalian dengan angka kecil. Jumlahnya berada di kisaran 6 ... 36, yang cukup kecil untuk diwakili dalam bitmap 32-bit. Saya sebenarnya tidak menyimpan bit yang mewakili perkalian dengan 6 - ini memungkinkan saya mengatur kode dalam satu
do-while
lingkaran, dimulai dengan perkalian tanpa syarat dengan 6.Angka-angka besar diwakili menggunakan bentuk desimal - setiap byte adalah nilai dalam rentang 0 ... 9, mulai dari MSB.
Perkalian dilakukan dari LSB ke MSB; itu mengasumsikan bahwa jumlah digit akan bertambah 2 untuk setiap perkalian. Setelah melakukan perkalian dengan faktor kecil seperti 6, jumlah digit dapat tumbuh hanya 1. Jadi, jika MSB = 0, itu akan memindahkan seluruh hasil antara yang tersisa. Dapat benar-benar terjadi bahwa jumlah digit tidak tumbuh sama sekali, dan kemudian MSB akan tetap 0, tetapi masalah ini akan memperbaiki dirinya sendiri ketika kode berlanjut ke faktor yang lebih besar.
Karena kode multiplikasi besar, saya tidak ingin memasukkannya dua kali. Saya juga tidak ingin memindahkannya ke suatu fungsi, karena kode mesin untuk memanggil suatu fungsi besar. Jadi saya mengatur ulang loop luar sedemikian rupa sehingga kode pengali hanya diperlukan sekali.
Kode C:
Membongkar:
Waktu berjalan untuk n = 100 adalah sekitar 4 detik, dan hasilnya adalah angka dengan 38416 digit:
23491019577617 (banyak digit di sini) ... (banyak nol di sini) 000000000000000000
sumber
05AB1E , 38 byte
Upaya awal.
Menggunakan Formula Chris Hardwick .
Akan berusaha bermain golf lebih jauh dan menjelaskan kapan saya punya waktu.
Cobalah online!
sumber
Julia 1.0 ,
8376 byteCobalah online!
Menggunakan Formula Chris Hardwick. Mengambil input sebagai bilangan bulat besar.
Terima kasih kepada H.PWiz untuk -7 byte
sumber
~=n->factorial(big(n))
->~n=prod(big,1:n)
dan(24576*~12)^(n%2)
->^(24576*~12,n%2)
~=n->
bukan~n=
?Python 2 , 72 byte
Cobalah online!
Disimpan 4 byte dengan menyalin
n*(n-2)/4
dari Neil .sumber
Bahasa Wolfram (Mathematica) , 67 byte
Menggunakan Formula Chris Hardwick.
Cobalah online!
sumber
JavaScript (Node.js) , 81 byte
Formula rekursif Herbert Kociemba. Mengambil BigInt sebagai input.
Cobalah online!
JavaScript (Node.js) ,
102 9896 byteFormula Chris Hardwick. Mengambil BigInt sebagai input.
Cobalah online!
sumber
JavaScript (Node.js) ,
777573 byteCobalah online! Berdasarkan formula Christopher Mowla. Mengambil BigInt sebagai input. Uji harness tanpa malu-malu dicuri dari @Arnauld
0xb88d4641131f0n
adalah3246670537110000n
dalam desimal. Penjelasan: Saya mulai dengan eksponen utama terakhir dan menyederhanakannyan*(n-2n)/4n
(ini adalah pembagian bilangan bulat, jadi saya tidak perlu penyesuaian untuk angka ganjil). Saya kemudian memeriksa bilangan prima lainnya untuk melihat apakah eksponen mereka terkait dengan nilai ini (yang akan saya sebut sebagaio
), dan menemukan bahwa mereka mengejar mode, jika saya mengizinkan penggunaan paritasn
(yang saya sebut sebagaip
). Rumus untuk eksponen adalah sebagai berikut:Kekuatan kemudian dapat dikelompokkan berdasarkan eksponen jadi misalnya
p
adalah eksponen11*7*5**2*3**3*2**14
.sumber
Racket ,
151141 byte-7 byte berkat fede s.!
Cobalah online!
Jawaban terpanjang menggunakan Formula Chris Hardwick :)
sumber
expt
panggilan:(λ(n[e expt])...(e ...)...)
.Python 2 , 122 byte
Cobalah online!
Menggunakan metode rekursif Herbert Kociemba.
-2 byte terima kasih kepada Herman L
sumber
3**6
dengan 729 dan2**10
dengan1024
TIOJelly ,
3938 byteSaya merasa seperti melewatkan beberapa golf, tapi ...
Tautan monadik yang menerapkan Formula Chris Hardwick.
Cobalah online! Atau lihat test-suite (
n=[1..33]
).sumber
CJam (47 byte)
Demo online
j
sumber
Jelly , 43 byte
Cobalah online!
sumber
Ikon ,
125110 byteCobalah online!
sumber
C (gcc) -lgmp, 279 byte
Cobalah online!
sumber
N--*--N/4
alih-alih(N*N-2*N)/4
dan hapusN-=2
dan#define s mpz_init_set_str
Perl 6 , 85 byte
Cobalah online!
sumber
Haskell ,
868574 byte-1 byte disimpan berkat H.PWiz
-11 byte yang disimpan berkat Max Yekhlakov
Cobalah online!
sumber
24576
lebih pendek dari2^13*3
Python 2 , 92 byte
Cobalah online!
sumber
Sekam ,
514844 byte-4 byte terima kasih kepada H.PWiz
Cobalah online!
Ini adalah Formula Chris Hardwick. Juga, ini adalah program kulit pertama saya, jadi tips apa pun akan sangat dihargai.
sumber
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24*1024Π12
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24576Π12
C ++,
187 185 180 176 195 (ada bug) 193175 bytes (dengan bantuan dari ceiling cat)Ini menggunakan pembungkus GMP C ++ (GNU multi-precision library), dan formula yang digunakan oleh @ J42161217 ( https://codegolf.stackexchange.com/a/183381/55953 ).
Gunakan
g++ -g rubix.cpp -lgmp -lgmpxx
untuk mengkompilasi dan menautkanungolfed, dengan kode uji
https://tio.run/##PZAxb4MwEIV3foWVDrETqBpARMImWZqha7t0iFQZ4xC3xrg2tJERf73UIVXfcE937zvpdEzrqGZsmu6EYrKvOKkbfbncn3dBb4WqgSsa7d6YpNZiBzR0gIYOlGhwgBUb/H0WksMyihBbFRQb3vVGAYZHB4xnFRr@Rqoo4n2SbdNN9pD7Jtk7uNCvafVEn7fvjx@LMItRbqCKYrTSME7D7OoeOpivl4Mp@eeMhFcAj//3AiJa2xlOm13QUKEgCoYAeJ1aA4XqgChiDARJUl/XazRnXrar8py1fUeIIGR57JaE@AUECLllXFUSB2Mw/bCTpLWdIjm/5ua/
sumber
n=10
test case, jadi saya dapat memverifikasi bahwa itu berfungsi? Saya kira tidak ada cara untuk membuat ini bekerja pada C ++ (clang) atau C ++ (gcc) TIO karena pustaka yang digunakan?TI-BASIC,
6362 byte , (tidak bersaing)Ekspresi yang menerima input sebagai integer aktif
Ans
. Penerapan formula Chris Hardwick. Tidak bersaing karena perangkat keras yang dijalankannya hanya akan menyimpan hingga 16 desimal, jadi jawabannya tidak akan pernah 100% akurat.Penjelasan:
sumber