Sementara iseng memutar kubus Rubik saya , anak saya memperhatikan bahwa itu terus kembali ke keadaan terpecahkan. Saya cukup yakin dia mengira ini semacam sihir voodoo pada awalnya, tetapi saya menjelaskan bahwa jika Anda terus mengulangi urutan gerakan yang sama, itu akan selalu kembali ke keadaan semula. Akhirnya.
Tentu saja, sebagai anak kecil, ia harus mencobanya sendiri dan memilih urutan "acak" yang menurutnya akan sulit. Dia kehilangan jejak setelah sepuluh pengulangan atau lebih, dan bertanya kepada saya berapa kali dia harus mengulanginya. Tidak tahu urutan yang dia gunakan, saya katakan kepadanya saya tidak tahu, tetapi kita bisa menulis sebuah program untuk mengetahuinya.
Di sinilah Anda masuk. Tentu saja, saya bisa menyiapkan sesuatu, tetapi dia ingin mengetiknya sendiri. Dia bukan pengetik yang sangat cepat, jadi saya perlu program sesingkat mungkin .
Objektif
Diberikan urutan belokan, output berapa kali harus dilakukan untuk mengembalikan kubus ke keadaan semula. Ini adalah kode golf, jadi paling tidak byte menang. Anda dapat menulis suatu program atau fungsi, dan semua standar lain yang biasa berlaku.
Memasukkan
Input adalah urutan gerakan, diambil sebagai string, daftar, atau format lain yang cocok untuk bahasa Anda. Jangan ragu untuk menggunakan pemisah (atau tidak) antara gerakan jika dalam bentuk string.
Ada enam gerakan "dasar" yang harus diperhitungkan, bersama dengan inversinya:
R - Turn the right face clockwise
L - Turn the left face clockwise
U - Turn the up (top) face clockwise
D - Turn the down (bottom) face clockwise
F - Turn the front face clockwise
B - Turn the back face clockwise
Invers diwakili dengan menambahkan tanda prima '
setelah surat. Ini menunjukkan Anda memutar wajah berlawanan arah jarum jam, jadi putar muka F'
depan berlawanan arah jarum jam, dan F F'
akan segera mengembalikannya ke kondisi semula.
Bagi yang berminat, tantangan ini menggunakan seperangkat Notasi Singmaster terbatas . Ruwix memiliki beberapa animasi yang bagus jika Anda ingin melihatnya beraksi.
Keluaran
Output hanyalah jumlah minimum kali urutan input harus dilakukan.
Contohnya
Input Output
FF' -> 1
R -> 4
RUR'U' -> 6
LLUUFFUURRUU -> 12
LUFFRDRBF -> 56
LF -> 105
UFFR'DBBRL' -> 120
FRBL -> 315
Inilah pemecah (yang cukup naif) untuk membandingkan jawaban Anda, yang ditulis dalam Java. Itu juga menerima 2
untuk gerakan ganda (jadi kasus keempat setara dengan L2U2F2U2R2U2
).
import java.util.ArrayList;
import java.util.List;
public class CycleCounter{
public static void main(String[] args){
int[] cube = new int[54];
for(int i=0;i<54;i++)
cube[i] = i;
String test = args.length > 0 ? args[0] : "RUR'U'";
List<Rotation> steps = parse(test);
System.out.println(steps.toString());
int count = 0;
do{
for(Rotation step : steps)
cube = step.getRotated(cube);
count++;
}while(!isSorted(cube));
System.out.println("Cycle length for " + test + " is " + count);
}
static List<Rotation> parse(String in){
List<Rotation> steps = new ArrayList<Rotation>();
for(char c : in.toUpperCase().toCharArray())
switch(c){
case 'R':steps.add(Rotation.R);break;
case 'L':steps.add(Rotation.L);break;
case 'U':steps.add(Rotation.U);break;
case 'D':steps.add(Rotation.D);break;
case 'F':steps.add(Rotation.F);break;
case 'B':steps.add(Rotation.B);break;
case '\'':
steps.add(steps.get(steps.size()-1));
case '2':
steps.add(steps.get(steps.size()-1));
break;
}
return steps;
}
static boolean isSorted(int[] in){for(int i=0;i<in.length-1;i++)if(in[i]>in[i+1])return false;return true;}
enum Rotation{
R(new int[]{-1,-1,42,-1,-1,39,-1,-1,36, -1,-1,2,-1,-1,5,-1,-1,8, 20,23,26,19,-1,25,18,21,24, -1,-1,11,-1,-1,14,-1,-1,17, 35,-1,-1,32,-1,-1,29,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1}),
L(new int[]{9,-1,-1,12,-1,-1,15,-1,-1, 27,-1,-1,30,-1,-1,33,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 44,-1,-1,41,-1,-1,38,-1,-1, -1,-1,6,-1,-1,3,-1,-1,0, 47,50,53,46,-1,52,45,48,51}),
U(new int[]{2,5,8,1,-1,7,0,3,6, 45,46,47,-1,-1,-1,-1,-1,-1, 9,10,11,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 18,19,20,-1,-1,-1,-1,-1,-1, 36,37,38,-1,-1,-1,-1,-1,-1}),
D(new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,24,25,26, -1,-1,-1,-1,-1,-1,42,43,44, 29,32,35,28,-1,34,27,30,33, -1,-1,-1,-1,-1,-1,51,52,53, -1,-1,-1,-1,-1,-1,15,16,17}),
F(new int[]{-1,-1,-1,-1,-1,-1,18,21,24, 11,14,17,10,-1,16,9,12,15, 29,-1,-1,28,-1,-1,27,-1,-1, 47,50,53,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,8,-1,-1,7,-1,-1,6}),
B(new int[]{51,48,45,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,0,-1,-1,1,-1,-1,2, -1,-1,-1,-1,-1,-1,26,23,20, 38,41,44,37,-1,43,36,39,42, 33,-1,-1,34,-1,-1,35,-1,-1});
private final int[] moves;
Rotation(int[] moves){
this.moves = moves;
}
public int[] getRotated(int[] cube){
int[] newCube = new int[54];
for(int i=0;i<54;i++)
if(moves[i]<0)
newCube[i] = cube[i];
else
newCube[moves[i]] = cube[i];
return newCube;
}
}
}
Jawaban:
Pyth,
6663 byteCobalah online: Demonstrasi atau Test Suite . Perhatikan bahwa program ini agak lambat dan kompiler online tidak dapat menghitung jawabannya
RU2D'BD'
. Tapi yakinlah, bahwa itu dapat menghitungnya di laptop saya dalam waktu sekitar 12 detik.Program (tidak sengaja) juga menerima
2
untuk gerakan ganda.Penjelasan Lengkap:
Perebutan Parse:
Pertama saya akan berurusan dengan tanda prima
'
di string input. Saya cukup mengganti ini dengan3
dan run-length decode string ini. Karena format decoding Pyth membutuhkan angka di depan char, saya membalikkan string sebelumnya._r_Xz\'\39
. Jadi setelah itu saya balikkan.Jelaskan keadaan kubus yang dipecahkan:
=Z"UDLRFB
menetapkan string dengan semua 6 gerakan keZ
.Kita bisa menggambarkan keadaan kubus dengan menjelaskan lokasi untuk setiap bagian kubus. Misalnya kita dapat mengatakan bahwa edge, yang seharusnya berada di UL (Atas-Kiri) saat ini di FR (Depan-Kanan). Untuk ini saya perlu untuk menghasilkan semua potongan kubus dipecahkan:
f!s}RTcZ2yZ
.yZ
menghasilkan semua himpunan bagian yang mungkin dari"UDLRFB"
. Ini jelas juga menghasilkan subset"UDLRFB"
dan subset"UD"
. Yang pertama tidak masuk akal, karena tidak ada bagian yang terlihat dari semua 6 sisi, dan yang kedua tidak masuk akal, karena tidak ada bagian tepi, yang terlihat dari atas dan bawah . Karenanya saya menghapus semua himpunan bagian, yang berisi urutan"UD"
,"LR"
atau"FB"
. Ini memberi saya 27 buah berikut:Ini juga termasuk string kosong dan semua enam string 1 huruf. Kita bisa menafsirkannya sebagai bagian di tengah kubus dan 6 bagian tengah. Jelas mereka tidak diperlukan (karena mereka tidak bergerak), tetapi saya akan menyimpannya.
Melakukan beberapa gerakan:
Saya akan melakukan beberapa terjemahan string untuk melakukan gerakan. Untuk memvisualisasikan ide, lihat bagian sudut masuk
URF
. Apa yang terjadi padanya, ketika sayaR
bergerak? Stiker diU
wajah bergerak keB
wajah, stikerF
bergerak keU
wajah dan stiker diR
wajah tetap diR
wajah. Kita dapat mengatakan, bahwa potonganURF
bergerak ke posisi ituBRU
. Pola ini berlaku untuk semua bagian di sisi kanan. Setiap stiker yang ada diF
wajah bergerak keU
wajah saatR
gerakan dilakukan, setiap stiker yang ada diU
wajah bergerak keB
wajah, setiap stiker diB
bergerak keD
dan setiap stiker diD
pindah keF
. Kami dapat mendekode perubahan dariR
langkah sebagaiFUBD
.Kode berikut menghasilkan semua 6 kode yang diperlukan:
Dan kami melakukan perpindahan
H
ke status kubusG
sebagai berikut:Hitung jumlah pengulangan:
Sisanya cukup sepele. Saya hanya melakukan perebutan input ke kubus yang dipecahkan berulang-ulang sampai saya mencapai posisi yang saya kunjungi sebelumnya.
sumber
GAP,
792 783 782749650 BytesIni sepertinya berhasil. Jika itu mengacaukan sesuatu, beri tahu saya.
Terima kasih kepada @Lynn karena menyarankan agar saya menguraikan beberapa gerakan primitif.
Terima kasih kepada @Neil karena menyarankan itu daripada
Inverse(X)
saya gunakanX^3
.Contoh penggunaan:
f("R");
Berikut adalah kode yang tidak ditandai dengan sedikit penjelasan
sumber
45
dengan5
di permutasi Anda, dan menyimpan tiga byte.A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;
lebih pendek dari definisi Anda untukD
(tapi saya tidak bisa mengujinya ...)^-1
untuk invers, BTW?Mathematica,
413401 bytePenjelasan
Cube Sebuah Rubik terdiri dengan 20 bergerak cubies (8 sudut, 12 tepi). Setiap cubie dapat diberi nomor:
sudut :
tepi :
Perhatikan bahwa ketika kubus dipelintir, kubus umumnya tidak berada di posisi awal lagi. Misalnya, ketika
R
selesai, cubie1
bergerak dariUFR
posisi baruUBR
.Dalam notasi seperti itu, belokan 90 derajat dapat digambarkan oleh 8 gerakan kubus. Misalnya,
R
dijelaskan olehKarena setiap cubie memiliki posisi awal yang unik, setiap posisi memiliki cubie awal yang unik. Dengan kata lain, aturan
UFR->UBR
adalah adil1->2
(artinyaR
mengambil cubie pada posisi awal cubie1
ke posisi awal cubie2
). Dengan demikian,R
dapat disederhanakan lebih lanjut menjadi satu siklusUntuk menyelesaikan Kubus Rubik sepenuhnya, kita juga perlu menyelaraskan kubus dengan orientasi awal yang sesuai. Wajah kubus dicat dengan warna berbeda, skema yang sering saya gunakan saat memecahkan kubus adalah
Ketika kami menganalisis orientasi sudut, warna selain kuning atau putih diabaikan, dan kuning dan putih dianggap sebagai warna yang sama.
Misalkan cubie
1
berada pada posisi awalUFR
, segi kuning dapat disejajarkan dengan tiga wajah yang berbeda. Kami menggunakan integer untuk mewakili kasus-kasus ini,Misalkan cubie
1
aktifDFL
, tiga orientasi yang mungkin adalahKetika kami menganalisis orientasi tepi, merah dan oranye diabaikan, dan kuning dan putih diabaikan hanya jika tepi memiliki segi hijau atau biru.
Misalkan cubie
10
berada pada posisi awalUR
, sisi hijau dapat disejajarkan dengan dua wajah yang berbeda. Dua kemungkinan orientasi adalahMisalkan cubie
10
aktifDF
, dua orientasi yang mungkin adalahArray digunakan untuk menyimpan status kubus. Keadaan awal kubus adalah
yang berarti bahwa setiap cubies berada pada posisi awal dengan orientasi yang benar.
Setelah itu
R
, keadaan kubus menjadiyang berarti bahwa cubie
5
sekarang pada posisi1
(UFR
) dengan orientasi2
, cubie1
sekarang pada posisi2
(UBR
) dengan orientasi1
, cubie3
sekarang masih pada posisi3
(UBL
) dengan orientasi0
, dan seterusnya.Uji kasus
sumber
Haskell, 252 byte
Sampel berjalan:
Pengamatan utama di sini adalah lebih mudah untuk memodelkan kubus Rubik sebagai kotak 5 × 5 × 5 poin daripada kotak 3 × 3 × 3 kotak kubus berorientasi. Kubus sudut menjadi kubus 2 × 2 × 2 poin, kubus tepi menjadi kotak 2 × 2 × 1 poin, dan bergerak memutar irisan 5 × 5 × 2 poin.
sumber
c:"'"
denganc:_
menghemat dua byte._
juga cocok dengan daftar kosong.Ruby, 225 byte
Mirip dengan jawaban Anders Kaseorg dan terinspirasi oleh jawaban Jan Dvorak untuk pertanyaan sebelumnya.
Namun tidak seperti jawaban itu, saya tidak perlu 125 kubus. Saya menggunakan kubus rubik dengan 27 kubus, tetapi dimensi persegi panjang. Dalam kondisi terpecahkan, sudut berada
+/-1,+/-4,+/-16
.Saya menghasilkan array 64 cubies, masing-masing dengan pusat dipilih
x=[-1,0,1,2], y=[-4,0,4,8], z=[-16-0,16,32]
. Kubus dengan koordinat 2, 8 dan 32 tidak perlu, tetapi mereka tidak membahayakan, sehingga mereka dibiarkan bermain golf. Fakta bahwa panjang, lebar dan kedalaman kubus berbeda: (1,4,16) berarti mudah untuk mendeteksi apakah mereka berada di tempat yang tepat tetapi dengan orientasi yang salah.Setiap cubie dilacak saat dipindahkan oleh faceturns. Jika koordinat kubus dalam sumbu yang sesuai dengan wajah (dikalikan dengan
e=-1
untuk U, F, R ataue=1
untuk D, B, L) adalah positif, maka akan diputar dengan menukar koordinat dalam 2 sumbu lainnya dan menerapkan tanda yang sesuai diubah ke salah satu koordinat. Ini dikontrol dengan mengalikan dengane*d
.Urutan input dipindai dengan urutan terbalik. Ini tidak ada bedanya, selama rotasi "normal" dilakukan berlawanan arah jarum jam, bukan searah jarum jam. Alasannya adalah agar jika suatu
'
simbol ditemukan, nilai darid
dapat diubah dari 1 ke -1 untuk menyebabkan rotasi dari wajah berikut dalam arah yang berlawanan.Tidak terkurung dalam program uji
sumber
Python 2, 343 byte
Input diambil dari stdin.
Urutan putaran yang dilakukan dilakukan berulang-ulang pada kubus virtual hingga kembali ke keadaan terpecahkan. Keadaan kubus disimpan sebagai vektor orientasi dan vektor permutasi, keduanya dengan panjang 20.
Orientasi agak ditentukan secara sewenang-wenang: sebuah tepi kubus diorientasikan dengan benar jika dapat dipindahkan ke tempatnya tanpa menerapkan putaran seperempat R atau L. Orientasi cubies sudut dianggap relatif terhadap wajah F dan B.
Contoh Penggunaan
Demonstrasi dan Test Suite Online .
sumber
Clojure, 359 byte
Ini mungkin codegolf kedua terpanjang saya. Menyadari bahwa saya bisa menghilangkan angka nol dari vektor
A
untukF
membuat saya sangat senang: DKurang bermain golf:
Ini hanya mengimplementasikan rotasi 3D dari himpunan bagian
5 x 5 x 5
kubus yang dipilih . Awalnya saya akan menggunakan3 x 3 x 3
dan butuh beberapa saat untuk menyadari mengapa saya tidak mendapatkan hasil yang benar. Kasing uji bagus! Beberapa byte tambahan untuk pengodean kepalan"RUR'U'"
sebagai"RURRRUUU"
.sumber
Secara kubik ,
96 byteCobalah online! (Tidak bekerja sampai Dennis memperbarui TIO Cubically interpreter)
Penjelasan:
Bahasa ini akan mendominasi semua tantangan rubiks-cube >: D
sumber
-7
berarti kurangi tujuh tidak menambahkan satu walker getar marahBersih , 255 byte
Berasal secara terpisah dari jawaban Haskell yang hampir identik sebagai jawaban untuk pertanyaan ini yang ditutup sebagai duplikat ketika hampir selesai, jadi saya memposting jawabannya di sini.
Cobalah online!
sumber