Mientras giraba ociosamente el cubo de mi Rubik , mi hijo notó que seguía volviendo al estado resuelto. Estoy bastante seguro de que al principio pensó que esto era una especie de magia vudú, pero le expliqué que si sigue repitiendo la misma secuencia de movimientos, siempre volverá a su estado original. Finalmente.
Por supuesto, siendo un niño, tuvo que probarlo por sí mismo y eligió una secuencia "aleatoria" que pensó que sería difícil. Perdió la pista después de diez repeticiones más o menos, y me preguntó cuántas veces tendría que repetirla. Sin saber la secuencia que estaba usando, le dije que no sabía, pero que podíamos escribir un programa para averiguarlo.
Aquí es donde entras tú. Por supuesto, podría preparar algo, pero a él le gustaría escribirlo él mismo. Sin embargo, todavía no es un mecanógrafo muy rápido, así que necesito el programa más corto posible .
Objetivo
Dada una secuencia de giros, genera la menor cantidad de veces que se debe realizar para devolver el cubo a su estado original. Este es el código de golf, por lo que gana menos bytes. Puede escribir un programa o función, y se aplican todos los demás valores predeterminados habituales.
Entrada
La entrada es una secuencia de movimientos, tomada como una cadena, lista u otro formato adecuado para su idioma. Siéntase libre de usar un separador (o no) entre movimientos si está en forma de cadena.
Hay seis movimientos "básicos" que deben tenerse en cuenta, junto con sus inversas:
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
Las inversas se representan agregando una marca principal 'después de la letra. Esto indica que gira esa cara en sentido antihorario, por lo que F'gira la cara frontal en sentido antihorario y la F F'devolverá al estado original de inmediato.
Para los interesados, este desafío está utilizando un conjunto limitado de notación Singmaster . Ruwix tiene algunas animaciones agradables si desea verlo en acción.
Salida
La salida es simplemente el número mínimo de veces que se debe realizar la secuencia de entrada.
Ejemplos
Input Output
FF' -> 1
R -> 4
RUR'U' -> 6
LLUUFFUURRUU -> 12
LUFFRDRBF -> 56
LF -> 105
UFFR'DBBRL' -> 120
FRBL -> 315
Aquí hay un solucionador (bastante ingenuo) para comparar sus respuestas, escrito en Java. También acepta 2movimientos dobles (por lo que el cuarto caso es equivalente a 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;
}
}
}
fuente
Respuestas:
Pyth,
6663 bytesPruébelo en línea: Demostración o Test Suite . Observe que el programa es un poco lento y el compilador en línea no puede calcular la respuesta
RU2D'BD'. Pero tenga la seguridad de que puede calcularlo en mi computadora portátil en aproximadamente 12 segundos.El programa (accidentalmente) también acepta
2movimientos dobles.Explicación completa:
Parse scramble:
Primero me ocuparé de las marcas principales
'en las cadenas de entrada. Simplemente los reemplazo3y decodifico esta cadena con longitud de ejecución. Dado que el formato de decodificación de Pyth requiere el número delante del carácter, invierto la cadena de antemano._r_Xz\'\39. Así que luego lo revierto.Describa el estado del cubo resuelto:
=Z"UDLRFBasigna la cadena con los 6 movimientos aZ.Podemos describir un estado de cubo describiendo la ubicación de cada pieza de cubo. Por ejemplo, podemos decir que el borde, que debería estar en UL (arriba a la izquierda) está actualmente en FR (frente a la derecha). Para esto necesito para generar todas las piezas del cubo resuelto:
f!s}RTcZ2yZ.yZgenera todos los subconjuntos posibles de"UDLRFB". Obviamente, esto también genera el subconjunto"UDLRFB"y el subconjunto"UD". El primero no tiene ningún sentido, ya que no hay una pieza que sea visible desde los 6 lados, y el segundo no tiene ningún sentido, ya que no hay una pieza de borde, que es visible desde la parte superior e inferior. . Por lo tanto, elimino todos los subconjuntos, que contienen la subsecuencia"UD","LR"o"FB". Esto me da las siguientes 27 piezas:Esto también incluye la cadena vacía y las seis cadenas de 1 letra. Podríamos interpretarlos como la pieza en el medio del cubo y las 6 piezas centrales. Obviamente no son necesarios (ya que no se mueven), pero los guardaré.
Haciendo algunos movimientos:
Haré algunas traducciones de cadenas para realizar un movimiento. Para visualizar la idea, mira la pieza de la esquina
URF. ¿Qué le sucede cuando hago unRmovimiento? La pegatina en laUcara se mueve hacia laBcara, la pegatina seFmueve hacia laUcara y la pegatina en laRcara permanece en laRcara. Podemos decir que la pieza en seURFmueve a la posiciónBRU. Este patrón es cierto para todas las piezas en el lado derecho. Cada pegatina que está en laFcara se mueve hacia laUcara cuandoRse realiza un movimiento, cada pegatina que está en laUcara se mueve hacia laBcara, cada pegatina en losBmovimientos haciaDy cada pegatina en losDmovimientos haciaF. Podemos decodificar los cambios de unRmovimiento comoFUBD.El siguiente código genera los 6 códigos necesarios:
Y realizamos un movimiento
Hal estado del cubo de laGsiguiente manera:Cuenta el número de repeticiones:
El resto es bastante trivial. Simplemente realizo la codificación de entrada al cubo resuelto una y otra vez hasta llegar a una posición que visité anteriormente.
fuente
GAP,
792 783 782749650 BytesEsto parece estar funcionando. Si se equivoca con algo, hágamelo saber.
Gracias a @Lynn por sugerir que descomponga algunos de los movimientos primitivos.
Gracias a @Neil por sugerir que en lugar de
Inverse(X)usarX^3.Ejemplo de uso:
f("R");Aquí está el código no golfista con un poco de explicación.
fuente
45con5en sus permutaciones y guardar tres bytes.A:=R*L*L*L*F*F*B*B*R*L*L*L;D:=A*U*A;es más corto que su definición deD(pero no puedo probarlo ...)^-1para inversas, por cierto?Mathematica,
413401 bytesExplicaciones
Un cubo de Rubik está compuesto por 20 cubos móviles (8 esquinas, 12 bordes). A cada cubito se le puede dar un número:
esquinas :
bordes :
Tenga en cuenta que cuando el cubo está torcido, los cubos generalmente ya no están en sus posiciones iniciales. Por ejemplo, cuando
Rse hace, el cubito se1mueve desdeUFRuna nueva posiciónUBR.En tal notación, un giro de 90 grados se puede describir con 8 movimientos de cubos. Por ejemplo,
Rse describe porComo cada cubito tiene una posición inicial única, cada posición tiene un cubo inicial único. Es decir, la regla
UFR->UBRes justa1->2(significa queRlleva el cubito en la posición inicial del cubo1a la posición inicial del cubo2). Por lo tanto,Rse puede simplificar más a un cicloPara resolver completamente un cubo de Rubik, también necesitamos alinear los cubos con sus orientaciones iniciales correspondientes. Las caras de un cubo están pintadas en diferentes colores, el esquema que uso a menudo para resolver cubos es
Cuando analizamos las orientaciones de las esquinas, se ignoran los colores que no sean amarillo o blanco, y el amarillo y el blanco se consideran del mismo color.
Supongamos que el cubo
1está en su posición inicialUFR, la faceta amarilla puede estar alineada con tres caras diferentes. Usamos un número entero para representar estos casos,Supongamos que cubie
1está activadoDFL, sus tres orientaciones posibles sonCuando analizamos las orientaciones de los bordes, se ignoran el rojo y el naranja, y el amarillo y el blanco se ignoran solo si el borde tiene una faceta verde o azul.
Supongamos que el cubo
10está en su posición inicialUR, la faceta verde puede estar alineada con dos caras diferentes. Sus dos orientaciones posibles sonSupongamos que cubie
10está activadoDF, sus dos orientaciones posibles sonUna matriz se usa para almacenar el estado de un cubo. El estado inicial de un cubo es
lo que significa que cada cubito está en su posición inicial con la orientación correcta.
Después
R, el estado del cubo se convierte enlo que significa que el cubo
5ahora está en posición1(UFR) con orientación2, el cubo1ahora está en posición2(UBR) con orientación1, el cubo3todavía está en posición3(UBL) con orientación0, y así sucesivamente.Casos de prueba
fuente
Haskell, 252 bytes
Ejecuciones de muestra:
La observación clave aquí es que es más simple modelar el cubo de Rubik como una cuadrícula de puntos de 5 × 5 × 5 en lugar de una cuadrícula de cubos orientados de 3 × 3 × 3. Los cubos de esquina se convierten en cubos de 2 × 2 × 2 puntos, los cubos de borde se convierten en cuadrados de 2 × 2 × 1 puntos y se mueven rotando rodajas de 5 × 5 × 2 puntos.
fuente
c:"'"conc:_salva dos bytes._también coincide con la lista vacía.Ruby, 225 bytes
Similar a la respuesta de Anders Kaseorg e inspirado por la respuesta de Jan Dvorak a una pregunta anterior.
Sin embargo, a diferencia de esas respuestas, no necesito 125 cubitos. Utilizo un cubo de rubik de 27 cubos, pero de dimensiones rectangulares. En el estado resuelto, las esquinas están en
+/-1,+/-4,+/-16.Genero una matriz de 64 cubos, cada uno con un centro elegido
x=[-1,0,1,2], y=[-4,0,4,8], z=[-16-0,16,32]. Los cubos con coordenadas de 2, 8 y 32 son innecesarios, pero no causan daño, por lo que se dejan adentro por razones de golf. El hecho de que la longitud, el ancho y la profundidad de los cubos sean diferentes: (1,4,16) significa que es fácil detectar si están en el lugar correcto pero con una orientación incorrecta.Cada cubito se rastrea a medida que lo mueven las facetas. Si la coordenada de un cubo en el eje correspondiente a la cara (multiplicada por
e=-1U, F, R oe=1D, B, L) es positiva, se rotará intercambiando las coordenadas en los otros 2 ejes y aplicando un cambio de signo apropiado a una de las coordenadas. Esto se controla multiplicando pore*d.La secuencia de entrada se escanea en orden inverso. Esto no hace ninguna diferencia, siempre que las rotaciones "normales" se realicen en sentido antihorario en lugar de hacerlo en sentido horario. La razón de esto es que si
'se encuentra un símbolo, el valor dedse puede cambiar de 1 a -1 para provocar la rotación de la siguiente cara en la dirección opuesta.Sin golf en el programa de prueba
fuente
Python 2, 343 bytes
La entrada se toma de stdin.
La secuencia de giros dada se realiza repetidamente en un cubo virtual hasta que regrese al estado resuelto. El estado del cubo se almacena como un vector de orientación y un vector de permutación, ambos de longitud 20.
Las orientaciones se definen de manera arbitraria: un cubo de arista está orientado correctamente si se puede mover a su lugar sin invocar un cuarto de vuelta R o L. La orientación de los cubos de esquina se considera relativa a las caras F y B.
Uso de muestra
Demostración en línea y conjunto de pruebas .
fuente
Clojure, 359 bytes
Este podría ser mi segundo codegolf más largo. Al darme cuenta de que podía eliminar los ceros finales de los vectores
AparaFhacerme muy feliz: DMenos golfizado:
Esto simplemente implementa rotaciones 3D de subconjuntos seleccionados de
5 x 5 x 5cubos. Originalmente iba a usar3 x 3 x 3y me tomó un tiempo darme cuenta de por qué no obtenía los resultados correctos. ¡Buenos casos de prueba! Algunos bytes adicionales para la codificación de puño"RUR'U'"como"RURRRUUU".fuente
Cúbicamente ,
96 bytesPruébalo en línea! (No funciona hasta que Dennis actualice el intérprete de TIO Cubically)
Explicación:
Este lenguaje dominará todos los desafíos del cubo de rubik >: D
fuente
-7significaba restar siete, no agregar un andador enojadoLimpio , 255 bytes
Derivado por separado de la respuesta casi idéntica de Haskell como respuesta a esta pregunta que se cerró como un duplicado cuando estaba casi terminada, así que publiqué la respuesta aquí.
Pruébalo en línea!
fuente