Résoudre le cube de Rubik

Ecrivez le programme le plus court qui résout le cube de Rubik (3 * 3 * 3) dans un délai raisonnable et se déplace (par exemple, maximum 5 secondes sur votre machine et moins de 1 000 déplacements).

L'entrée est au format:

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

(cette entrée particulière représente le cube résolu).
Les 12 premières chaînes de 2 caractères sont les arêtes des positions UF, UR, ... BL (U = haut, F = avant, R = droite, B = arrière, L = gauche, D = bas), puis les 8 suivantes Les chaînes de 3 caractères sont les coins des positions UFR, URB, ... DBR.

La sortie devrait donner une séquence de mouvements dans ce format:

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

Où D1 ou D + représente une rotation de 90 degrés de la face D (vers le bas) dans le sens des aiguilles d'une montre, L2 d'une rotation de 180 degrés de la face L, U3 ou U- représente une rotation de 90 degrés de la face U dans le sens inverse des aiguilles d'une montre.
Les lettres ne sont pas sensibles à la casse et les espaces sont facultatifs.

Par exemple, la sortie ci-dessus est correcte pour l'entrée suivante:

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

Pour plus de détails, veuillez vous reporter au concours de cube de Tomas Rokicki , sauf que la notation se fera directement par la taille du fichier, comme un problème de golf classique. Un testeur en ligne est également inclus.

Pour référence, la solution la plus courte déjà écrite est la dernière entrée dans la liste des gagnants du concours de cube

Pour ceux qui ont du mal à visualiser le format de mise en page:

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
la source

Les langages autres que C / C ++ / Java / Perl / Python sont-ils acceptés?

Egor Skriptunoff

@EgorSkriptunoff Ici, oui, utilisez ce que vous voulez, mais pas de bibliothèques de résolution de cubes.

Aditsu

Et que dire de la notation? Score de code-golf habituel (octets dans le programme) ou score complexe comme dans le concours de 2004?

Egor Skriptunoff

@jdstankosky, j'ai ajouté un diagramme.

Peter Taylor

Sommes-nous autorisés à retirer les autocollants et à les déplacer?

Iszi

Réponses:

C ++ - 1123

Comme personne n’avait posté de réponse à ce jour, j’ai décidé de simplifier et de mettre au golf ma solution de 2004. C'est encore loin derrière le plus court que j'ai mentionné dans la question.

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

Ce n'est pas aléatoire, mais cela ne se fait pas non plus directement. Il résout les bords en premier, puis les coins. À chaque étape, il essaie diverses combinaisons allant jusqu'à 4 algorithmes et des tours de visage simples (séquentiellement, pas au hasard), jusqu'à ce qu'il trouve une amélioration du nombre de morceaux résolus, puis se répète jusqu'à ce qu'il soit résolu. Il utilise 2 algorithmes pour les arêtes et 2 pour les angles, traduits dans toutes les positions du cube.

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

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 coups, 0,3 sec ici)

Aditsu
la source

Que savez-vous ... une autre réponse a été postée en quelques secondes :)

Aditsu

Bien que cela soit plus long que la solution Ruby, je pense que cela correspond mieux au critère du problème "dans un délai raisonnable et évolue". J'aimerais quand même voir une solution qui fait en moyenne moins de 50 coups.

Primo

@primo Merci :) Mon code original comptait en moyenne plus de 50 mouvements. Pour les moins de 50 ans, je pense que vous avez besoin de plus d'algorithmes (en cube) ou d'une approche différente telle que la méthode de Thistlethwaite. Cependant, l'efficacité (en nombre de coups) n'est pas très compatible avec le golf. Quoi qu'il en soit, pour des solutions alternatives, consultez les gagnants du concours de Tomas Rokicki.

Aditsu

Python 1166 octets

Une quantité considérable d’espaces a été laissée pour des raisons de lisibilité. La taille est mesurée après suppression de cette espaces, et en changeant différents niveaux d'indentation à Tab, Tab Space, Tab Tab, etc. J'ai aussi évité tout le golf qui a affecté la performance de manière trop drastique.

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

Exemple d'utilisation:

$ 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

