Kolarstwo z Rubikiem

43

Bezczynnie przekręcając kostkę Rubika , mój syn zauważył, że wraca do stanu rozwiązanego. Jestem prawie pewien, że początkowo myślał, że to jakaś magia voodoo, ale wyjaśniłem, że jeśli będziesz powtarzał tę samą sekwencję ruchów, zawsze wróci do swojego pierwotnego stanu. Ostatecznie.

Oczywiście, będąc dzieckiem, musiał sam to wypróbować i wybrać „losową” sekwencję, która według niego będzie trudna. Stracił utwór po około dziesięciu powtórzeniach i zapytał mnie, ile razy będzie musiał to powtórzyć. Nie znając sekwencji, której używał, powiedziałem mu, że nie wiem, ale że możemy napisać program, aby się dowiedzieć.

Właśnie tam wchodzisz. Oczywiście mógłbym coś wymieszać, ale chciałby to napisać w sobie. Jednak nie jest jeszcze bardzo szybką maszynistką, więc potrzebuję możliwie najkrótszego programu .

Cel

Biorąc pod uwagę sekwencję zwojów, wypisz najmniejszą liczbę operacji, które należy wykonać, aby przywrócić kostkę do pierwotnego stanu. To jest kod golfowy, więc wygrywa najmniej bajtów. Możesz napisać program lub funkcję i obowiązują wszystkie inne standardowe ustawienia domyślne.

Wejście

Dane wejściowe to sekwencja ruchów, traktowana jako ciąg znaków, lista lub inny format odpowiedni dla Twojego języka. Możesz używać separatora (lub nie) między ruchami, jeśli jest w postaci łańcucha.

Istnieje sześć „podstawowych” ruchów, które należy wziąć pod uwagę, wraz z ich odwróceniami:

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

Odwrotności są reprezentowane przez dodanie znaku pierwszego 'po literze. Oznacza to, że obrócisz tę twarz przeciwnie do ruchu wskazówek zegara, więc F'obróci przednią twarz przeciwnie do ruchu wskazówek zegara i F F'od razu powróci do pierwotnego stanu.

Dla zainteresowanych wyzwaniem jest ograniczony zestaw notacji Singmaster . Ruwix ma fajne animacje, jeśli chcesz zobaczyć go w akcji.

Wynik

Dane wyjściowe to po prostu minimalna liczba przypadków, w których sekwencja wejściowa musi zostać wykonana.

Przykłady

Input                Output

FF'               ->      1
R                 ->      4
RUR'U'            ->      6
LLUUFFUURRUU      ->     12
LUFFRDRBF         ->     56
LF                ->    105
UFFR'DBBRL'       ->    120
FRBL              ->    315

Oto (dość naiwny) solver do porównywania twoich odpowiedzi, napisany w Javie. Akceptuje również 2podwójne ruchy (więc czwarty przypadek jest równoważny 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;
        }
    }
}
Geobity
źródło
„zgodnie z ruchem wskazówek zegara” oznacza „zgodnie z ruchem wskazówek zegara, gdy stoisz przed nim”, zakładam?
msh210
@ msh210 Prawidłowo.
Geobits
7
W kwestii pedanterii myślę, że powinieneś wyraźnie powiedzieć, że chcesz najmniejszej liczby, która wystarczy. W przeciwnym razie mógłbym podać wielkość grupy i zacytować twierdzenie Lagrange'a ...
Peter Taylor
2
@PeterTaylor Pedantry akceptowane.
Geobity
4
I może zaoferować 500 punktową premię do roztworu w Shuffle. Nie wiem jeszcze.
lirtosiast

Odpowiedzi:

16

Pyth, 66 63 bajtów

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

Wypróbuj online: pakiet demonstracyjny lub testowy . Zauważ, że program działa trochę wolno i kompilator online nie jest w stanie obliczyć odpowiedzi RU2D'BD'. Ale zapewniam, że może to obliczyć na moim laptopie w około 12 sekund.

Program (przypadkowo) akceptuje również 2podwójne ruchy.

Pełne objaśnienie:

Parse scramble:

Najpierw zajmę się znakami pierwszymi 'w ciągach wejściowych. Po prostu zastępuję je 3ciągiem dekodującym ten ciąg. Ponieważ format dekodowania Pytha wymaga liczby przed znakiem, uprzednio odwracam ciąg. _r_Xz\'\39. Więc potem odwracam to z powrotem.

