Secuencias de identidad en el cubo de Rubik

32

Una secuencia de movimiento es una secuencia de movimientos (giros) en un Cubo de Rubik (para la notación, mira abajo). Además de la secuencia de movimiento vacía, hay muchas otras secuencias de movimiento que no tienen ningún efecto en el cubo. Llamamos a estas secuencias de movimiento secuencias de identidad.

Es obvio determinar algunas de estas secuencias de identidad, como U2 R R' U2o U D2 U' D2. En el primero, se realizan dos movimientos aleatorios U2 Ry luego se deshacen inmediatamente R' U2. El segundo es similar. Los primeros dos movimientos aleatorios U D2y luego se deshacen, pero en orden inverso U' D2. Esto solo funciona, porque el movimiento Uafecta solo a las piezas de la capa superior y el movimiento D2solo afecta a las piezas de la capa inferior. Puede ver una visualización de estas dos secuencias de movimiento.

U2 RR 'U2 U D2 U 'D2

Otras secuencias de identidad pueden no ser obvias en absoluto. Por ejemplo la secuencia R' U' R' F' U F U' R' F R F' U' R U2 R. Es bastante largo, pero tampoco tiene ningún efecto en el cubo.

ingrese la descripción de la imagen aquí

Mover notación

Un movimiento describe el giro de una capa de una de las seis caras del cubo. Un movimiento consiste en una letra que representa la cara seguida de un sufijo opcional que representa el ángulo de giro.

Las letras y sus caras correspondientes son U (arriba - el lado hacia arriba), D (abajo - el lado hacia abajo), R (derecha - el lado hacia la derecha), L (izquierda - el lado hacia la izquierda) , F (Delantero - el lado hacia usted) y B (Atrás - el lado hacia afuera).

Si no hay sufijo, la cara se gira 90 grados en sentido horario, el sufijo 'significa que la cara se gira 90 grados en sentido antihorario y el sufijo 2significa que la cara se gira 180 grados en sentido horario.

Si tiene algún problema con la notación, solo use http://alg.cubing.net , donde puede visualizar tales secuencias de movimiento.

El reto

Su tarea es escribir un programa, que determina si una secuencia de movimiento es una identidad o no.

Puede escribir un programa completo o una función. Debería recibir una cadena que contenga una secuencia de movimiento (los movimientos están separados por espacios) como entrada (a través de STDIN, argumento de línea de comandos, argumento de solicitud o función) y salida (a través del valor de retorno o STDOUT) un valor booleano o un entero correspondiente ( Verdadero - 1 - secuencia de identidad / Falso - 0 - no secuencia de identidad).

Si el sufijo 'crea problemas en su lenguaje de programación, puede usar un símbolo diferente, pero no en el dígito. R F2 U3No se permite.

Este es codegolf, por lo tanto, el código más corto (en bytes) gana.

Casos de prueba

"" -> True
"U2 R R' U2" -> True
"U D2 U' D2" -> True
"U2 R U2 R'" -> False
"R' U' R' F' U F U' R' F R F' U' R U2 R" -> True
"L'" -> False
"B B2 B' B2" -> True
"D D2 D'" -> False
"R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'" -> True
"D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2" -> False
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'" -> True
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'" -> False
"B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2" -> True
"R U2 R' U R' U2 R U2 R U R' U' R' U R U2" -> False
"U F B' R' U F' R U' F' B L U' F L'" -> False
"R2 U' R' U' R U R U R U' R" -> False
"R' F R' B2 R F' R' B2 R2" -> False
code-golf rubiks-cube Jakube
fuente
¿Qué tiene de malo R F2 U3?
John Dvorak
2
Solo quiero asegurarme de que todos tengan las mismas condiciones previas. Si lo permitiera U3, podrías simplemente convertir el sufijo en un dígito.
Jakube
3
Estoy más acostumbrado a la notación que usa T-Top, B-Bottom y P-Posterior (parte posterior). A la gente probablemente solo le gustó ver la secuencia R2 D2.
mbomb007
2
@ mbomb007 Puedo entender T para arriba, pero nunca he visto P para posterior y no entendería su significado si no fuera por tu comentario ...
John Dvorak
2
@ mbomb007 También he visto esa notación, pero no es tan común ni tan antigua como la notación original de Singmaster, y no sé por qué la gente quiere meterse con la original. Aunque David Singmaster (hasta donde yo sé) no lo mencionó, he observado que todas las caras son perfectamente consistentes y sin enfrentamientos si se consideran direcciones en lugar de posiciones. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Level River St el

