Bersepeda dengan Rubik's

43

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 2untuk 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;
        }
    }
}
Geobit
sumber
"Searah jarum jam" berarti "searah jarum jam saat Anda menghadapinya" Saya kira?
msh210
@ msh210 Benar.
Geobits
7
Pada titik pedantry, saya pikir Anda harus membuatnya secara eksplisit bahwa Anda ingin jumlah terkecil yang mencukupi. Kalau tidak, saya hanya bisa menampilkan ukuran kelompok dan mengutip teorema Lagrange ...
Peter Taylor
2
@PeterTaylor Pedantry diterima.
Geobits
4
Saya dapat menawarkan hadiah 500 poin untuk solusi di Shuffle. Belum yakin.
lirtosiast

Jawaban:

16

Pyth, 66 63 byte

l.uum.rW}Hdd@_sm_B.iFP.>c3Zk3xZHG_r_Xz\'\39Nf!s}RTcZ2y=Z"UDLRFB

Cobalah 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 2untuk gerakan ganda.

Penjelasan Lengkap:

Perebutan Parse:

Pertama saya akan berurusan dengan tanda prima 'di string input. Saya cukup mengganti ini dengan 3dan 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"UDLRFBmenetapkan string dengan semua 6 gerakan ke Z.

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. yZmenghasilkan 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:

'', 'U', 'D', 'L', 'R', 'F', 'B', 'UL', 'UR', 'UF', 'UB', 'DL', 'DR', 'DF', 'DB', 
'LF', 'LB', 'RF', 'RB', 'ULF', 'ULB', 'URF', 'URB', 'DLF', 'DLB', 'DRF', 'DRB'

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 saya Rbergerak? Stiker di Uwajah bergerak ke Bwajah, stiker Fbergerak ke Uwajah dan stiker di Rwajah tetap di Rwajah. Kita dapat mengatakan, bahwa potongan URFbergerak ke posisi itu BRU. Pola ini berlaku untuk semua bagian di sisi kanan. Setiap stiker yang ada di Fwajah bergerak ke Uwajah saat Rgerakan dilakukan, setiap stiker yang ada di Uwajah bergerak ke Bwajah, setiap stiker di Bbergerak ke Ddan setiap stiker di Dpindah keF. Kami dapat mendekode perubahan dari Rlangkah sebagai FUBD.

Kode berikut menghasilkan semua 6 kode yang diperlukan:

_sm_B.iFP.>c3Zk3
['BRFL', 'LFRB', 'DBUF', 'FUBD', 'RDLU', 'ULDR']
    ^       ^       ^       ^       ^       ^
 U move  D move  L move  R move  F move  B move

Dan kami melakukan perpindahan Hke status kubus Gsebagai berikut:

m.rW}[email protected]
m              G   map each piece d in G to:
 .rW   d              perform a rotated translation to d, but only if:
    }Hd                  H appears in d (d is currently on the face H)
            xZH           get the index of H in Z
        @...              and choose the code in the list of 6 (see above)

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.

l.uu<apply move H to G><parsed scramble>N<solved state>
u...N   performs all moves of the scramble to the state N
.u...   do this until cycle detected, this returns all intermediate states
l       print the length
Jakube
sumber
13

GAP, 792 783 782 749 650 Bytes

Ini 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 gunakan X^3.

Contoh penggunaan: f("R");

R:=(3,39,21,48)(6,42,24,51)(9,45,27,54)(10,12,18,16)(13,11,15,17);L:=(1,46,19,37)(4,49,22,40)(7,52,25,43)(30,36,34,28)(29,33,35,31);U:=(1,10,27,28)(2,11,26,29)(3,12,25,30)(37,43,45,39)(40,44,42,38);A:=R*L^3*F*F*B*B*R*L^3;D:=A*U*A;;F:=(1,3,9,7)(2,6,8,4)(10,48,36,43)(13,47,33,44)(16,46,30,45);B:=(27,25,19,21)(26,22,20,24)(39,28,52,18)(38,31,53,15)(37,34,54,12);d:=NewDictionary((),true);AddDictionary(d,'R',R);AddDictionary(d,'L',L);AddDictionary(d,'U',U);AddDictionary(d,'D',D);AddDictionary(d,'F',F);AddDictionary(d,'B',B);f:=function(s) local i,p,b,t;p:=();
for c in s do if c='\'' then t:=t^2;else t:=LookupDictionary(d,c);fi;p:=p*t;od;return Order(p);end;

