Löse Rubiks Würfel

Schreiben Sie das kürzeste Programm, das Rubiks Würfel (3 * 3 * 3) innerhalb eines angemessenen Zeitraums löst und sich bewegt (z. B. maximal 5 Sekunden auf Ihrer Maschine und weniger als 1000 Züge).

Die Eingabe erfolgt im Format:

UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

(Diese spezielle Eingabe repräsentiert den gelösten Würfel).
Die ersten 12 2-stelligen Zeichenfolgen sind die Kanten in den Positionen UF, UR, ... BL (U = oben, F = vorne, R = rechts, B = hinten, L = links, D = unten), dann die nächsten 8 3-stellige Zeichenfolgen sind die Ecken an den Positionen UFR, URB, ... DBR.

Die Ausgabe sollte eine Folge von Zügen in diesem Format enthalten:

D+ L2 U+ F+ D+ L+ D+ F+ U- F+

Während D1 oder D + das Drehen der D-Seite (nach unten) im Uhrzeigersinn um 90 Grad darstellt, dreht L2 die L-Seite um 180 Grad, U3 oder U- das Drehen der U-Seite gegen den Uhrzeigersinn um 90 Grad.
Bei Buchstaben wird die Groß- / Kleinschreibung nicht berücksichtigt, und Leerzeichen sind optional.

Die obige Ausgabe ist beispielsweise für die folgende Eingabe korrekt:

RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

Weitere Details finden Sie in Tomas Rokickis Würfelwettbewerb , mit der Ausnahme, dass die Wertung direkt nach Dateigröße erfolgt, wie bei einem normalen Code-Golfproblem. Ein Online-Tester ist ebenfalls enthalten.

Als Referenz ist die kürzeste bereits geschriebene Lösung der letzte Eintrag in der Liste der Gewinner des Würfelwettbewerbs

Für diejenigen, die Schwierigkeiten haben, das Layoutformat zu visualisieren:

0-1 2-3 4-5 6-7 8-9 10-11 12-13 14-15 16-17 18-19 20-21 22-23 24-25-26 27-28-29 30-31-32 33-34-35 36-37-38 39-40-41 42-43-44 45-46-47
UF  UR  UB  UL  DF   DR    DB   DL    FR    FL     BR    BL     UFR      URB      UBL      ULF      DRF      DFL      DLB      DBR

Front:

                 +-------+-------+-------+
                /       /       /       /|
               /  30   /   4   /  27   / |
              +-------+-------+-------+  |
             /       /       /       /|28+
            /   6   /       /   2   / | /|
           +-------+-------+-------+  |/ |
          /       /       /       /|3 +  |
         /  33   /   0   /  24   / | /|21+
        +-------+-------+-------+  |/ | /|
        |       |       |       |26+  |/ |
        |  35   |   1   |   25  | /|  +  |
        |       |       |       |/ | /|47+
        +-------+-------+-------+  |/ | /
        |       |       |       |17+  |/
        |  18   |       |  16   | /|11+
        |       |       |       |/ | /
        +-------+-------+-------+  |/
        |       |       |       |37+
        |  40   |   9   |  38   | /
        |       |       |       |/
        +-------+-------+-------+


Hidden faces:

                 +-------+-------+-------+
                /|       |       |       |
               / |  31   |   5   |  29   |
              +  |       |       |       |
             /|32+-------+-------+-------+
            / | /|       |       |       |
           +  |/ |  22   |       |  20   |
          /|7 +  |       |       |       |
         / | /|23+-------+-------+-------+
        +  |/ | /|       |       |       |
        |34+  |/ |  44   |  13   |  46   |
        | /|  +  |       |       |       |
        |/ | /|43+-------+-------+-------+
        +  |/ | /       /       /       /
        |19+  |/  42   /  12   /  45   /
        | /|15+-------+-------+-------+
        |/ | /       /       /       /
        +  |/  14   /       /  10   /
        |41+-------+-------+-------+
        | /       /       /       /
        |/  39   /   8   /   36  /
        +-------+-------+-------+