Respuestas:

14

Haskell, 263 261 247 243 caracteres

c[x]=[x]
c(x:"2")=[x,x]
c(x:_)=[x,x,x]
s!a@[x,y,z]=case s of
 'R'|x>0->[x,-z,y]
 'B'|y>0->[z,y,-x]
 'U'|z>0->[-y,x,z]
 'L'|x<0->[x,z,-y]
 'F'|y<0->[-z,y,x]
 'D'|z<0->[y,-x,z]
 _->a
r=[-2..2]
i=mapM id[r,r,r]
f w=i==foldr(map.(!))i(c=<<words w)

Algoritmo bastante sencillo; cada cubelet está hecho de 1,2,4 u 8 trozos que codifican su posición y orientación; 4 trozos por cubelet de borde, 8 por cubelet de esquina, 7 cubelets son estacionarios.

c c recoge cada palabra de la entrada en una secuencia de turnos CW y !envía cada fragmento de acuerdo con un turno. ies la i posición dentity. fes la principal f unción.

No estoy muy contento con la cfunción homp, pero tampoco puedo encontrar una manera de acortarla (@Nimi lo hizo, sin embargo)

John Dvorak
fuente
¿Qué tal c(x:"2")=[x,x]y c(x:_)=[x,x,x]. Guarda 2 bytes.
nimi
Si usa i=sequence[s,s,s]y cambia todas las tuplas a listas (es decir, se (x,y,z)convierte en [x,y,z]), ahorrará ~ 9 caracteres. En línea ahorra 4 más. Al dejar el _caso, se !salvan otros 11.
MtnViewMark
@MtnViewMark hecho y mejorado i, gracias. No estoy seguro de lo que quiere decir con línea i: tenga en cuenta que aparece dos veces en la definición de f. No estoy seguro de lo que quieres decir con dejar el _estuche: dejarlo _->acompletamente o moverlo a la parte superior produce una excepción de patrón no exhaustiva, y moverlo a la parte superior no guarda ningún personaje de todos modos. Sin embargo, logré guardar 5 caracteres allí.
John Dvorak
Gran solución Revisé todos los casos de prueba.
Jakube
Nuevamente, felicidades por su solución. Desde que presentó el código más corto, recibe la recompensa por valor de 100 reputación.
Jakube
4

Cúbicamente , 6 4 bytes

¶=8%

Yo gano: P

¶=8%
¶     read a string, evaluate as Cubically code
 =8   set notepad to (notepad == 8th face)
   %  print notepad

El bloc de notas se inicializa a cero. La octava "cara" contiene 1 si el cubo no está resuelto y 0 en caso contrario.

Pruébalo en línea!

MD XF
fuente
3
Parece un lenguaje interesante. Pero debido a que el idioma se creó después de que se publicó el desafío, no es elegible para ganar.
Jakube
2
@Jakube Estoy de acuerdo en que no debería aceptarse, solo por el hecho de que es un lenguaje con los cubos de Rubik publicados tan tarde después del desafío y diezmando completamente las otras respuestas. Pero es técnicamente elegible para ganar según meta (la regla de no competencia fue revocada de alguna manera).
MD XF
3

J - 232, 220, 381, 315 296 bytes

Esta solución codifica todas las operaciones como permutaciones de caras y funciona en función del hecho de que todos los giros de caras son realmente iguales, bajo una rotación de todo el cubo.

Editar : un poco más de golf

