Radfahren mit Rubiks

43

Während mein Sohn müßig den Zauberwürfel herumdrehte, bemerkte er, dass er immer wieder in den gelösten Zustand zurückkehrte. Ich bin mir ziemlich sicher, dass er anfangs dachte, dies sei eine Art Voodoo-Magie, aber ich erklärte, dass, wenn Sie dieselbe Abfolge von Zügen wiederholen, diese immer in ihren ursprünglichen Zustand zurückkehren wird. Schließlich.

Natürlich musste er es als Kind selbst ausprobieren und eine "zufällige" Sequenz auswählen, die er für schwierig hielt. Nach etwa zehn Wiederholungen verlor er den Überblick und fragte mich, wie oft er es wiederholen müsse. Da ich nicht wusste, welche Sequenz er benutzte, sagte ich ihm, dass ich es nicht wüsste, aber dass wir ein Programm schreiben könnten, um es herauszufinden.

Hier kommst du rein. Natürlich könnte ich einfach etwas zaubern, aber er würde es gerne selbst eintippen. Er ist allerdings noch kein sehr schneller Typist, deshalb brauche ich das kürzestmögliche Programm .

Zielsetzung

Geben Sie in einer vorgegebenen Abfolge von Umdrehungen so oft wie möglich aus, um den Würfel wieder in den ursprünglichen Zustand zu versetzen. Dies ist Codegolf, also gewinnen die wenigsten Bytes. Sie können ein Programm oder eine Funktion schreiben, und es gelten alle anderen üblichen Standardeinstellungen.

Eingang

Die Eingabe ist eine Folge von Zügen, die als Zeichenfolge, Liste oder in einem anderen Format für Ihre Sprache verwendet werden. Fühlen Sie sich frei, ein Trennzeichen (oder nicht) zwischen Zügen zu verwenden, wenn es sich um eine Zeichenfolge handelt.

Es gibt sechs "grundlegende" Züge, die zusammen mit ihren Inversen berücksichtigt werden müssen:

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

Die Umkehrungen werden durch das Hinzufügen eines Strichs 'nach dem Buchstaben dargestellt. Dies zeigt an, dass Sie dieses Gesicht gegen den Uhrzeigersinn drehen, also F'das vordere Gesicht gegen den Uhrzeigersinn drehen und F F'es sofort in den ursprünglichen Zustand zurückversetzen würden.

Für die Interessenten wird bei dieser Herausforderung eine begrenzte Anzahl von Singmaster-Notationen verwendet . Ruwix hat einige nette Animationen, wenn Sie es in Aktion sehen möchten .

Ausgabe

Die Ausgabe ist einfach die Mindestanzahl, mit der die Eingabesequenz ausgeführt werden muss.

Beispiele

Input                Output

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

Hier ist ein (ziemlich naiver) Löser, mit dem Sie Ihre in Java geschriebenen Antworten vergleichen können. Es werden auch 2Doppelzüge akzeptiert (der vierte Fall ist also gleichbedeutend mit 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;
        }
    }
}
Geobits
quelle
"im uhrzeigersinn" bedeutet "im uhrzeigersinn, wenn sie davor stehen" nehme ich an?
msh210
@ msh210 Richtig.
Geobits
7
In Bezug auf Pedanterie sollten Sie klarstellen, dass Sie die kleinste Zahl haben möchten, die ausreicht. Ansonsten könnte ich einfach die Größe der Gruppe ausgeben und Lagranges Satz zitieren ...
Peter Taylor
2
@ PeterTaylor Pedantry akzeptiert.
Geobits
4
Ich kann ein 500-Punkte-Kopfgeld für eine Lösung in Shuffle anbieten. Noch nicht sicher.
Lirtosiast

Antworten:

16

Pyth, 66 63 Bytes

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

Probieren Sie es online aus: Demo oder Test Suite . Beachten Sie, dass das Programm etwas langsam ist und der Online-Compiler die Antwort nicht berechnen kann RU2D'BD'. Aber seien Sie versichert, dass es auf meinem Laptop in etwa 12 Sekunden berechnet werden kann.

Das Programm akzeptiert (aus Versehen) auch 2Doppelzüge.

Vollständige Erklärung:

Scramble analysieren:

Zuerst werde ich mich mit den Primzahlen 'in den Eingabezeichenfolgen befassen . Ich ersetze diese einfach durch 3und dekodiere diese Zeichenfolge mit Lauflänge. Da Pyths Dekodierungsformat die Zahl vor dem Zeichen erfordert, kehre ich die Zeichenfolge vorher um. _r_Xz\'\39. Also kehre ich es danach wieder um.

