Resuelve el cubo de Rubik

Escriba el programa más corto que resuelva el cubo de Rubik (3 * 3 * 3) dentro de un tiempo razonable y se mueva (digamos, máximo 5 segundos en su máquina y menos de 1000 movimientos).

La entrada está en el formato:

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

(esta entrada particular representa el cubo resuelto).
Las primeras 12 cadenas de 2 caracteres son los bordes en las posiciones UF, UR, ... BL (U = arriba, F = adelante, R = derecha, B = atrás, L = izquierda, D = abajo), luego las siguientes 8 Las cadenas de 3 caracteres son las esquinas en las posiciones UFR, URB, ... DBR.

La salida debe dar una secuencia de movimientos en este formato:

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

Donde D1 o D + representa girar la cara D (hacia abajo) en sentido horario 90 grados, L2 está girando la cara L 180 grados, U3 o U- representa girar la cara U 90 grados en sentido antihorario.
Las letras no distinguen entre mayúsculas y minúsculas y los espacios son opcionales.

Por ejemplo, la salida anterior es correcta para la siguiente entrada:

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

Para obtener más detalles, consulte el concurso de cubos de Tomas Rokicki , excepto que la puntuación se realizará directamente por tamaño de archivo como un problema normal de golf de código. También se incluye un probador en línea .

Como referencia, la solución más corta ya escrita es la última entrada en la lista de ganadores del concurso de cubos.

Para aquellos que luchan por visualizar el formato de diseño:

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
fuente

¿Se aceptan lenguajes distintos de C / C ++ / Java / Perl / Python?

Egor Skriptunoff

@EgorSkriptunoff Aquí sí, usa lo que quieras, simplemente no hay bibliotecas para resolver cubos.

aditsu

¿Y qué hay de anotar? ¿Puntuación de código de golf habitual (bytes en el programa) o puntuación compleja como en el concurso de 2004?

Egor Skriptunoff

@jdstankosky, agregué un diagrama.

Peter Taylor

¿Se nos permite sacar las pegatinas y moverlas?

Iszi

Respuestas:

C ++ - 1123

Como nadie ha publicado ninguna respuesta hasta el momento, decidí simplificar y desarrollar mi solución 2004. Todavía está muy por detrás del más corto que mencioné en la pregunta.

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

No es aleatorio, pero tampoco procede directamente. Primero resuelve los bordes, luego las esquinas. En cada paso, prueba varias combinaciones de hasta 4 algoritmos y giros de caras simples (secuencialmente, no al azar), hasta que encuentra una mejora en el número de piezas resueltas, luego se repite hasta que se resuelva. Utiliza 2 algoritmos para bordes y 2 para esquinas, traducidos a todas las posiciones del cubo.

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

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 movimientos, 0.3 segundos aquí)

aditsu
fuente

¿Qué sabes ... otra respuesta fue publicada en segundos :)

aditsu

Aunque esto es más largo que la solución Ruby, creo que se ajusta mejor a los criterios del problema "dentro de un tiempo razonable y se mueve". Sin embargo, todavía me gustaría ver una solución que promedia menos de ~ 50 movimientos.

primo

@primo Gracias :) Mi código original promedió más de 50 movimientos, por menos de 50 creo que necesitas más algoritmos (cubos) o un enfoque diferente, como el método de Thistlethwaite. Sin embargo, la eficiencia (en no. De movimientos) no es muy compatible con el golf. De todos modos, para obtener soluciones alternativas, consulte a los ganadores del concurso de Tomas Rokicki.

aditsu

Python 1166 bytes

Se ha dejado una cantidad considerable de espacio en blanco en aras de la legibilidad. El tamaño se mide después de la eliminación de este espacio en blanco, y el cambio de varios niveles de sangría a Tab, Tab Space, Tab Tab, etc. También he evitado todo el golf que afectó el rendimiento demasiado drástica.

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

Uso de la muestra:

$ 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

Esta es una implementación del Algoritmo de Thistlethwaite, usando una búsqueda IDA * para resolver cada paso. Debido a que todas las tablas heurísticas deben calcularse sobre la marcha, se han hecho varios compromisos, generalmente dividiendo una heurística en dos o más partes de tamaño bastante igual. Esto hace que el cálculo de las tablas heurísticas sea cientos de veces más rápido, mientras que ralentiza la fase de búsqueda, generalmente solo un poco, pero puede ser significativo dependiendo del estado inicial del cubo.