code-golf puzzle-solver rubiks-cube restricted-time code-bowling code-golf ascii-art code-challenge code-golf c code-golf hello-world code-golf string decision-problem code-challenge primes number-theory code-golf code-golf python pi code-golf graphical-output game atomic-code-golf whitespace balanced-string code-golf geometry code-golf optimization board-game puzzle-solver fastest-code primes code-challenge code-golf hello-world polyglot code-golf cryptography code-golf javascript aditsu
quelle

Werden andere Sprachen als C / C ++ / Java / Perl / Python akzeptiert?

Egor Skriptunoff

@EgorSkriptunoff Verwenden Sie hier ja, was immer Sie möchten, nur keine Bibliotheken zum Lösen von Würfeln.

Aditsu

Und was ist mit Punkten? Übliches Code-Golf-Scoring (Bytes im Programm) oder komplexes Scoring wie im Wettbewerb von 2004?

Egor Skriptunoff

@jdstankosky, ich habe ein Diagramm hinzugefügt.

Peter Taylor

Dürfen wir die Aufkleber abziehen und bewegen?

Iszi

Antworten:

C ++ - 1123

Da bisher noch niemand eine Antwort gepostet hat, habe ich beschlossen, meine 2004-Lösung zu vereinfachen und zu verbessern. Es ist immer noch weit hinter der kürzesten, die ich in der Frage erwähnt habe.

#include<iostream>
#include<vector>
#define G(i,x,y)for(int i=x;i^y;i++)
#define h(x)s[a[x]/q*q+(a[x]+j)%q-42]
#define B(x)D=x;E=O.substr(j*3,3);G(i,0,3)E+=F[5-F.find(E[2-i])];G(i,0,D.length())D[i]=E[F.find(D[i++])];m.push_back(D);
#define P(a,b)G(i,0,6)G(k,49,52){e[0]=F[i];e[1]=k;m.push_back(e);}G(j,0,24){B(a)B(b)}
#define T C();z=m.size();for(b=c;b;){d=s;G(i,o=w=1,4){w*=z;if(o)G(j,0,w)if(o){s=d;u=j;G(k,0,i){f=m[u%z];G(x,0,f.length()){a=M[F.find(f[x++])];G(i,0,f[x]-48)G(l,0,2){q=3-l;p=4*l;G(j,0,q){t=h(p+3);G(k,-3,0)h(p-k)=h(p-1-k);h(p)=t;}}}u/=z;}C();if(c<b){u=j;G(k,0,i){std::cout<<m[u%z];u/=z;}b=c;o=0;}}}}
std::string s,a,D,E,d,f,e="  ",S="UFURUBULDFDRDBDLFRFLBRBLUFRURBUBLULFDRFDFLDLBDBR",F="ULFBRD",M[]={"KHEB*0.,","KRTI0<8@","KDNS*;2=","IVXG/@7>","BGWP,>4:","QNWT2468"},O=S.substr(24)+"FDRFRUFULFLDRDBRBURUFRFDBDLBLUBURBRDLDFLFULUBLBD";std::vector<std::string>m;int
w,X=8,Y=16,o,c,u,b,z,p,q,t;void C(){c=0;G(i,X,Y)c+=s[i]!=S[i];}main(int
g,char**v){G(i,1,g)s+=v[i];P("U2F1R1L3U2L1R3F1U2","L3R1F3L1R3D2L3R1F3L1R3");T;Y=24;T;X=0;T;m.clear();P("R3D3R1D3R3D2R1L1D1L3D1L1D2L3","R1F3L3F1R3F3L1F1");G(I,5,9){Y=I*6;T}}