Opisz stan rozwiązanej kostki:

=Z"UDLRFBprzypisuje ciąg ze wszystkimi 6 ruchami do Z.

Możemy opisać stan kostki, opisując lokalizację każdego kawałka kostki. Na przykład możemy powiedzieć, że krawędź, która powinna znajdować się w UL (lewy górny róg), znajduje się obecnie w FR (prawy przedni). Do tego muszę wygenerować wszystkie kawałki Prócz modułu: f!s}RTcZ2yZ. yZgeneruje wszystkie możliwe podzbiory "UDLRFB". To oczywiście generuje również podzbiór "UDLRFB"i podzbiór "UD". Pierwszy nie ma żadnego sensu, ponieważ nie ma elementu widocznego ze wszystkich 6 stron, a drugi nie ma żadnego sensu, ponieważ nie ma elementu krawędzi, który byłby widoczny od góry i od dołu . Dlatego usuwam wszystkie podzbiory, które zawierają podsekwencje "UD", "LR"lub "FB". To daje mi 27 następujących elementów:

'', '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'

Obejmuje to również pusty ciąg i wszystkie sześć ciągów 1-literowych. Możemy zinterpretować je jako element pośrodku sześcianu i 6 elementów środkowych. Oczywiście nie są wymagane (ponieważ się nie ruszają), ale ich zatrzymam.

Robienie niektórych ruchów:

Zrobię kilka tłumaczeń ciągów, aby wykonać ruch. Aby zwizualizować ten pomysł, zajrzyj do narożnika URF. Co się z tym stanie, kiedy wykonam Rruch? Naklejka na Utwarzy przesuwa się na Btwarz, nalepka Fprzesuwa się na Utwarz, a naklejka na Rtwarzy pozostaje na Rtwarzy. Można powiedzieć, że kawałek przy URFprzesuwa się na pozycję BRU. Ten wzór dotyczy wszystkich elementów po prawej stronie. Każda naklejka na Ftwarzy przesuwa się na Utwarz podczas wykonywania Rruchu, każda naklejka na Utwarzy przesuwa się na Btwarz, każda naklejka na Bruchach Di każda naklejka na DruchachF. Możemy dekodować zmiany Rruchu jako FUBD.

Poniższy kod generuje wszystkie 6 niezbędnych kodów:

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

I wykonujemy przejście Hdo stanu kostki Gw następujący sposób:

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)

Policz liczbę powtórzeń:

Reszta jest prawie banalna. Po prostu wykonuję szyfrowanie wejściowe do rozwiązanej kostki w kółko, dopóki nie osiągnę pozycji, którą wcześniej odwiedziłem.

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
źródło
13

GAP, 792 783 782 749 650 bajtów

To wydaje się działać. Jeśli coś z tym popsunie, daj mi znać.

Dzięki @Lynn za sugestię, że rozkładam niektóre prymitywne ruchy.

Dzięki @Neil za sugestię, że zamiast Inverse(X)używać X^3.

Przykład użycia: 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;

Oto niepoznany kod z odrobiną wyjaśnienia

  # 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
źródło
Każdy ruch jest czwartym korzeniem tożsamości, więc Twój Odwrotny jest niepotrzebny.
Neil
Prawdopodobnie można wymienić 45ze 5w twoich permutacji i zapisz trzy bajty.
Lynn
Wynik Bensona, który znalazłem w Singmaster, 1981, mówi: „Niech A = RL⁻¹F²B²RL⁻¹, a następnie AUA = D.” Rzeczywiście, A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;jest krótszy niż twoja definicja D(ale nie mogę go przetestować ...)
Lynn
Czy GAP naprawdę nie pozwala pisać ^-1dla inwersów, BTW?
Lynn
Tak, całkowicie rozstawiłem się przy użyciu ^ -1. To, co zakładam, jest prawie tym samym, co mówił @Neil, z wyjątkiem zamiast ^ 3 (co w rzeczywistości jest najkrótsze). Tak, tak, mógłbym rozłożyć ruchy na inne ruchy i powinienem być w stanie zaoszczędzić kilka bajtów, robiąc to, byłoby to po prostu znalezienie najkrótszego rozkładu.
Liam
10

Mathematica, 413 401 bajtów

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

Objaśnienia