Ceci est une implémentation de l'algorithme de Thistlethwaite, utilisant une recherche IDA * à résoudre pour chaque étape. Étant donné que toutes les tables heuristiques doivent être calculées à la volée, plusieurs compromis ont été faits, divisant généralement une heuristique en deux ou plusieurs parties de taille sensiblement égale. Cela accélère le calcul des tables heuristiques des centaines de fois, tout en ralentissant légèrement la phase de recherche, mais il peut être important en fonction de l'état initial du cube.

Indice variable

T - la table heuristique principale.
S- un état de cube résolu. Chaque pièce individuelle est stockée sous forme de masque de bits, représenté par un caractère. Un vecteur d'orientation résolu est défini comme le vecteur zéro.
I - les différents rebondissements, dans l'ordre dans lequel ils sont éliminés de l'espace de recherche.
G- les groupes de permutations de torsion, stockés sous forme de paires à échanger. Chaque octet de la chaîne compressée code pour une paire. Chaque torsion nécessite six échanges: trois pour le cycle de bord et trois pour le cycle de coin. La chaîne compressée contient uniquement des caractères ASCII imprimables (caractères 32 à 126).
M - une fonction qui effectue un mouvement, donné par G.
N - convertit une permutation de quatre objets en un nombre, à des fins de codage.
H - calcule la valeur heuristique pour l'état de cube donné, utilisé pour rechercher la profondeur de déplacement à partir de T.
P - effectuer une recherche à une profondeur unique d'une phase de l'algorithme.
s - l'état de permutation du cube en entrée.
o - le vecteur d'orientation du cube en entrée.

Performance

En utilisant le jeu de données de Tomas Rokicki , ce script a enregistré une moyenne de 16,02 twists par résolution (maximum 35), avec un temps moyen de 472 ms (i5-3330 CPU @ 3.0 Ghz, PyPy 1.9.0). Le temps de résolution minimum était de 233 ms avec un maximum de 2,97 secondes, écart type de 0,488. En utilisant les directives de notation du concours (les espaces ne sont pas comptés, les mots-clés et les identifiants comptent pour un octet pour une longueur de 870), le score total aurait été de 13 549.

Pour les 46 derniers cas (les états aléatoires), la moyenne est de 30,83 torsions par résolution, avec un temps moyen de 721 ms.

Notes sur l'algorithme de Thistlethwaite

Pour le bénéfice de tous ceux qui voudraient tenter de mettre en œuvre l'algorithme de Thistlethwaite , voici une brève explication.

L'algorithme fonctionne sur un principe de réduction de l'espace de solution très simple. Autrement dit, réduisez le cube à un état dans lequel un sous-ensemble de torsions n'est pas nécessaire pour le résoudre, réduisez-le à un espace de solution plus petit, puis résolvez le reste en utilisant uniquement les quelques torsions restantes.

Thistlethwaite suggéré à l'origine <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. Cependant, étant donné le format d'entrée, je pense qu'il est plus facile de réduire d'abord à <L,R,F2,B2,U,D>(pas de quart de tour Fou B), et ensuite <L2,R2,F2,B2,U,D>avant d'atteindre l'état de demi-tour. Au lieu d’expliquer exactement pourquoi, je pense que ce sera évident après la définition des critères pour chaque État.

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