f=:+/~6&*
r=:4 :'y f&.>(]{^:x~)&.C.;/i.2 4'"0
t=:((r~0),_4<\44#.inv 1478253772705907911x)&C.&.
Y=:(C.(,0 2 r 4 5),;/4 f&i.8)&{^:t
X=:((,1 1 0 2 r 2 4 3 1)C.C.;/0 4 2 5 f i.8)&{^:t
61".@A."1'=: ',"#~6 3$'D0XR1YF1XU2YB3XL3Y'
T=:[:(_2".@}.'(i.48)-:'&(,,[))[:(,'^:',])/&.>@|.&.;:[:''''&=@{.`]},:&'3'

Aparte de los intentos anteriores, esto tiene en cuenta la rotación de esquinas.

fes solo una función auxiliar. rHace la rotación de una cara. una cara se codifica de la siguiente manera:

  1. todas las esquinas en pasos de 6
  2. todos los bordes en pasos de seis

Este orden facilita la codificación de rotaciones y giros. tes un adverbio que tuerce la cara bajo una cierta rotación de cubo, seleccionando la cara.

X y Y son adverbios que toman como argumento izquierdo el número de en esa dirección de todo el cubo.

La siguiente línea define todas las rotaciones: 3 caracteres por rotación: el nombre, el número de rotaciones y la dirección.

La última línea define el verbo de prueba T, convirtiendo 3 y' en notación de potencia, cambiando el orden de operación agregando el vector de prueba y finalmente excitando todo.

Más detalles a petición.

tests =: (] ;. _2) 0 : 0

 U2 R R' U2
 U D2 U' D2
 U2 R2 R'
 R' U' R' F' U F U' R' F R F' U' R U2 R
 L'
 B B2 B' B2
 D D2 D'
 R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'
 D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'
 B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2
 R U2 R' U R' U2 R U2 R U R' U' R' U R U2
 U F B' R' U F' R U' F' B L U' F L'
 R2 U' R' U' R U R U R U' R
 R' F R' B2 R F' R' B2 R2
)
res =: 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
res ([,],:=) T"1 tests NB. passes all tests.
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

NB. some handy display methods:
dispOrig=: (". ;._2) 0 :0
   _   _   _   5  29  11   _   _   _   _   _   _
   _   _   _  47  _1  35   _   _   _   _   _   _
   _   _   _  23  41  17   _   _   _   _   _   _
   3  27   9   0  24   6   1  25   7   2  26   8
  45  _3  33  42  _6  30  43  _5  31  44  _4  32
  21  39  15  18  36  12  19  37  13  20  38  14
   _   _   _   4  28  10   _   _   _   _   _   _
   _   _   _  46  _2  34   _   _   _   _   _   _
   _   _   _  22  40  16   _   _   _   _   _   _
)
ind =: dispOrig i.&, i. 48 NB. indices of i.48 in the original display

disp =: (9 12$(,dispOrig) ind}~ ])
changed =: 1 : '(u ~:&disp ]) i.48' NB. use to debug permutation verbs: L ch
vch =: 1 :'disp  ((]+_*=) u)'
NB. viewmat integration RGB
cm =: 255 * 1 0 0 , 1 1 1, 0 1 0, 1 1 0, 1 0.5 0, 0 0 1,: 0 0 0 NB. colormap
NB. use as:  "cube i. 48" for seeing a nice folded out cube.
cube =: cm viewmat (>&7 + >&15 + >&23 + >&31 + >& 39 + >&47)@|@disp@]
jpjacobs
fuente
11
"ya que los resultados de mi prueba no se corresponden con los dados ..." como en, ¿su solución no funciona? No lo publicaría entonces ...
John Dvorak
Tienes razón. Lo arregló ahora.
jpjacobs
Agregué 4 casos de prueba adicionales. Dos de ellos todavía devuelven el resultado falso. Parece que ignoras la orientación de las esquinas.
Jakube
@jpjacobs Ahora hay una recompensa de 100 repeticiones por la pregunta. ¿Quieres corregir tu código?
Jakube
Voila, hecho. Ahora solo reduciéndolo.
jpjacobs
2

Python 3: 280 caracteres

Este no es un participante en el desafío. Primero porque hice el desafío yo mismo y segundo porque no es mi código. Todos los créditos pertenecen a Stefan Pochmann , quien descubrió esta increíble forma de simular un Cubo de Rubik. Solo practiqué golf y algunos cambios menores con respecto al desafío.

def f(a):
 s=t="UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR".split()
 for m in a.split():q="FLBR FRBL FDBU FUBD URDL ULDR".split()['UDLRFB'.index(m[0])];n=2+"2'".find(m[-1]);s=[[p,p.translate(str.maketrans(q,q[n:]+q[:n]))][m[0]in p]for p in s]
 return s==t

La idea detrás de esto es la siguiente. srepresenta la ubicación de las piezas de UF, URy así sucesivamente. Por ejemplo: s = ['DF', 'BL', ...]significa que la pieza UFestá en la posición DF, la pieza URestá en la posiciónBL , ...

¿Cómo cambia la posición de una pieza al hacer un movimiento? Si hace un Umovimiento, todas las pegatinas (colores) de la Ucapa, que miraban hacia la cara frontal, se mueven hacia la cara izquierda. Las pegatinas de la cara izquierda se mueven hacia atrás, estas hacia la derecha y estas hacia la cara frontal. Codificada por FLBR. Algunos ejemplos: se UFmueve a UL, se UFRmueve a, ULFetc. Por lo tanto, aplicar un movimiento es simplemente traducir las caras de las piezas en la capa correspondiente.

Jakube
fuente