Berikut adalah kode yang tidak ditandai dengan sedikit penjelasan

  # Here we define the primitive moves
R:=(3,39,21,48)(6,42,24,51)(9,45,27,54)(10,12,18,16)(13,11,15,17);
L:=(1,46,19,37)(4,49,22,40)(7,52,25,43)(30,36,34,28)(29,33,35,31);
U:=(1,10,27,28)(2,11,26,29)(3,12,25,30)(37,43,45,39)(40,44,42,38);
#D:=(7,34,21,16)(8,35,20,17)(9,36,19,18)(48,46,52,54)(47,49,53,51);
F:=(1,3,9,7)(2,6,8,4)(10,48,36,43)(13,47,33,44)(16,46,30,45);
B:=(27,25,19,21)(26,22,20,24)(39,28,52,18)(38,31,53,15)(37,34,54,12);

# Here we define D in terms of other primitive moves, saving on bytes
# Thanks @Lynn
# This is actually doable with a maximum of 3 of the primitive moves
# if a short enough sequence can be found.
D:=U^(R*L^3*F*F*B*B*R*L^3);

# create dictionary and add moves to it with appropriate char labels
d:=NewDictionary((),true);
AddDictionary(d,'R',R);
AddDictionary(d,'L',L);
AddDictionary(d,'U',U);
AddDictionary(d,'D',D);
AddDictionary(d,'F',F);
AddDictionary(d,'B',B);

f:=function(s)
    local c,p,t;

    # p will become the actual permutation passed to the function
    p:=();

    for c in s do
        if c='\'' then
            # The last generator we mutiplied (that we still have in t)
            # should have been its inverse. Compensate by preparing to
            # multiply it two more times to get t^3=t^-1. Thanks @Neil.
            t:=t^2;
        else
            t:=LookupDictionary(d,c);
        fi;
        p:=p*t;
    od;

    return Order(p);

end;
Liam
sumber
Setiap gerakan adalah akar keempat dari identitas, jadi Inverse Anda tidak perlu.
Neil
Anda mungkin bisa mengganti 45dengan 5di permutasi Anda, dan menyimpan tiga byte.
Lynn
Hasil yang ditemukan oleh Benson I di Singmaster, 1981 mengatakan: "Biarkan A = RL⁻¹F²B²RL⁻¹, lalu AUA = D." Memang, A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;lebih pendek dari definisi Anda untuk D(tapi saya tidak bisa mengujinya ...)
Lynn
Apakah GAP benar-benar tidak membiarkan Anda menulis ^-1untuk invers, BTW?
Lynn
Ya saya benar-benar ingin menggunakan ^ -1. Yang saya anggap cukup banyak hal yang sama @Neil katakan, kecuali dengan ^ 3 sebagai gantinya (yang sebenarnya adalah yang terpendek). Juga, ya saya bisa menguraikan gerakan ke gerakan lain, dan saya harus dapat menyimpan beberapa byte dengan melakukan itu, itu hanya masalah menemukan dekomposisi terpendek.
Liam
10

Mathematica, 413 401 byte