Kostka Rubika składa się z 20 ruchomych kostek (8 rogów, 12 krawędzi). Każdy sześcian może otrzymać numer:

rogi :

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

krawędzie :

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

Zauważ, że gdy sześcian jest skręcony, zasadniczo nie są już w swoich pozycjach wyjściowych. Na przykład, po Rzakończeniu, kostka 1przechodzi z UFRnowej pozycji UBR.

W takiej notacji obrót o 90 stopni można opisać 8 ruchami sześcianów. Na przykład Rjest opisany przez

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

Ponieważ każdy sześcian ma unikalną pozycję początkową, każda pozycja ma unikalną pozycję początkową. Innymi słowy, reguła UFR->UBRjest po prostu 1->2(oznacza, że Rsześcienna pozycja początkowa sześciennego 1do pozycji początkowej sześciennego 2). W ten sposób Rmożna uprościć dalej do cyklu

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

Aby w pełni rozwiązać Kostkę Rubika, musimy również dopasować kostki do odpowiadających im orientacji początkowych. Ściany sześcianu są pomalowane na różne kolory, schemat, którego często używam podczas rozwiązywania kostek

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

Analizując orientacje narożników, kolory inne niż żółty lub biały są ignorowane, a żółty i biały są uważane za ten sam kolor.

Załóżmy, że kostka 1jest w pozycji początkowej UFR, żółty aspekt może być wyrównany do trzech różnych ścian. Używamy liczby całkowitej do reprezentowania tych przypadków,

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

Załóżmy, że sześcian 1jest włączony DFL, jego trzy możliwe orientacje to

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

Analizując orientację krawędzi, czerwony i pomarańczowy są ignorowane, a żółty i biały są ignorowane tylko wtedy, gdy krawędź ma zielony lub niebieski fasetowanie.

Załóżmy, że kostka 10jest w pozycji początkowej UR, zielony aspekt może być wyrównany do dwóch różnych ścian. Możliwe są dwie orientacje

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

Załóżmy, że cubie 10jest włączona DF, możliwe są dwie możliwe orientacje

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

Tablica służy do przechowywania stanu kostki. Stan początkowy kostki to

{{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}}

co oznacza, że ​​wszystkie kostki są w pozycji wyjściowej z prawidłową orientacją.

Po Rtym stanie się sześcian

{{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}}

co oznacza, że ​​kostka 5jest teraz w pozycji 1( UFR) z orientacją 2, kostka 1jest teraz w pozycji 2( UBR) z orientacją 1, kostka 3jest teraz w pozycji 3( UBL) z orientacją 0i tak dalej.


Przypadki testowe

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
źródło
7

Haskell, 252 bajty

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)

Przykładowe przebiegi:

*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

Kluczową obserwacją tutaj jest to, że łatwiej jest modelować kostkę Rubika jako siatkę punktów 5 × 5 × 5, a nie siatkę zorientowanych sześcianów 3 × 3 × 3. Narożniki stają się sześcianami o wymiarach 2 × 2 × 2 punkty, brzegi stają się kwadratami o wymiarach 2 × 2 × 1 punktów, a ruchy obracają plastry o wymiarach 5 × 5 × 2 punktów.

Anders Kaseorg
źródło
To jest naprawdę sprytne! Myślę, że zastąpienie c:"'"przez c:_zapisuje dwa bajty.
Lynn
Dzięki! Szukałem sekwencji 1260 dla przypadków testowych, ale nie mogłem się tym przejmować :)
Geobits
@ Lynn, to nie działa, ponieważ _pasuje również do pustej listy.
Anders Kaseorg,
To świetnie, ale wydaje się bardzo podobne do tej odpowiedzi na inne pytanie codegolf.stackexchange.com/a/44775/15599 . Jeśli zainspirowało Cię to, powinieneś to przyznać.
Level River St
@steveverrill, wow, to wygląda imponująco podobnie, ale nie, nie widziałem tego. Moja odpowiedź to moja niezależna praca. (Przyznaję oczywiście, że Jan Dvorak wpadł na większość tych samych pomysłów, zanim to zrobiłem.)
Anders Kaseorg,
7

Rubinowy, 225 bajtów

->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}

Podobna do odpowiedzi Anders Kaseorg i inspirowane przez Jana Dvoraka odpowiedzi na poprzednie pytanie.