Beschreiben Sie den gelösten Cube-Status:

=Z"UDLRFBordnet die Saite mit allen 6 Zügen zu Z.

Wir können einen Würfelzustand beschreiben, indem wir die Position für jedes Würfelstück beschreiben. Zum Beispiel können wir sagen, dass die Kante, die bei UL (Up-Left) sein sollte, derzeit bei FR (Front-Right) ist. Dazu muß ich alle Teile des Würfels gelöst erzeugen: f!s}RTcZ2yZ. yZgeneriert alle möglichen Teilmengen von "UDLRFB". Dies erzeugt offensichtlich auch die Teilmenge "UDLRFB"und die Teilmenge "UD". Das erste ergibt keinen Sinn, da es kein Stück gibt, das von allen 6 Seiten sichtbar ist, und das zweite ergibt keinen Sinn, da es kein Randstück gibt, das von oben und unten sichtbar ist . Deshalb entferne ich alle Subsets, die die Subsequenz enthalten "UD", "LR"oder "FB". Dies gibt mir die folgenden 27 Stücke:

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

Dies schließt auch die leere Zeichenfolge und alle sechs 1-Buchstaben-Zeichenfolgen ein. Wir könnten sie als das Stück in der Mitte des Würfels und die 6 Mittelstücke interpretieren. Offensichtlich werden sie nicht benötigt (da sie sich nicht bewegen), aber ich werde sie behalten.

Ein paar Züge machen:

Ich werde ein paar Zeichenkettenübersetzungen machen, um einen Zug auszuführen. Um die Idee zu visualisieren, schauen Sie sich das Eckstück an URF. Was passiert damit, wenn ich einen RUmzug mache ? Der Aufkleber auf dem UGesicht bewegt sich zum BGesicht, der Aufkleber Fbewegt sich zum UGesicht und der Aufkleber auf dem RGesicht bleibt auf dem RGesicht. Wir können sagen, dass sich das Stück an URFdie Position bewegt BRU. Dieses Muster gilt für alle Teile auf der rechten Seite. Jeder Aufkleber, der sich auf dem FGesicht befindet, bewegt sich zum UGesicht, wenn ein RZug ausgeführt wird, jeder Aufkleber, der sich auf dem UGesicht befindet, bewegt sich zum BGesicht, jeder Aufkleber auf den BZügen zu Dund jeder Aufkleber auf den DZügen zuF. Wir können die Änderungen eines RZuges als dekodieren FUBD.

Der folgende Code generiert alle 6 erforderlichen Codes:

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

Und wir führen einen Wechsel Hin den Cube-Status Gwie folgt aus:

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)

Zählen Sie die Anzahl der Wiederholungen:

Der Rest ist so ziemlich trivial. Ich führe einfach das Eingabe-Scramble für den gelösten Würfel immer wieder durch, bis ich eine Position erreiche, die ich zuvor besucht habe.

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
quelle
13

GAP, 792 783 782 749 650 Bytes

Das scheint zu funktionieren. Wenn es etwas vermasselt, lass es mich wissen.

Vielen Dank an @Lynn für den Hinweis, dass ich einige der primitiven Züge zerlegt habe.

Vielen Dank an @Neil für den Vorschlag, den Inverse(X)ich anstelle von verwende X^3.

Anwendungsbeispiel: 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;

Hier ist der ungolfed Code mit ein bisschen Erklärung

  # 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
quelle
Jeder Schritt ist eine vierte Wurzel der Identität, so dass Ihr Invers unnötig ist.
Neil
Sie können sich wahrscheinlich ersetzen 45mit 5in Ihre Permutationen und drei Bytes speichern.
Lynn
Ein Ergebnis von Benson, das ich 1981 in Singmaster gefunden habe, besagt: "Lass A = RL⁻¹F²B²RL⁻¹, dann AUA = D." Tatsächlich A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;ist es kürzer als deine Definition für D(aber ich kann es nicht testen ...)
Lynn
Lässt GAP Sie wirklich nicht ^-1für Inverses schreiben , übrigens?
Lynn
Ja, ich habe total Abstand zur Verwendung von ^ -1. Was ich annehme, ist so ziemlich dasselbe, was @Neil gesagt hat, außer mit ^ 3 (was eigentlich die kürzeste ist). Ja, ich könnte auch Züge in andere Züge zerlegen, und ich müsste in der Lage sein, dadurch mehrere Bytes einzusparen. Es wäre nur eine Frage der kürzesten Zerlegung.
Liam
10

Mathematica, 413 401 Bytes

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

Erklärungen