Índice variable

T - La tabla heurística principal.
S- un estado de cubo resuelto. Cada pieza individual se almacena como una máscara de bits, representada como un personaje. Un vector de orientación resuelto se define como el vector cero.
I - los diversos giros, en el orden en que se eliminan del espacio de búsqueda.
G- los grupos para permutaciones de torsión, almacenados como pares para ser intercambiados. Cada byte en la cadena comprimida codifica para un par. Cada giro necesita seis intercambios: tres para el ciclo de borde y tres para el ciclo de esquina. La cadena comprimida contiene solo ascii imprimible (caracteres 32 a 126).
M - una función que realiza un movimiento, dada por G.
N - Convierte una permutación de cuatro objetos en un número, con fines de codificación.
H - calcula el valor heurístico para el estado del cubo dado, utilizado para buscar profundidad de movimiento desde T.
P - realice una búsqueda a una sola profundidad de una sola fase del algoritmo.
s - el estado de permutación del cubo de entrada.
o - el vector de orientación del cubo de entrada.

Actuación

Utilizando el conjunto de datos de Tomas Rokicki , este script promedió 16.02 giros por resolución (máximo 35), con un tiempo promedio de 472 ms (CPU i5-3330 a 3.0 Ghz, PyPy 1.9.0). El tiempo mínimo de resolución fue de 233 ms con un máximo de 2.97 s, desviación estándar de 0.488. Utilizando las pautas de puntuación del concurso (no se cuentan los espacios en blanco, las palabras clave y los identificadores cuentan como un byte para una longitud de 870), la puntuación general habría sido 13.549.

Para los últimos 46 casos (los estados aleatorios), promedió 30.83 giros por resolución, con un tiempo promedio de 721 ms.

Notas sobre el algoritmo de Thistlethwaite

Para el beneficio de cualquiera que quiera intentar una implementación del Algoritmo de Thistlethwaite , aquí hay una breve explicación.

El algoritmo funciona en un principio de reducción de espacio de solución muy simple. Es decir, reduzca el cubo a un estado en el que no sea necesario un subconjunto de giros para resolverlo, reduzca a un espacio de solución más pequeño y luego resuelva el resto utilizando solo los pocos giros restantes.

Thistlethwaite sugirió originalmente <L,R,F,B,U,D>→ <L,R,F,B,U2,D2>→ <L,R,F2,B2,U2,D2>→ <L2,R2,F2,B2,U2,D2>. Sin embargo, dado el formato de entrada, creo que es más fácil reducir primero a <L,R,F2,B2,U,D>(sin cuarto de vuelta Fo B), y luego <L2,R2,F2,B2,U,D>antes de finalmente alcanzar el estado de media vuelta. En lugar de explicar exactamente por qué esto es así, creo que será evidente después de definir los criterios para cada estado.

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

Para eliminar Fy Bcuartos de vuelta, solo los bordes deben estar orientados correctamente. Gilles Roux tiene una muy buena explicación en su sitio de lo que es la orientación 'correcta' e 'incorrecta', así que le dejaré la explicación. Pero, básicamente, (y esto es por qué este formato de entrada es tan propicio para Fy Beliminación), un borde Cubie está orientado correctamente si coincide con la siguiente expresión regular: [^RL][^UD]. Una orientación correcta generalmente se indica con ay 0incorrecta con 1. Básicamente Uy Dpegatinas pueden no aparecer en las Ro Lcaras, o en los bordes de los alguna Uo Dborde cubitos, o pueden no ser movido en su lugar sin necesidad de una FoB cuarto de giro

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

Dos criterios aquí. En primer lugar, todas las esquinas deben ser orientados correctamente, y segundo, cada uno de los cubitos para la capa media ( FR, FL, BR, BL) deben estar en algún lugar en la capa media. La orientación de una esquina se define de manera muy simple dado el formato de entrada: la posición de la primera Uo D. Por ejemplo, URBtiene orientación 0(correctamente orientada), LDFtiene orientación 1y LFUtiene orientación 2.

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

