43 trilyun permutasi

16

Kami dapat mewakili Rubik's Cube sebagai jaring sebagai berikut (ketika dipecahkan):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Setiap huruf mewakili warna yang sesuai ( Wputih, Ghijau dll.)

Telah ditunjukkan bahwa ada 43,252,003,274,489,856,000 (~ 43 quintillion) permutasi yang berbeda yang dimiliki oleh Rubik's Cube.

Tugas Anda adalah mengambil bilangan bulat antara 1 dan 43,252,003,274,489,856,000 dan output yang sesuai permutasi, dengan cara yang ditunjukkan di atas. Anda dapat memilih bagaimana permutasi disusun, tetapi algoritma yang Anda gunakan harus ditunjukkan untuk menghasilkan permutasi yang unik, dan benar, untuk setiap input yang mungkin.

Aturan permutasi tidak valid

Diambil dari halaman ini

Untuk memulainya, pusat dari setiap wajah 3x3 harus tetap sama, karena alun-alun di Rubik's Cube tidak dapat diputar. Seluruh kubus dapat diputar, mengubah di mana wajah muncul, tetapi ini tidak mempengaruhi jaring kubus.

Jika kita mengatakan setiap permutasi memiliki paritas, berdasarkan paritas jumlah swap untuk mencapai permutasi itu, kita dapat mengatakan

  • Setiap potongan sudut memiliki tiga kemungkinan orientasi. Ia dapat diorientasikan dengan benar (0), searah jarum jam (1) atau berlawanan arah jarum jam (2). Jumlah orientasi sudut selalu tetap habis dibagi 3

  • Setiap rotasi legal pada Rubik's Cube selalu membalik jumlah tepi yang genap sehingga tidak mungkin hanya ada satu bagian yang salah.

  • Mempertimbangkan permutasi dari semua sudut dan tepi, paritas keseluruhan harus genap yang berarti bahwa setiap langkah hukum selalu melakukan yang setara dengan jumlah swap yang genap (mengabaikan orientasi)

Misalnya, tiga jaring berikut ini adalah keluaran yang tidak valid:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

Aturan

  • Anda harus membuktikan, bagaimanapun keinginan Anda, bahwa algoritma tersebut valid. Anda tidak perlu menghitung setiap permutasi tunggal, selama Anda membuktikan validitas algoritma Anda.
  • 143,252,003,274,489,856,000
    • 253-1253-1 , tetapi algoritma yang Anda gunakan seharusnya tidak.
    • 27,946,105,037,114,827,095
  • Anda harus memasukkan semacam bukti validitas dalam jawaban Anda. Bukti ini dapat membuktikan validitas dalam metode bukti yang diterima, kecuali untuk menyebutkan semua kemungkinan.
  • Anda dapat memilih untuk menggunakan metode input alternatif jika diinginkan, asalkan:
    • Input dibatasi
    • Setiap input sesuai dengan output unik
    • Anda dengan jelas menjelaskan format input dan bagaimana itu sesuai dengan setiap output
  • Anda dapat mengubah karakter yang digunakan untuk menggunakan 6 karakter ASCII yang berbeda, antara 33 ( !) dan 126 ( ~), alih-alihWGRBOY
  • Anda dapat menampilkan dengan cara apa pun yang Anda inginkan, asalkan itu membentuk representasi yang jelas dari sebuah kubus di mana semua 6 wajah dapat ditampilkan, termasuk jaring kubus yang valid, string berjajar tunggal atau rendering 3D. Jika Anda tidak yakin tentang format tertentu, jangan ragu untuk bertanya di komentar.

Ini adalah sehingga kode terpendek, dalam byte, dalam setiap bahasa menang.

Contoh output yang valid

   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)
caird coinheringaahing
sumber
Pada contoh ketiga yang tidak valid, bukan hanya sudutnya dalam konfigurasi yang tidak valid, sudut r / y / o adalah sudut yang tidak mungkin karena r dan o saling berseberangan
fəˈnɛtɪk
Memperbaiki contoh ketiga yang tidak valid (CC @ fəˈnɛtɪk)
Jonathan Allan
Masalah yang sama juga ada dalam contoh kedua yang tidak valid tetapi saya tidak menyadarinya. Itu kurang penting di sana karena warnanya tetap kacau
fəˈnɛtɪk
(Sebuah1,Sebuah2,Sebuah3,Sebuah4)Sebuah18!Sebuah237Sebuah312!/2Sebuah4211
1
@Shaggy Ya, satu baris string baik
caird coinheringaahing

Jawaban:

13

Arang , 334 297 byte

Nθ≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θF⪪”B"↷:μêKO″KW#})”³«J⌕α§ι⁰I§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δF²«Fδ«≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυFLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»≧÷Lκε»≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Nθ

Masukkan bilangan bulat ke dalam variabel q.

≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ

Bagi qdengan 3⁷, masukkan sisanya e. Kemudian, mengingat esebagai angka dalam basis 3, suffix digit ke esehingga digitnya (dalam basis 3) menambahkan hingga kelipatan 3. Ini memungkinkan euntuk menentukan rotasi sudut.

≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

Bagi qdengan 8 !, masukkan sisanya z. (8! Disimpan sementara duntuk menyimpan byte.) Ini memungkinkan zuntuk menentukan posisi sudut.

≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θ

Bagi qdengan 2¹¹, masukkan sisanya h. Kemudian, dengan mempertimbangkan hsebagai angka pada basis 2, sufikskan sebuah digit hsehingga digitnya (pada basis 2) bertambah hingga kelipatan 2. Hal ini memungkinkan huntuk menentukan garis tepi.

F⪪”B"↷:μêKO″KW#})”³