Ein Zauberwürfel besteht aus 20 beweglichen Würfeln (8 Ecken, 12 Kanten). Jedem Cubie kann eine Nummer zugewiesen werden:

Ecken :

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

Kanten :

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

Beachten Sie, dass sich die Würfel beim Drehen in der Regel nicht mehr in ihrer Ausgangsposition befinden. Wenn Rdies erledigt ist, 1bewegt sich der Cubie vonUFR zu einer neuen Position UBR.

In einer solchen Notation kann eine 90-Grad-Drehung durch 8 Bewegungen von Würfeln beschrieben werden. Zum Beispiel Rwird beschrieben durch

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

Da jeder Würfel eine eigene Startposition hat, hat jede Position einen eigenen Startwürfel. Das heißt, die Regel UFR->UBRist gerecht 1->2(bedeutet, dass Rder Cubie von der Startposition des Cubie 1zur Startposition des Cubie fährt 2). Somit Rkann ein Zyklus weiter vereinfacht werden

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

Um einen Zauberwürfel vollständig zu lösen, müssen wir die Würfel auch an ihren entsprechenden Startausrichtungen ausrichten. Die Flächen eines Würfels sind in verschiedenen Farben bemalt, das Schema, das ich beim Lösen von Würfeln häufig verwende, ist

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

Bei der Analyse der Ausrichtung von Ecken werden andere Farben als Gelb oder Weiß ignoriert und Gelb und Weiß werden als dieselbe Farbe betrachtet.

Angenommen, Cubie 1befindet sich in seiner Startposition UFRund die gelbe Facette kann auf drei verschiedene Flächen ausgerichtet werden. Wir verwenden eine ganze Zahl, um diese Fälle darzustellen,

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

Angenommen, Cubie 1ist eingeschaltet DFL, dann gibt es drei mögliche Ausrichtungen

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

Bei der Analyse der Ausrichtung von Kanten werden Rot und Orange ignoriert, und Gelb und Weiß werden nur ignoriert, wenn die Kante eine grüne oder blaue Facette aufweist.

Angenommen, Cubie 10befindet sich in seiner Startposition URund die grüne Facette kann auf zwei verschiedene Flächen ausgerichtet sein. Es gibt zwei mögliche Ausrichtungen

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

Angenommen, Cubie 10ist eingeschaltet DF, dann gibt es zwei mögliche Ausrichtungen

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

Ein Array wird zum Speichern des Status eines Cubes verwendet. Der Ausgangszustand eines Würfels ist

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

Das bedeutet, dass sich alle Cubies mit der richtigen Ausrichtung in ihrer Startposition befinden.

Danach Rwird der Zustand des Würfels

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

Das heißt, Cubie 5ist jetzt auf Position 1( UFR) mit Ausrichtung 2, Cubie 1ist jetzt auf Position 2( UBR) mit Ausrichtung 1, Cubie 3ist jetzt noch auf Position 3( UBL) mit Ausrichtung 0und so weiter.


Testfälle

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

Haskell, 252 Bytes

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)

Probeläufe:

*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

Die wichtigste Beobachtung hier ist, dass es einfacher ist, den Zauberwürfel als 5 × 5 × 5-Gitter von Punkten zu modellieren, als als 3 × 3 × 3-Gitter von orientierten Würfeln. Aus Eckwürfeln werden Würfel mit 2 × 2 × 2 Punkten, aus Kantenwürfeln Quadrate mit 2 × 2 × 1 Punkten und durch Verschieben werden Scheiben mit 5 × 5 × 2 Punkten gedreht.

Anders Kaseorg
quelle
Das ist wirklich schlau! Ich denke, das Ersetzen c:"'"durch c:_spart zwei Bytes.
Lynn
Vielen Dank! Ich war auf der Suche nach einer 1260-Sequenz für die Testfälle, konnte
mich
@Lynn, das funktioniert nicht, weil es _auch zur leeren Liste passt.
Anders Kaseorg
Das ist großartig, aber es scheint sehr ähnlich zu dieser Antwort auf eine andere Frage zu sein: codegolf.stackexchange.com/a/44775/15599 . Wenn Sie davon inspiriert wurden, sollten Sie es anerkennen.
Level River St
@steveverrill, wow, das sieht eindrucksvoll ähnlich aus, aber nein, ich hatte es nicht gesehen. Meine Antwort ist meine eigene unabhängige Arbeit. (Ich gebe natürlich zu, dass Jan Dvorak die meisten der gleichen Ideen hatte, bevor ich sie hatte.)
Anders Kaseorg,
7

Ruby, 225 Bytes

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