Jednak w przeciwieństwie do tych odpowiedzi, nie potrzebuję 125 kostek. Używam kostki rubika złożonej z 27 sześcianów, ale o prostokątnych wymiarach. W stanie rozwiązanym rogi są +/-1,+/-4,+/-16.

Generuję tablicę 64 sześcianów, każdy z wybranym środkiem x=[-1,0,1,2], y=[-4,0,4,8], z=[-16-0,16,32]. Kostki o współrzędnych 2, 8 i 32 są niepotrzebne, ale nie wyrządzają szkody, więc pozostawia się je z powodów golfowych. Fakt, że długość, szerokość i głębokość kostek są różne: (1,4,16) oznacza, że ​​łatwo jest wykryć, czy znajdują się we właściwym miejscu, ale mają niewłaściwe ustawienie.

Każdy sześcian jest śledzony, gdy jest przesuwany przez obie strony. Jeśli współrzędna sześcianu w osi odpowiadającej powierzchni (pomnożona przez e=-1dla U, F, R lub e=1dla D, B, L) jest dodatnia, wówczas zostanie obrócona poprzez zamianę współrzędnych na drugiej 2 osi i zastosowanie odpowiednia zmiana znaku na jedną ze współrzędnych. Jest to kontrolowane przez pomnożenie przez e*d.

Sekwencja wejściowa jest skanowana w odwrotnej kolejności. Nie robi to różnicy, o ile „normalne” obroty są wykonywane w kierunku przeciwnym do ruchu wskazówek zegara zamiast w prawo. Powodem tego jest to, że jeśli 'zostanie znaleziony symbol, wartość dmożna zmienić z 1 na -1, aby spowodować obrót następnej powierzchni w przeciwnym kierunku.

Niegolfowany w programie testowym

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
źródło
7

Python 2, 343 bajty

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

Dane wejściowe są pobierane ze standardowego wejścia.

Dana sekwencja skrętów jest wykonywana wielokrotnie na wirtualnej kostce, aż powróci do stanu rozwiązanego. Stan kostki jest przechowywany jako wektor orientacji i wektor permutacji, oba o długości 20.

Orientacje są nieco dowolnie zdefiniowane: sześcian brzegowy jest zorientowany poprawnie, jeśli można go przesunąć na miejsce bez wywoływania obrotu o ćwierć obrotu R lub L. Orientacja kostek narożnych jest uwzględniana względem powierzchni F i B.


Przykładowe użycie

$ echo FRBL|python rubiks-cycle.py
315

$ echo RULURFLF|python rubiks-cycle.py
1260

Pakiet demonstracyjny i testowy online .

primo
źródło
3
Niezły wybór nazwy funkcji i argumentów!
Neil,
3

Clojure, 359 bajtów

To może być mój drugi najdłuższy codegolf. Zdając sobie sprawę, że mogę upuścić końcowe zera z wektorów, Aaby Fbardzo mnie uszczęśliwić: 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)))))

Mniej golfa:

(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)))))

To po prostu implementuje obroty 3D wybranych podzbiorów 5 x 5 x 5kostki. Początkowo miałem zamiar użyć 3 x 3 x 3i zajęło mi trochę czasu, aby zrozumieć, dlaczego nie otrzymałem poprawnych wyników. Dobre przypadki testowe! Niektóre dodatkowe bajty do kodowania pięści "RUR'U'"jako "RURRRUUU".

NikoNyrh
źródło
3

Sześciennie , 9 6 bajtów

¶-7)8%

Wypróbuj online! (Nie działa, dopóki Dennis nie zaktualizuje interpretera Cubio TIO)

Wyjaśnienie:

¶-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

Ten język zdominuje wszystkie wyzwania >: D

MD XF
źródło
3
Wszystkie te nowomodne esolangi. W moich czasach -7oznaczało to odjęcie siedmiu, a nie dodanie jednego ze złością trzęsie
walkerem
@cairdcoinheringaahing Rzeczywiście. : P Dodano wyjaśnienie.
MD XF,
1

Czysty , 255 bajtów

Pochodzi osobno od prawie identycznej odpowiedzi Haskella jako odpowiedź na to pytanie, które zostało zamknięte jako duplikat, gdy było prawie gotowe, więc opublikowałem odpowiedź tutaj.

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

Wypróbuj online!

Obrzydliwe
źródło