Pour éliminer Fet Bquart de tour, seules les arêtes doivent être correctement orientées. Gilles Roux a une très bonne explication sur son site de ce qu'est une orientation "correcte" et "incorrecte", je vais donc lui laisser l'explication. Mais au fond, (ce qui est la raison pour laquelle ce format d'entrée est donc propice au Fet Bélimination), un Cubie de bord est orienté correctement si elle correspond à l'expression rationnelle suivante: [^RL][^UD]. Une orientation correcte est généralement indiquée avec un 0et incorrect avec 1. Fondamentalement Uet Dautocollants peuvent ne pas apparaître sur les Rou Lfaces, ou sur les bords des tout Uou Dbord petits cubes, ou ils ne peuvent pas être déplacés en place sans avoir besoin d' un FouB quart de tour.

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

Deux critères ici. Tout d' abord, tous les coins doivent être orientés correctement, et d' autre part, chacun des pour petits cubes de couche du milieu ( FR, FL, BR, BL) doit être quelque part dans la couche intermédiaire. Une orientation de coin est très simplement définie en fonction du format d'entrée: la position du premier Uou D. Par exemple, URBa une orientation 0(correctement orientée), LDFa une orientation 1et LFUa une orientation 2.

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

Les critères sont les suivants: chaque face ne peut contenir que des autocollants collés sur sa face ou directement sur la face opposée. Par exemple, sur le Uvisage , il ne peut être Uet Dautocollants, sur le Rvisage , il ne peut y avoir RetL autocollants, sur le Fvisage , il peut seulement être Fet Bautocollants, etc. La façon d' y parvenir est plus facile de vérifier si chaque pièce de bord est en sa "tranche" et chaque coin dans son "orbite". De plus, il faut faire attention à la parité des bords. Bien que, si vous ne vérifiez que la parité d'angle, la parité de bord est également garantie, et inversement.

Comment les rebondissements affectent l'orientation

Uet les Dtorsions n’affectent ni l’orientation des bords, ni l’angle des angles. Les pièces peuvent être échangées directement sans mettre à jour le vecteur d’orientation.

Ret les Ltorsions n’affectent pas l’orientation des bords, mais l’orientation des coins. Selon la façon dont vous définissez votre cycle, le changement d'orientation des coins sera soit modulaire, +1, +2, +1, +2soit +2, +1, +2, +1modulaire 3. Notez que R2et L2torsions ne touchent pas l'orientation du coin, comme +1+2est égal à zéro modulo 3, comme +2+1.

Fet Baffecte à la fois les orientations des bords et les orientations des coins. Les orientations des bords deviennent +1, +1, +1, +1(mod 2) et les orientations des coins sont les mêmes que pour Ret L. Notez que F2et B2affectent ni les orientations de bord, ni les orientations d'angle.

primo
la source

Grande écriture. Avez-vous entendu parler de l'algorithme de Kociemba?

miles

J'ai. En principe, c'est le même algorithme, sauf qu'au lieu de quatre phases, il n'en a que deux: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. La résolution d'un cube nécessite au maximum 29 torsions (au lieu de 52 pour celles de Thistlethwaite), mais elle nécessite également de très grandes tables de consultation, ce qui ne serait pas pratique pour générer "à la volée".

primo

@ P0W le format d'entrée est un peu déroutant, je suppose que vous pouvez y avoir une erreur. Chaque cas que j'ai vérifié aboutit à une solution.

primo

@primo Souhaitez-vous publier un lien vers le code sans golf si vous en avez un?

Bilow

Ruby, 742 caractères

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}

Le code ruby ci-dessus n'est pas encore complètement joué au golf. Il reste encore des possibilités d’améliorer le code (mais c’est déjà suffisant en tant que démarreur).

Il résout le cube couche par couche mais n'utilise aucun algorithme spécifique, mais effectue des séquences aléatoires de déplacements jusqu'à la résolution du cube.

En raison de la nature probabiliste, la résolution du cube peut prendre parfois plus de 5 secondes et, dans de rares cas, plus de 1 000 déplacements sont nécessaires.

Exemple de sortie (pour l'entrée 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU') est de 757 mouvements:

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

Il est possible de réduire considérablement le nombre de mouvements si les mêmes mouvements sont regroupés. Par conséquent, on peut remplacer la sortie comme

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

Howard
la source

Bien, mais parfois cela prend plus de 20 secondes sur mon ordinateur. Dans un cas, cela s'est terminé en 48,7 secondes

Aditsu

@aditsu Oui. Mais cela dépend aussi fortement de l’interprète Ruby que vous utilisez. Sur ma machine, cela prend généralement moins de 5 secondes.

Howard

J'utilise actuellement ruby 1.9.3_p392, cela prend souvent moins de 5 secondes, mais je ne peux pas dire "généralement"

Aditsu

Essayez cette entrée:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR

Aditsu

Une demande: pourriez-vous consolider des séquences comme U1 U1 U1en une seule U3?

Primo

Résoudre le cube de Rubik

Réponses:

C ++ - 1123

Python 1166 octets

Indice variable

Performance

Notes sur l'algorithme de Thistlethwaite

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

Comment les rebondissements affectent l'orientation

Ruby, 742 caractères

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