Es ist nicht zufällig, aber es geht auch nicht einfach vonstatten. Es löst zuerst die Kanten, dann die Ecken. Bei jedem Schritt werden verschiedene Kombinationen von bis zu 4 Algorithmen und einfachen Gesichtszügen (nacheinander, nicht zufällig) ausprobiert, bis sich die Anzahl der gelösten Teile verbessert hat. Anschließend werden die Schritte wiederholt, bis sie gelöst sind. Es werden 2 Algorithmen für Kanten und 2 für Ecken verwendet, die in alle Würfelpositionen übersetzt werden.

Beispielausgabe für RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU:

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 Züge, 0,3 Sek. Hier)

aditsu
quelle

Was weißt du ... eine andere Antwort wurde innerhalb von Sekunden gepostet :)

aditsu

Dies ist zwar länger als die Ruby-Lösung, aber meines Erachtens entspricht es den Problemkriterien "in angemessener Zeit und bei angemessenen Umzügen" besser . Ich würde trotzdem gerne eine Lösung sehen, die im Durchschnitt unter ~ 50 Zügen liegt.

Primo

@primo Danke :) Mein ursprünglicher Code bewegte sich durchschnittlich über 50, für unter 50 brauchst du entweder mehr (Würfel-) Algorithmen oder einen anderen Ansatz wie die Methode von Thistlethwaite. Die Effizienz (bei der Anzahl der Züge) ist jedoch nicht sehr gut mit dem Golfen vereinbar. Wie auch immer, für alternative Lösungen schauen Sie sich die Gewinner von Tomas Rokickis Wettbewerb an.

Aditsu

Python 1166 Bytes

Aus Gründen der Lesbarkeit wurde eine beträchtliche Menge an Leerzeichen gelassen. Die Größe wird nach dem Entfernen dieser Leerzeichen gemessen und das Ändern von verschiedenen Einrückungen zu Tab, Tab Space, Tab Tabetc. Ich habe auch alle Golf vermieden , das die Leistung zu stark beeinträchtigt.

T=[]
S=[0]*20,'QTRXadbhEIFJUVZYeijf',0
I='FBRLUD'

G=[(~i%8,i/8-4)for i in map(ord,'ouf|/[bPcU`Dkqbx-Y:(+=P4cyrh=I;-(:R6')]
R=range

def M(o,s,p):
 z=~p/2%-3;k=1
 for i,j in G[p::6]:i*=k;j*=k;o[i],o[j]=o[j]-z,o[i]+z;s[i],s[j]=s[j],s[i];k=-k

N=lambda p:sum([i<<i for i in R(4)for j in R(i)if p[j]<p[i]])

def H(i,t,s,n=0,d=()):
 if i>4:n=N(s[2-i::2]+s[7+i::2])*84+N(s[i&1::2])*6+divmod(N(s[8:]),24)[i&1]
 elif i>3:
  for j in s:l='UZifVYje'.find(j);t[l]=i;d+=(l-4,)[l<4:];n-=~i<<i;i+=l<4
  n+=N([t[j]^t[d[3]]for j in d])
 elif i>1:
  for j in s:n+=n+[j<'K',j in'QRab'][i&1]
 for j in t[13*i:][:11]:n+=j%(2+i)-n*~i
 return n

def P(i,m,t,s,l=''):
 for j in~-i,i:
  if T[j][H(j,t,s)]<m:return
 if~m<0:print l;return t,s
 for p in R(6):
  u=t[:];v=s[:]
  for n in 1,2,3:
   M(u,v,p);r=p<n%2*i or P(i,m+1,u,v,l+I[p]+`n`)
   if r>1:return r

s=raw_input().split()
o=[-(p[-1]in'UD')or p[0]in'RL'or p[1]in'UD'for p in s]
s=[chr(64+sum(1<<I.find(a)for a in x))for x in s]

for i in R(7):
 m=0;C={};T+=C,;x=[S]
 for j,k,d in x:
  h=H(i,j,k)
  for p in R(C.get(h,6)):
   C[h]=d;u=j[:];v=list(k)
   for n in i,0,i:M(u,v,p);x+=[(u[:],v[:],d-1)]*(p|1>n)
 if~i&1:
  while[]>d:d=P(i,m,o,s);m-=1
  o,s=d

