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 2
Doppelzü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;
}
}
}
quelle
Antworten:
Pyth,
6663 BytesProbieren 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
2
Doppelzüge.Vollständige Erklärung:
Scramble analysieren:
Zuerst werde ich mich mit den Primzahlen
'
in den Eingabezeichenfolgen befassen . Ich ersetze diese einfach durch3
und 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"UDLRFB
ordnet die Saite mit allen 6 Zügen zuZ
.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
.yZ
generiert 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: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 einenR
Umzug mache ? Der Aufkleber auf demU
Gesicht bewegt sich zumB
Gesicht, der AufkleberF
bewegt sich zumU
Gesicht und der Aufkleber auf demR
Gesicht bleibt auf demR
Gesicht. Wir können sagen, dass sich das Stück anURF
die Position bewegtBRU
. Dieses Muster gilt für alle Teile auf der rechten Seite. Jeder Aufkleber, der sich auf demF
Gesicht befindet, bewegt sich zumU
Gesicht, wenn einR
Zug ausgeführt wird, jeder Aufkleber, der sich auf demU
Gesicht befindet, bewegt sich zumB
Gesicht, jeder Aufkleber auf denB
Zügen zuD
und jeder Aufkleber auf denD
Zügen zuF
. Wir können die Änderungen einesR
Zuges als dekodierenFUBD
.Der folgende Code generiert alle 6 erforderlichen Codes:
Und wir führen einen Wechsel
H
in den Cube-StatusG
wie folgt aus: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.
quelle
GAP,
792 783 782749650 BytesDas 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 verwendeX^3
.Anwendungsbeispiel:
f("R");
Hier ist der ungolfed Code mit ein bisschen Erklärung
quelle
45
mit5
in Ihre Permutationen und drei Bytes speichern.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ürD
(aber ich kann es nicht testen ...)^-1
für Inverses schreiben , übrigens?Mathematica,
413401 BytesErklärungen
Ein Zauberwürfel besteht aus 20 beweglichen Würfeln (8 Ecken, 12 Kanten). Jedem Cubie kann eine Nummer zugewiesen werden:
Ecken :
Kanten :
Beachten Sie, dass sich die Würfel beim Drehen in der Regel nicht mehr in ihrer Ausgangsposition befinden. Wenn
R
dies erledigt ist,1
bewegt sich der Cubie vonUFR
zu einer neuen PositionUBR
.In einer solchen Notation kann eine 90-Grad-Drehung durch 8 Bewegungen von Würfeln beschrieben werden. Zum Beispiel
R
wird beschrieben durchDa jeder Würfel eine eigene Startposition hat, hat jede Position einen eigenen Startwürfel. Das heißt, die Regel
UFR->UBR
ist gerecht1->2
(bedeutet, dassR
der Cubie von der Startposition des Cubie1
zur Startposition des Cubie fährt2
). SomitR
kann ein Zyklus weiter vereinfacht werdenUm 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
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
1
befindet sich in seiner StartpositionUFR
und die gelbe Facette kann auf drei verschiedene Flächen ausgerichtet werden. Wir verwenden eine ganze Zahl, um diese Fälle darzustellen,Angenommen, Cubie
1
ist eingeschaltetDFL
, dann gibt es drei mögliche AusrichtungenBei 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
10
befindet sich in seiner StartpositionUR
und die grüne Facette kann auf zwei verschiedene Flächen ausgerichtet sein. Es gibt zwei mögliche AusrichtungenAngenommen, Cubie
10
ist eingeschaltetDF
, dann gibt es zwei mögliche AusrichtungenEin Array wird zum Speichern des Status eines Cubes verwendet. Der Ausgangszustand eines Würfels ist
Das bedeutet, dass sich alle Cubies mit der richtigen Ausrichtung in ihrer Startposition befinden.
Danach
R
wird der Zustand des WürfelsDas heißt, Cubie
5
ist jetzt auf Position1
(UFR
) mit Ausrichtung2
, Cubie1
ist jetzt auf Position2
(UBR
) mit Ausrichtung1
, Cubie3
ist jetzt noch auf Position3
(UBL
) mit Ausrichtung0
und so weiter.Testfälle
quelle
Haskell, 252 Bytes
Probeläufe:
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.
quelle
c:"'"
durchc:_
spart zwei Bytes._
auch zur leeren Liste passt.Ruby, 225 Bytes
Ä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=-1
für U, F, R odere=1
fü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 gesteuerte*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 vond
von 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
quelle
Python 2, 343 Bytes
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
Online-Demonstrations- und Test-Suite .
quelle
Clojure, 359 Bytes
Dies könnte mein zweitlängster Codegolf sein. Zu realisieren, dass ich nachfolgende Nullen aus Vektoren entfernen konnte
A
,F
hat mich sehr glücklich gemacht: DWeniger golfen:
Dies implementiert einfach 3D-Rotationen ausgewählter Teilmengen des
5 x 5 x 5
Würfels. Ursprünglich wollte ich verwenden3 x 3 x 3
und 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"
.quelle
Kubisch ,
96 BytesProbieren Sie es online! (Funktioniert erst, wenn Dennis den TIO Cubically-Interpreter aktualisiert.)
Erläuterung:
Diese Sprache beherrscht alle Rubiks-Cube- Herausforderungen>: D
quelle
-7
bedeutete subtrahieren sieben eine Beurteilung schreibt wütend schüttelt WalkerSauber , 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.
Probieren Sie es online!
quelle