Ähnlich wie Anders Kaseorgs Antwort und inspiriert von Jan Dvoraks Antwort auf eine frühere Frage.

Im Gegensatz zu diesen Antworten benötige ich jedoch keine 125 Cubies. Ich verwende einen Zauberwürfel mit 27 Würfeln, aber rechteckigen Dimensionen. Im gelösten Zustand liegen die Ecken bei+/-1,+/-4,+/-16 .

Ich generiere ein Array von 64 Cubies, von denen jeder einen Mittelpunkt hat x=[-1,0,1,2], y=[-4,0,4,8], z=[-16-0,16,32] . Die Cubies mit den Koordinaten 2, 8 und 32 sind nicht erforderlich, richten aber keinen Schaden an und werden aus Golfgründen nicht verwendet. Die Tatsache, dass Länge, Breite und Tiefe der Cubies unterschiedlich sind: (1,4,16) bedeutet, dass leicht erkannt werden kann, ob sie sich am richtigen Ort, aber mit falscher Ausrichtung befinden.

Jeder Cubie wird nachverfolgt, während er durch die Faceturns bewegt wird. Wenn die Koordinate eines Cubies in der Achse, die der Fläche entspricht (multipliziert mit e=-1für U, F, R oder e=1für D, B, L), positiv ist, wird sie gedreht, indem die Koordinaten in der anderen 2-Achse vertauscht und ein angewendet werden entsprechender Vorzeichenwechsel auf eine der Koordinaten. Dies wird durch Multiplikation mit gesteuert e*d.

Die Eingabereihenfolge wird in umgekehrter Reihenfolge abgefragt. Dies macht keinen Unterschied, solange die "normalen" Drehungen nicht im Uhrzeigersinn, sondern gegen den Uhrzeigersinn ausgeführt werden. Der Grund dafür ist, dass 'der Wert von dvon 1 auf -1 geändert werden kann , wenn ein Symbol gefunden wird, um die Drehung der folgenden Fläche in die entgegengesetzte Richtung zu bewirken.

Ungolfed im Testprogramm

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

Python 2, 343 Bytes

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

Die Eingabe erfolgt aus stdin.

Die gegebene Folge von Drehungen wird wiederholt an einem virtuellen Würfel ausgeführt, bis er in den gelösten Zustand zurückkehrt. Der Würfelzustand wird als Orientierungsvektor und Permutationsvektor mit der Länge 20 gespeichert.

Die Ausrichtungen sind willkürlich festgelegt: Ein Kantenwürfel ist richtig ausgerichtet, wenn er an seinen Platz bewegt werden kann, ohne eine R- oder L-Vierteldrehung auszulösen. Die Ausrichtung der Eckwürfel wird relativ zu den Flächen F und B berücksichtigt.


Beispielnutzung

$ echo FRBL|python rubiks-cycle.py
315

$ echo RULURFLF|python rubiks-cycle.py
1260

Online-Demonstrations- und Test-Suite .

primo
quelle
3
Gute Auswahl an Funktionsnamen und Argumenten!
Neil
3

Clojure, 359 Bytes

Dies könnte mein zweitlängster Codegolf sein. Zu realisieren, dass ich nachfolgende Nullen aus Vektoren entfernen konnte A, Fhat mich sehr glücklich gemacht: 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)))))

Weniger golfen:

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

Dies implementiert einfach 3D-Rotationen ausgewählter Teilmengen des 5 x 5 x 5Würfels. Ursprünglich wollte ich verwenden 3 x 3 x 3und es dauerte eine Weile, bis mir klar wurde, warum ich nicht die richtigen Ergebnisse erhielt. Gute Testfälle! Einige zusätzliche Bytes für die erste Codierung "RUR'U'"als "RURRRUUU".

NikoNyrh
quelle
3

Kubisch , 9 6 Bytes

¶-7)8%

Probieren Sie es online! (Funktioniert erst, wenn Dennis den TIO Cubically-Interpreter aktualisiert.)

Erläuterung:

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

Diese Sprache beherrscht alle Herausforderungen>: D

MD XF
quelle
3
All diese neuen Esolangs. Zurück in meiner Zeit -7bedeutete subtrahieren sieben eine Beurteilung schreibt wütend schüttelt Walker
caird coinheringaahing
@cairdcoinheringaahing In der Tat. : P Fügte eine Erklärung hinzu.
MD XF
1

Sauber , 255 Bytes

Getrennt von der fast identischen Haskell-Antwort als Antwort auf diese Frage, die als Duplikat geschlossen wurde, als sie fast fertig war, habe ich die Antwort hier gepostet.

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

Probieren Sie es online!

Οurous
quelle