El criterio aquí es el siguiente: cada cara solo puede contener pegatinas de su cara o de la cara directamente opuesta. Por ejemplo, en la Ucara solo puede haber Uy Dcalcomanías, en la Rcara solo puede haber Ry Lcalcomanías, en la Fcara solo puede haber Fy Bcalcomanías, etc. La forma más fácil de asegurarse de esto es verificar si cada pieza del borde está su 'corte', y cada pieza de esquina en su 'órbita'. Además, uno debe prestar atención a la paridad de esquina de borde. Sin embargo, si marca solo la paridad de esquina, la paridad de borde también está garantizada y viceversa.

Cómo los giros afectan la orientación

Uy los Dgiros no afectan ni a la orientación del borde ni a la orientación de la esquina. Las piezas pueden intercambiarse directamente sin actualizar el vector de orientación.

Ry los Lgiros no afectan la orientación del borde, pero sí afectan la orientación de la esquina. Dependiendo de cómo defina su ciclo, el cambio en la orientación de la esquina será +1, +2, +1, +2o +2, +1, +2, +1, todo el módulo 3. Tenga en cuenta que R2y los L2giros no afectan la orientación de la esquina, como +1+2es el módulo cero 3, como es +2+1.

Fy Bafectan tanto las orientaciones de los bordes como las orientaciones de las esquinas. Las orientaciones de los bordes se vuelven +1, +1, +1, +1(mod 2) y las orientaciones de las esquinas son las mismas que para Ry L. Tenga en cuenta que F2y B2afecta ni las orientaciones de bordes, ni orientaciones de esquina.

primo
fuente

Gran redacción. ¿Has oído hablar del algoritmo de Kociemba?

millas

Yo tengo. En principio, es el mismo algoritmo, excepto que en lugar de cuatro fases, solo tiene dos: <L,R,F,B,U,D>-> <L2,R2,F2,B2,U,D>-> <I>. Requiere un máximo de 29 giros para resolver un cubo (en lugar de 52 para Thistlethwaite's), pero también requiere tablas de búsqueda muy grandes, lo que sería poco práctico para generar 'sobre la marcha'.

primo

@ P0W el formato de entrada es un poco confuso, sospecho que puede tener un error allí. Cada caso que he verificado da como resultado una solución.

primo

@primo ¿Te importaría publicar un enlace al código no golfizado si lo tienes?

Bilow

Rubí, 742 caracteres

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}

El código rubí anterior aún no se ha desarrollado completamente. Todavía hay posibilidades de mejorar aún más el código (pero ya es suficiente como iniciador).

Resuelve el cubo capa por capa, pero no utiliza un algoritmo específico, sino que realiza secuencias aleatorias de movimientos hasta que se resuelve el cubo.

Debido a la naturaleza probabilística, a veces puede llevar más de 5 segundos resolver el cubo y, en casos excepcionales, tomar más de 1000 movimientos.

La salida de ejemplo (para la entrada 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU') es de 757 movimientos:

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 posible reducir el conteo de movimientos considerablemente si los mismos movimientos se agrupan. Por lo tanto, uno puede reemplazar la salida como

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

Howard
fuente

Agradable, pero a veces toma más de 20 segundos en mi computadora, en un caso terminó en 48.7 segundos

aditsu

@aditsu Sí. Pero también depende en gran medida del intérprete de rubíes que utilice. En mi máquina, generalmente toma menos de 5 segundos.

Howard

Actualmente estoy usando rubí 1.9.3_p392, a menudo toma menos de 5 segundos, pero no puedo decir "por lo general"

aditsu

Pruebe esta entrada:FU FR RU BR DB LD LU LB LF RD DF BU FRU BUR FDR DLB DFL LUB FUL DBR

aditsu

Una solicitud: ¿podría consolidar secuencias como U1 U1 U1en una sola U3?

primo

Resuelve el cubo de Rubik

Respuestas:

C ++ - 1123

Python 1166 bytes

Índice variable

Actuación

Notas sobre el algoritmo 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>

Cómo los giros afectan la orientación

Rubí, 742 caracteres

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