Beispielnutzung:

$ more in.dat
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

$ pypy rubiks.py < in.dat
F3R1U3D3B1
F2R1F2R3F2U1R1L1
R2U3F2U3F2U1R2U3R2U1
F2L2B2R2U2L2D2L2F2

Dies ist eine Implementierung des Thistlethwaite-Algorithmus, bei der für jeden Schritt eine IDA * -Suche verwendet wird. Da alle heuristischen Tabellen im laufenden Betrieb berechnet werden müssen, wurden mehrere Kompromisse eingegangen, wobei eine Heuristik normalerweise in zwei oder mehr Teile gleicher Größe aufgeteilt wurde. Dies beschleunigt die Berechnung der heuristischen Tabellen um ein Vielfaches und verlangsamt die Suchphase, normalerweise nur geringfügig. Dies kann jedoch in Abhängigkeit vom ursprünglichen Cube-Status erheblich sein.

Variablenindex

T - die heuristische Haupttabelle.
S- ein gelöster Würfelzustand. Jedes einzelne Stück wird als Bitmaske gespeichert und als Zeichen dargestellt. Ein gelöster Orientierungsvektor ist als der Nullvektor definiert.
I - die verschiedenen Wendungen in der Reihenfolge, in der sie aus dem Suchfeld entfernt werden.
G- die Gruppen für Twist-Permutationen, die als auszutauschende Paare gespeichert sind. Jedes Byte in der komprimierten Zeichenfolge codiert für ein Paar. Für jede Drehung sind sechs Tauschvorgänge erforderlich: drei für den Kantenzyklus und drei für den Eckenzyklus. Die komprimierte Zeichenfolge enthält nur druckbare ASCII-Zeichen (Zeichen 32 bis 126).
M - eine Funktion, die einen Zug ausführt, gegeben von G.
N - wandelt eine Permutation von vier Objekten zu Kodierungszwecken in eine Zahl um.
H - berechnet den heuristischen Wert für den angegebenen Würfelstatus, der zum Nachschlagen der Verschiebungstiefe von T verwendet wird.
P - Führen Sie eine Suche in einer einzelnen Tiefe einer einzelnen Phase des Algorithmus durch.
s - Der Permutationsstatus des Eingabewürfels.
o - Der Orientierungsvektor des Eingabewürfels.

Performance

Unter Verwendung des Datensatzes von Tomas Rokicki ergab dieses Skript einen Durchschnitt von 16,02 Drehungen pro Lösung (maximal 35) mit einer durchschnittlichen Zeit von 472 ms (i5-3330 CPU @ 3,0 Ghz, PyPy 1.9.0). Die minimale Lösungszeit betrug 233 ms mit einem Maximum von 2,97 s, Standardabweichung 0,488. Nach den Bewertungsrichtlinien des Wettbewerbs (Leerraum wird nicht gezählt, Schlüsselwörter und Bezeichner zählen bei einer Länge von 870 als ein Byte) hätte die Gesamtpunktzahl 13.549 betragen.

In den letzten 46 Fällen (den Zufallszuständen) wurden durchschnittlich 30,83 Drehungen pro Lösung mit einer durchschnittlichen Zeit von 721 ms ermittelt.

Anmerkungen zum Thistlethwaite-Algorithmus

Hier finden Sie eine kurze Erklärung für alle, die eine Implementierung des Thistlethwaite-Algorithmus versuchen möchten .

Der Algorithmus arbeitet nach einem sehr einfachen Lösungsprinzip zur Raumreduzierung. Das heißt, reduzieren Sie den Würfel auf einen Zustand, in dem eine Teilmenge von Drehungen nicht erforderlich ist, um ihn zu lösen, reduzieren Sie ihn auf einen kleineren Lösungsraum und lösen Sie den Rest mit nur den wenigen verbleibenden Drehungen.