Evaluate[f/@Characters@"RFLBUD"]=LetterNumber@"ABFEJNRMDAEHIMQPCDHGLPTOBCGFKOSNADCBILKJEFGHQRST"~ArrayReshape~{6,2,4};
r[c_,l_]:=(b=Permute[c,Cycles@f@l];MapThread[(b[[#,2]]=Mod[b[[#,2]]+{"F","B","L","R"}~Count~l{-1,1,-1,1},#2])&,{f@l,{3,2}}];b);
p@s_:=Length[c={#,0}&~Array~20;NestWhileList[Fold[r,#,Join@@StringCases[s,x_~~t:""|"'":>Table[x,3-2Boole[t==""]]]]&,c,(Length@{##}<2||c!=Last@{##})&,All]]-1

Penjelasan

Cube Sebuah Rubik terdiri dengan 20 bergerak cubies (8 sudut, 12 tepi). Setiap cubie dapat diberi nomor:

sudut :

N   starting position
1     UFR
2     UBR
3     UBL
4     UFL
5     DFR
6     DBR
7     DBL
8     DFL

tepi :

N   starting position
9     UF
10    UR
11    UB
12    UL
13    FR
14    BR
15    BL
16    FL
17    DF
18    DR
19    DB
20    DL

Perhatikan bahwa ketika kubus dipelintir, kubus umumnya tidak berada di posisi awal lagi. Misalnya, ketika Rselesai, cubie 1bergerak dari UFRposisi baru UBR.

Dalam notasi seperti itu, belokan 90 derajat dapat digambarkan oleh 8 gerakan kubus. Misalnya, Rdijelaskan oleh

from  to
UFR   UBR
UBR   DBR
DBR   DFR
DFR   UFR
UR    BR
BR    DR
DR    FR
FR    UR

Karena setiap cubie memiliki posisi awal yang unik, setiap posisi memiliki cubie awal yang unik. Dengan kata lain, aturan UFR->UBRadalah adil 1->2(artinya Rmengambil cubie pada posisi awal cubie 1ke posisi awal cubie 2). Dengan demikian, Rdapat disederhanakan lebih lanjut menjadi satu siklus

Cycles[{{1,2,6,5}, {10,14,18,13}}]

Untuk 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

face color
U    yellow
D    white
F    red
B    orange
R    green
L    blue

Ketika kami menganalisis orientasi sudut, warna selain kuning atau putih diabaikan, dan kuning dan putih dianggap sebagai warna yang sama.

Misalkan cubie 1berada pada posisi awal UFR, segi kuning dapat disejajarkan dengan tiga wajah yang berbeda. Kami menggunakan integer untuk mewakili kasus-kasus ini,

0  yellow on U  (correct)
1  yellow on R  (120 degree clockwise)
2  yellow on F  (120 degree counterclockwise)

Misalkan cubie 1aktif DFL, tiga orientasi yang mungkin adalah

0  yellow on D  (correct)
1  yellow on L  (120 degree clockwise)
2  yellow on F  (120 degree counterclockwise)

Ketika kami menganalisis orientasi tepi, merah dan oranye diabaikan, dan kuning dan putih diabaikan hanya jika tepi memiliki segi hijau atau biru.

Misalkan cubie 10berada pada posisi awal UR, sisi hijau dapat disejajarkan dengan dua wajah yang berbeda. Dua kemungkinan orientasi adalah

0  green on R  (correct)
1  green on U  (180 degree)

Misalkan cubie 10aktif DF, dua orientasi yang mungkin adalah

0  green on D  (correct)
1  green on F  (180 degree)

Array digunakan untuk menyimpan status kubus. Keadaan awal kubus adalah

{{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},{9,0},{10,0},{11,0},{12,0},{13,0},{14,0},{15,0},{16,0},{17,0},{18,0},{19,0},{20,0}}

yang berarti bahwa setiap cubies berada pada posisi awal dengan orientasi yang benar.

Setelah itu R, keadaan kubus menjadi

{{5,2},{1,1},{3,0},{4,0},{6,1},{2,2},{7,0},{8,0},{9,0},{13,1},{11,0},{12,0},{18,1},{10,1},{15,0},{16,0},{17,0},{14,1},{19,0},{20,0}}

yang berarti bahwa cubie 5sekarang pada posisi 1( UFR) dengan orientasi 2, cubie 1sekarang pada posisi 2( UBR) dengan orientasi 1, cubie 3sekarang masih pada posisi 3( UBL) dengan orientasi 0, dan seterusnya.


Uji kasus

p["FF'"]            (* 1   *)
p["R"]              (* 4   *)
p["RUR'U'"]         (* 6   *)
p["LLUUFFUURRUU"]   (* 12  *)
p["LUFFRDRBF"]      (* 56  *)
p["LF"]             (* 105 *)
p["UFFR'DBBRL'"]    (* 120 *)
p["FRBL"]           (* 315 *)
njpipeorgan
sumber
7

Haskell, 252 byte

r=[-2..2]
s=mapM id[r,r,r]
t m p@[x,y,z]=case m of"R"|x>0->[x,z,-y];"L"|x<0->[x,-z,y];"U"|y>0->[-z,y,x];"D"|y<0->[z,y,-x];"F"|z>0->[y,-x,z];"B"|z<0->[-y,x,z];c:"'"->t[c]$t[c]$t[c]p;_->p
f m=length$s:fst(span(/=s)$tail$iterate(flip(foldl$flip$map.t)m)s)

Sampel berjalan:

*Main> f ["F","F'"]
1
*Main> f ["R"]
4
*Main> f ["R","U","R'","U'"]
6
*Main> f ["L","L","U","U","F","F","U","U","R","R","U","U"]
12
*Main> f ["L","U","F","F","R","D","R","B","F"]
56
*Main> f ["L","F"]
105
*Main> f ["U","F","F","R'","D","B","B","R","L'"]
120
*Main> f ["F","R","B","L"]
315
*Main> f ["R","U","U","D'","B","D'"]  -- maximum possible order
1260

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.

Anders Kaseorg
sumber
Ini sangat pintar! Saya pikir mengganti c:"'"dengan c:_menghemat dua byte.
Lynn
Terima kasih! Saya sedang mencari urutan 1260 untuk kasus-kasus uji, tetapi tidak bisa repot-repot mencarinya :)
Geobits
@ Lynn, itu tidak berhasil karena _juga cocok dengan daftar kosong.
Anders Kaseorg
Ini hebat, tetapi tampaknya sangat mirip dengan jawaban ini untuk pertanyaan lain codegolf.stackexchange.com/a/44775/15599 . Jika Anda terinspirasi oleh itu, Anda harus mengakuinya.
Level River St
@steveverrill, wow, itu memang terlihat sangat mirip, tapi tidak, saya belum melihatnya. Jawaban saya adalah pekerjaan mandiri saya. (Saya mengakui, tentu saja, bahwa Jan Dvorak datang dengan sebagian besar ide yang sama sebelum saya melakukannya.)
Anders Kaseorg
7

Ruby, 225 byte

->s{n=0
a=[]
b=[]
64.times{|i|a<<j=[(i&48)-16,(i&12)-4,i%4-1];b<<j*1}
d=1
(n+=1
s.reverse.chars{|c|m="UFRDBL".index(c)
m ?(e=m/3*2-1
b.each{|j|j[m%=3]*e>0&&(j[m-2],j[m-1]=j[m-1]*e*d,-j[m-2]*e*d)}
d=1):d=-1})until n>0&&a==b
n}

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=-1untuk U, F, R atau e=1untuk 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 dengan e*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 dari ddapat diubah dari 1 ke -1 untuk menyebabkan rotasi dari wajah berikut dalam arah yang berlawanan.

Tidak terkurung dalam program uji

f=->s{n=0                                      #number of repeats=0
  a=[]                                         #empty array for solved position
  b=[]                                         #empty array for current position
  64.times{|i|
    a<<j=[(i&48)-16,(i&12)-4,i%4-1]            #generate 64 cubies and append them to the solved array
    b<<j*1                                     #duplicate them and append to active array
  }
  d=1                                          #default rotation direction anticlockwise (we scan the moves in reverse)                              
  (                                            #start of UNTIL loop
    n+=1                                       #increment repeat counter
    s.reverse.chars{|c|                        #reverse list of moves and iterate through it
      m="UFRDBL".index(c)                      #assign move letter to m (for ' or any other symbol m is false)
      m ?                                      #if a letter
        (e=m/3*2-1                             #e=-1 for UFR, 1 for DBL
        b.each{|j|                             #for each cubie 
          j[m%=3]*e>0&&                        #m%=3 picks an axis. If the cubie is on the moving face of the cube
         (j[m-2],j[m-1]=j[m-1]*e*d,-j[m-2]*e*d)#rotate it: exchange the coordinates in the other 2 axes and invert the sign of one of them according to direction
        }                                      #as per the values of e and d. 
        d=1                                    #set d=1 (in case it was -1 at the start of the b.each loop)
      ):
      d=-1                                     #ELSE the input must be a ', so set d=-1 to reverse rotation of next letter
    }
   )until n>0&&a==b                            #end of UNTIL loop. continue until back at start position a==b
n}                                             #return n

p f["FF'"]               #      1
p f["R"]                 #      4
p f["RUR'U'"]            #      6
p f["LLUUFFUURRUU"]      #     12
p f["LUFFRDRBF"]         #     56
p f["LF"]                #    105
p f["UFFR'DBBRL'"]       #    120
p f["FRBL"]              #    315
Level River St
sumber
7

Python 2, 343 byte

def M(o,v,e):
 k=1
 for m in e:
  for c in'ouf|/[bPcU`Dkqbx-Y:(+=P4cyrh=I;-(:R6'[m::6]:i=~ord(c)%8*k;j=(ord(c)/8-4)*k;o[i],o[j]=o[j]-m/2,o[i]+m/2;v[i],v[j]=v[j],v[i];k=-k
V=range(20)
o,v,e=[0]*20,V[:],[]
for c in raw_input():i='FBRLUD'.find(c);e+=i<0and e[-1:]*2or[i]
M(o,v,e);n=1
while any(o[i]%(2+i/12)for i in V)or v>V:M(o,v,e);n+=1
print n

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

$ echo FRBL|python rubiks-cycle.py
315

$ echo RULURFLF|python rubiks-cycle.py
1260

Demonstrasi dan Test Suite Online .

primo
sumber
3
Pilihan nama dan argumen fungsi yang bagus!
Neil
3

Clojure, 359 byte

Ini mungkin codegolf kedua terpanjang saya. Menyadari bahwa saya bisa menghilangkan angka nol dari vektor Auntuk Fmembuat saya sangat senang: D

#(let[I(clojure.string/replace % #"(.)'""$1$1$1")D(range -2 3)S(for[x D y D z D][x y z])A[0 1]B[0 0 1]C[1]D[-1]E[0 -1]F[0 0 -1]](loop[P S[[n R]& Q](cycle(map{\F[A[B A D]]\B[E[F A C]]\L[D[C B E]]\R[C[C F A]]\U[B[E C B]]\D[F[A D B]]}I))c 0](if(=(> c 0)(= P S))(/ c(count I))(recur(for[p P](if(>(apply +(map * n p))0)(for[r R](apply +(map * r p)))p))Q(inc c)))))

Kurang bermain golf:

(def f #(let [I (clojure.string/replace % #"(.)'""$1$1$1")
              D [-2 -1 0 1 2]
              S (for[x D y D z D][x y z])
              L   {\F [[ 0  1  0][[0  0  1][ 0 1  0][-1  0 0]]]
                   \B [[ 0 -1  0][[0  0 -1][ 0 1  0][ 1  0 0]]]
                   \L [[-1  0  0][[1  0  0][ 0 0  1][ 0 -1 0]]]
                   \R [[ 1  0  0][[1  0  0][ 0 0 -1][ 0  1 0]]]
                   \U [[ 0  0  1][[0 -1  0][ 1 0  0][ 0  0 1]]]
                   \D [[ 0  0 -1][[0  1  0][-1 0  0][ 0  0 1]]]}]
          (loop [P S c 0 [[n R] & Q] (cycle(map L I))]
            (if (and (> c 0) (= P S))
              (/ c (count I))
              (recur (for[p P](if(pos?(apply +(map * n p)))
                                (for[r R](apply +(map * r p)))
                                p))
                     (inc c)
                     Q)))))

Ini hanya mengimplementasikan rotasi 3D dari himpunan bagian 5 x 5 x 5kubus yang dipilih . Awalnya saya akan menggunakan 3 x 3 x 3dan 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".

NikoNyrh
sumber
3

Secara kubik , 9 6 byte

¶-7)8%

Cobalah online! (Tidak bekerja sampai Dennis memperbarui TIO Cubically interpreter)

Penjelasan:

¶-7)8%
¶       read a string, insert into code
 -7     add 1 to notepad (subtracts the 7th face "sum" from notepad, defaulted to -1)
   )8   jump back to start of code if cube unsolved
     %  print notepad

Bahasa ini akan mendominasi semua tantangan >: D

MD XF
sumber
3
Semua esolang yang baru terbentuk ini. Kembali di hari saya, -7berarti kurangi tujuh tidak menambahkan satu walker getar marah
caird coinheringaahing
@cairdcoinheringaahing Memang. : P Menambahkan beberapa penjelasan tentang itu.
MD XF
1

Bersih , 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.

import StdEnv,StdLib
a=[-2..2];b=diag3 a a a
?m=iter(size m*2-1)\p=:(x,y,z)=case m.[0]of'F'|z>0=(y,~x,z);'U'|y>0=(~z,y,x);'R'|x>0=(x,z,~y);'B'|z<0=(~y,x,z);'D'|y<0=(z,y,~x);'L'|x<0=(x,~z,y);_=p
$l=length(takeWhile((<>)b)(tl(iterate(map(sseq(map?l)))b)))+1

Cobalah online!

Suram
sumber