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 ( W
putih, G
hijau dll.)
Telah ditunjukkan bahwa ada (~ quintillion) permutasi yang berbeda yang dimiliki oleh Rubik's Cube.
Tugas Anda adalah mengambil bilangan bulat antara dan 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.
- , tetapi algoritma yang Anda gunakan seharusnya tidak.
- 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 kode-golf 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)
sumber
Jawaban:
Arang ,
334297 byteCobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:
Masukkan bilangan bulat ke dalam variabel
q
.Bagi
q
dengan 3⁷, masukkan sisanyae
. Kemudian, mengingate
sebagai angka dalam basis 3, suffix digit kee
sehingga digitnya (dalam basis 3) menambahkan hingga kelipatan 3. Ini memungkinkane
untuk menentukan rotasi sudut.Bagi
q
dengan 8 !, masukkan sisanyaz
. (8! Disimpan sementarad
untuk menyimpan byte.) Ini memungkinkanz
untuk menentukan posisi sudut.Bagi
q
dengan 2¹¹, masukkan sisanyah
. Kemudian, dengan mempertimbangkanh
sebagai angka pada basis 2, sufikskan sebuah digith
sehingga digitnya (pada basis 2) bertambah hingga kelipatan 2. Hal ini memungkinkanh
untuk menentukan garis tepi.Ulangi representasi string pusat.
Lompat ke posisi masing-masing pusat dan cetak.
Melacak paritas posisi sudut dalam variabel
w
.Buat array posisi sudut.
Buat array warna sudut.
Loop dua kali, sekali untuk sudut, sekali untuk tepi, selanjutnya disebut "kubus".
Ulangi susunan warna kubus.
Ekstrak posisi kubus berikutnya dari
z
, memperbarui paritas dalamw
. Gunakan paritas ini untuk yang terakhir tetapi satu sisi. Ini memastikan bahwa jumlah paritas tepi dan sudut rata.Cetak kubus pada posisi itu, sesuaikan untuk rotasi berikutnya atau flip yang sesuai.
Hapus rotasi atau flip dari
e
.Buat array posisi tepi. Ini akan digunakan kedua kalinya melalui loop.
Buat array warna tepi.
Timpa variabel sudut
z
dane
dengan variabel tepi yang sesuaiq
danh
sehingga tepi di permutasi dan dibalik selama pass kedua loop.sumber
Ruby ,
570408 byteCobalah online!
Versi asli, dengan array angka ajaib, bukan string ajaib
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 - 1
dan yang kedua adalah orientasi potongan-potongan di kisaran 0 ke2**11 * 3*7 - 1
. Output dalam keadaan terpecahkan adalah string berikut: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
. Inputg
dibagi dengan angka-angka12..1
dengan modulus digunakan untuk mengambil dan menghapus tepi daria
dan tempatkanz
. Setelah ini dilakukan, hanya sudut-sudut yang tersisaa
, jadig
dibagi dengan angka-angka8..1
dengan modulus yang digunakan untuk menghilangkan suduta
dan menempatkannya diz
.Karena tidak ada info yang cukup untuk menentukan urutan dua sudut terakhir, nilai
g
akan telah dibagi menjadi nol pada saat mencapai mereka, sehingga mereka akan selalu ditambahkan kez
dalam 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
0
atau1
di 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 a2
atau4
ke depan / belakang atau a3
atau5
ke 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%2048
dijumlahkan dan modulus digunakan untuk menentukan orientasi tepi pertama.h
dikalikan 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 lainnyaj
. Untuk sudut terakhir (di manai/19
=1
) nilaij%3
ditambahkan keh
(yang akan dikurangi menjadi nol) dan ini menentukan orientasi sudut terakhir.String
b
datang dengan inisialisasi dengan teks untuk pusat wajah.h
dibagi2
dua belas kali kemudian3
delapan kali, dengan modulos yang digunakan untuk menentukan orientasi potongan. Dalam setiap kasus, angka dalamz
dikonversi 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
b
ke dalam format yang lebih dapat dibaca manusia dalams
menggunakan angka ajaib dalam tabel indeks.sumber