Thistlethwaite schlug ursprünglich vor <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. Angesichts des Eingabeformats halte ich es jedoch für einfacher, zuerst auf <L,R,F2,B2,U,D>(keine Vierteldrehung Foder B) zu reduzieren und dann, <L2,R2,F2,B2,U,D>bevor schließlich der halbe Drehungszustand erreicht wird. Anstatt genau zu erklären, warum dies der Fall ist, wird es meiner Meinung nach offensichtlich, nachdem die Kriterien für jeden Staat definiert wurden.

`<L,R,F,B,U,D>` ⇒ `<L,R,F2,B2,U,D>`

Um zu beseitigen Fund BVierteldrehungen, nur die Kanten müssen korrekt ausgerichtet sein. Gilles Roux hat auf seiner Website eine sehr gute Erklärung dafür, was "richtige" und "falsche" Orientierung ist, also überlasse ich die Erklärung ihm. Aber im Grunde (und das ist , warum dieses Eingabeformat so günstig ist Fund BBeseitigung), wird eine Kante Cubie richtig ausgerichtet , wenn sie die folgende Regex übereinstimmt: [^RL][^UD]. Eine korrekte Ausrichtung wird in der Regel mit 0und falsch mit gekennzeichnet 1. Grundsätzlich können Uund DAufkleber möglicherweise nicht auf den Roder LFlächen oder an den Kanten der beliebigen Uoder DKantenwürfel erscheinen, oder sie können nicht an Ort und Stelle verschoben werden, ohne dass ein Foder erforderlich istB Vierteldrehung.

`<L,R,F2,B2,U,D>` ⇒ `<L2,R2,F2,B2,U,D>`

Zwei Kriterien hier. Zunächst müssen alle Ecken richtig ausgerichtet werden, und die zweite, die jeweils die für die Mittelschicht Cubies ( FR, FL, BR, BL) muss irgendwo in der Mittelschicht sein. Eine Eckausrichtung ist aufgrund des Eingabeformats sehr einfach zu definieren: die Position des ersten Uoder D. Hat zum Beispiel URBOrientierung 0(richtig orientiert), LDFhat Orientierung 1und LFUhat Orientierung 2.

`<L2,R2,F2,B2,U,D>` ⇒ `<L2,R2,F2,B2,U2,D2>`

Hier gelten folgende Kriterien: Jedes Gesicht darf nur Aufkleber von seinem Gesicht oder von dem Gesicht direkt gegenüber enthalten. Zum Beispiel kann es auf dem UGesicht nur Uund DAufkleber geben, auf dem RGesicht nur Rund LAufkleber geben, auf dem FGesicht nur Fund BAufkleber usw. Der einfachste Weg, dies sicherzustellen, besteht darin, zu überprüfen, ob sich jedes Kantenstück in befindet seine "Scheibe" und jedes Eckstück in seiner "Umlaufbahn". Zusätzlich muss auf die Kanten-Ecken-Parität geachtet werden. Wenn Sie jedoch nur auf Eckparität prüfen, ist auch die Kantenparität garantiert und umgekehrt.

Wie Drehungen die Orientierung beeinflussen

Uund DVerdrehungen wirken sich weder auf die Kantenausrichtung noch auf die Eckenausrichtung aus. Die Teile können direkt getauscht werden, ohne den Ausrichtungsvektor zu aktualisieren.

Rund LDrehungen wirken sich nicht auf die Kantenausrichtung aus, wirken sich jedoch auf die Eckenausrichtung aus. Je nachdem, wie Sie Ihren Zyklus definieren, ist die Änderung der Eckenausrichtung entweder +1, +2, +1, +2oder vollständig +2, +1, +2, +1modulo 3. Es ist zu beachten, dass R2und L2Drehungen die Eckenorientierung nicht beeinflussen, da +1+2Null-Modulo ist 3, wie es ist +2+1.