Ulangi representasi string pusat.

«J⌕α§ι⁰I§ι¹§ι²»

Lompat ke posisi masing-masing pusat dan cetak.

≔⁰ω

Melacak paritas posisi sudut dalam variabel w.

≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ

Buat array posisi sudut.

≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

Buat array warna sudut.

F²«

Loop dua kali, sekali untuk sudut, sekali untuk tepi, selanjutnya disebut "kubus".

Fδ«

Ulangi susunan warna kubus.

≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

Ekstrak posisi kubus berikutnya dari z, memperbarui paritas dalam w. Gunakan paritas ini untuk yang terakhir tetapi satu sisi. Ini memastikan bahwa jumlah paritas tepi dan sudut rata.

FLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»

Cetak kubus pada posisi itu, sesuaikan untuk rotasi berikutnya atau flip yang sesuai.

≧÷Lκε»

Hapus rotasi atau flip dari e.

≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ

Buat array posisi tepi. Ini akan digunakan kedua kalinya melalui loop.

≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

Buat array warna tepi.

≔θζ≔ηε

Timpa variabel sudut zdan edengan variabel tepi yang sesuai qdan hsehingga tepi di permutasi dan dibalik selama pass kedua loop.

Neil
sumber
Beri tahu saya sendiri: Jika sesuatu yang golf di Charcoal adalah 330 byte, jangan coba-coba dalam PHP!
Night2
@ Night2 Sedihnya 334 sekarang, karena perbaikan bug (perhitungan paritas salah).
Neil
8

Ruby , 570 408 byte

->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

Cobalah online!

Versi asli, dengan array angka ajaib, bukan string ajaib

->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48, 
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

Cobalah online!

Fungsi anonim yang dalam bentuk saat ini mengambil input dari dua bilangan bulat, yang tampaknya diizinkan: "Anda dapat memilih metode input alternatif." Yang pertama adalah permutasi dalam kisaran 0 ke 12!*8!/2 - 1dan yang kedua adalah orientasi potongan-potongan di kisaran 0 ke 2**11 * 3*7 - 1. Output dalam keadaan terpecahkan adalah string berikut:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Golf lebih lanjut

Ada sekitar 10 karakter yang harus disimpan dengan menyesuaikan format output ke bentuk berikut. Tapi ini akan mengurangi keterbacaan, jadi saya tidak akan melakukannya saat ini

      #########
      #########
      #########
#########
#########
#########

Penjelasan

Permutasi

Secara internal, keadaan terpecahkan diwakili oleh serangkaian angka oktal dalam array a. Input gdibagi dengan angka-angka 12..1dengan modulus digunakan untuk mengambil dan menghapus tepi dari adan tempatkan z. Setelah ini dilakukan, hanya sudut-sudut yang tersisa a, jadi gdibagi dengan angka-angka 8..1dengan modulus yang digunakan untuk menghilangkan sudut adan menempatkannya di z.

Karena tidak ada info yang cukup untuk menentukan urutan dua sudut terakhir, nilai gakan telah dibagi menjadi nol pada saat mencapai mereka, sehingga mereka akan selalu ditambahkan ke zdalam urutan asli di sana. Pemeriksaan kemudian dilakukan untuk menentukan apakah permutasi keseluruhan genap atau ganjil, dan jika perlu dua sudut terakhir ditukar untuk membuat permutasi merata.

Orientasi

Ada berbagai cara untuk memutuskan apakah sudut atau tepian berada dalam orientasi yang benar jika tidak berada di lokasi yang terpecahkan. Untuk keperluan jawaban ini, sudut dianggap dalam orientasi yang benar jika itu menunjukkan 0atau 1di bagian atas atau bawah. Oleh karena itu memutar muka atas atau bawah tidak mengubah orientasi sudut. Memutar wajah-wajah lain memang mengubah orientasi, tetapi sedemikian rupa sehingga jumlah paritas keseluruhan tetap tidak berubah. Tepi dianggap dalam orientasi yang benar jika mereka menunjukkan a 2atau 4ke depan / belakang atau a 3atau 5ke kiri / kanan. Ini berarti bahwa rotasi bagian atas atau bawah oleh seperempat putaran membalik keempat sisi tetapi rotasi dari sisi lain meninggalkan status flip tidak berubah.

Input berisi informasi eksplisit untuk semua kecuali tepi pertama dan sudut terakhir. 11 bit paling tidak penting h%2048dijumlahkan dan modulus digunakan untuk menentukan orientasi tepi pertama. hdikalikan dengan 2 dengan menambahkannya sendiri dan nilai untuk orientasi tepi pertama ditambahkan sebagai bit paling tidak signifikan. Orientasi sudut terakhir ditemukan dengan secara progresif mengurangi orientasi sudut lainnya j. Untuk sudut terakhir (di mana i/19= 1) nilai j%3ditambahkan ke h(yang akan dikurangi menjadi nol) dan ini menentukan orientasi sudut terakhir.

String bdatang dengan inisialisasi dengan teks untuk pusat wajah. hdibagi 2dua belas kali kemudian 3delapan kali, dengan modulos yang digunakan untuk menentukan orientasi potongan. Dalam setiap kasus, angka dalam zdikonversi menjadi string dengan jumlah digit yang sesuai (2 atau 3) dan string kemudian digandakan. Ini memungkinkan rotasi digit yang benar seperti yang ditemukan oleh modulo untuk diekstraksi dari string dengan mengindeks dan ditambahkan keb

Tampilan

Akhirnya, stiker mentah disalin dari bke dalam format yang lebih dapat dibaca manusia dalam smenggunakan angka ajaib dalam tabel indeks.

Level River St
sumber