Fund Bwirken sich sowohl auf die Kantenorientierungen als auch auf die Eckenorientierungen aus. Kantenorientierungen werden zu +1, +1, +1, +1(Mod 2), und Eckenorientierungen sind dieselben wie für Rund L. Beachten Sie dies F2und B2beeinflussen Sie weder die Kantenausrichtungen noch die Eckenausrichtungen.

primo
quelle

Großartige Zusammenfassung. Haben Sie von Kociembas Algorithmus gehört?

Meilen

Ich habe. Im Prinzip ist es der gleiche Algorithmus, außer dass er anstelle von vier Phasen nur zwei hat: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. Es sind maximal 29 Drehungen erforderlich, um einen Würfel zu lösen (anstelle von 52 für Thistlethwaite), aber es sind auch sehr große Nachschlagetabellen erforderlich, deren Generierung "on the fly" unpraktisch wäre.

Primo

@ P0w das eingabeformat ist etwas verwirrend, ich vermute du hast da einen fehler. Jeder Fall, den ich überprüft habe, führt zu einer Lösung.

Primo

@primo Würde es Ihnen etwas ausmachen, einen Link zum Code ohne Golf zu veröffentlichen, wenn Sie ihn haben?

Bilow

Ruby, 742 Zeichen

r=->y{y.split.map{|x|[*x.chars]}}
G=r['UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR']
o=r[gets]
x=[];[[%w{U UU UUU L LL LLL}+D=%w{D DD DDD},0],[%w{FDFFF RFDFFFRRR}+D,12],[%w{DDDRRRDRDFDDDFFF DLDDDLLLDDDFFFDF}+D,8],[%w{DFLDLLLDDDFFF RDUUUFDUUULDUUUBDUUU}+D,4],[%w{LDDDRRRDLLLDDDRD RRRDLDDDRDLLLDDD LFFFLLLFLFFFLLLF},16]].map{|q,y|x+=[*y..y+3]
3.times{q.map{|e|q|=[e.tr('LFRB','FRBL')]}}
w=->u{x.count{|t|u[t]!=G[t]}}
s=w[o]
(c=(0..rand(12)).map{q.sample}*''
z=o
c.chars{|m|z="=$'*:036\".?BOHKVGRWZ!$@*-0C69<4(E\\INQTMX!$'B-03<9*?6EHYLQPUZ!9'*-?360<$BSFKN[TWJ$'*!-0369<?BHKNEQTWZ!$'*6-039<?BEHKNTWZQ"[20*('FBLRUD'=~/#{m}/),20].bytes.map{|e|z[e/3-11].rotate e%3}}
t=w[z]
(c.chars{|e|$><<e<<'1 '};o=z;s=t)if s>t
)until s<1}

Der obige Ruby-Code ist noch nicht vollständig golfen. Es gibt immer noch Möglichkeiten, den Code weiter zu verbessern (aber es reicht schon als Starter).

Der Würfel wird schichtweise aufgelöst, es wird jedoch kein spezifischer Algorithmus verwendet, sondern es werden zufällige Abfolgen von Zügen ausgeführt, bis der Würfel aufgelöst ist.

Aufgrund der Wahrscheinlichkeit kann es manchmal länger als 5 Sekunden dauern, bis der Würfel gelöst ist. In seltenen Fällen sind mehr als 1000 Züge erforderlich.

Beispielausgabe (für Eingabe 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU') ist 757 Züge:

F1 R1 R1 F1 F1 F1 R1 R1 R1 L1 L1 L1 F1 D1 L1 L1 D1 D1 D1 D1 L1 B1 D1 
B1 B1 B1 L1 L1 L1 F1 D1 F1 F1 F1 L1 D1 L1 L1 L1 B1 D1 B1 B1 B1 R1 D1 
R1 R1 R1 L1 B1 D1 B1 B1 B1 L1 L1 L1 D1 D1 B1 D1 B1 B1 B1 B1 D1 B1 B1 
B1 L1 D1 L1 L1 L1 D1 D1 D1 D1 D1 R1 D1 R1 R1 R1 R1 F1 D1 F1 F1 F1 R1 
R1 R1 R1 D1 R1 R1 R1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 D1 D1 L1 D1 L1 
L1 L1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 L1 D1 L1 L1 L1 D1 L1 D1 L1 L1 
L1 L1 D1 L1 L1 L1 D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1 
L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 D1 D1 B1 B1 B1 D1 B1 
D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1 R1 D1 D1 D1 R1 R1 
R1 D1 B1 D1 D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 B1 D1 D1 D1 B1 
B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 F1 D1 D1 D1 F1 F1 F1 D1 D1 D1 R1 
R1 R1 D1 R1 D1 D1 D1 R1 R1 R1 D1 R1 D1 F1 D1 D1 D1 F1 F1 F1 D1 B1 D1 
D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 
D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 
L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 F1 D1 D1 D1 
F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 R1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 
D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 
D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 R1 F1 
D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 F1 L1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 
D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 
B1 B1 B1 D1 D1 D1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 D1 D1 D1 
D1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 L1 
D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1 D1 D1 D1 F1 F1 F1 D1 B1 B1 B1 D1 
D1 D1 F1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 L1 D1 D1 
D1 R1 R1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1 
R1 R1 F1 F1 F1 R1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1 
B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 F1 R1 R1 R1 F1 F1 F1 R1 
F1 R1 R1 R1 F1 F1 F1 R1 F1 D1 D1 D1 B1 B1 B1 D1 F1 F1 F1 D1 D1 D1 B1 
D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1 R1 R1 F1 F1 F1 R1 F1 F1 F1 D1 B1 D1 
D1 D1 F1 D1 B1 B1 B1 D1 D1 D1 R1 D1 D1 D1 L1 L1 L1 D1 R1 R1 R1 D1 D1 
D1 L1 D1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 D1 D1 
L1 L1 L1 D1 R1 R1 R1 D1 D1 D1 L1 D1 F1 F1 F1 D1 B1 D1 D1 D1 F1 D1 B1 
B1 B1 D1 D1 D1 L1 L1 L1 D1 R1 D1 D1 D1 L1 D1 R1 R1 R1 D1 D1 D1

Es ist möglich, die Anzahl der Züge erheblich zu reduzieren, wenn die gleichen Züge in Gruppen zusammengefasst werden. Daher kann man die Ausgabe gerne ersetzen

(c.gsub(/(.)\1*/){j=$&.size%4;$><<$1<<j<<' 'if j>0};o=z;s=t)if s>t

Howard
quelle

Schön, aber manchmal dauert es mehr als 20 Sekunden auf meinem Computer, in einem Fall endete es in 48,7 Sekunden

@aditsu Ja. Es hängt aber auch stark davon ab, welchen Ruby-Interpreter Sie verwenden. Auf meinem Computer dauert es normalerweise weniger als 5 Sekunden.

Howard

Ich verwende derzeit Ruby 1.9.3_p392, es dauert oft weniger als 5 Sekunden, aber ich kann nicht "normalerweise" sagen

aditsu

Versuchen Sie diese Eingabe:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR

Aditsu

Eine Bitte: Könnten Sie Sequenzen wie U1 U1 U1in einer einzigen zusammenfassen U3?

Primo

Löse Rubiks Würfel

Antworten:

C ++ - 1123

Python 1166 Bytes

Variablenindex

Performance

Anmerkungen zum Thistlethwaite-Algorithmus

<L,R,F,B,U,D> ⇒ <L,R,F2,B2,U,D>

<L,R,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U,D>

<L2,R2,F2,B2,U,D> ⇒ <L2,R2,F2,B2,U2,D2>

Wie Drehungen die Orientierung beeinflussen

Ruby, 742 Zeichen

`<L,R,F,B,U,D>` ⇒ `<L,R,F2,B2,U,D>`

`<L,R,F2,B2,U,D>` ⇒ `<L2,R2,F2,B2,U,D>`

`<L2,R2,F2,B2,U,D>` ⇒ `<L2,R2,F2,B2,U2,D2>`