Un pasatiempo venerado de los pedantes es señalar que las imágenes de "Cubos de Rubik" (en camisetas, carteles, etc.) en realidad no tienen solución.
Lo primero que debe verificarse es que el cubo esté formado por las piezas correctas. Para poder resolverse, un cubo necesita seis colores, cada uno con nueve cuadrados. El cubo también necesita que cada unidad de borde y esquina (estos son los cubos más pequeños que conforman el cubo) para ser únicos. No solo deben ser únicos, sino que si dos piezas centrales están opuestas entre sí, ninguna pieza de borde o esquina puede contener ambos colores.
Una vez que tenga un cubo que esté formado por todas las piezas correctas, aún debe verificar que pueda resolverse. Aquí hay un par de reglas, por lo que consultaré a un experto para que las explique, el spoiler a continuación explica cómo podemos hacer esto. Si está interesado en resolver el problema por su cuenta, no necesita visitar el sitio para comprender o participar en este desafío.
Su tarea es tomar un patrón como entrada y determinar si de hecho es un cubo de Rubik solucionable. Para que sea solucionable debe haber una forma de realizar movimientos válidos en un cubo para que el cubo tenga un solo color en cada cara (y las diferentes caras tengan colores diferentes). La mayoría de los cubos de Rubik tienen un color estándar (el blanco es opuesto al amarillo, etc.). No puede suponer que el estado de resolución sigue a este color particular.
Un movimiento válido es la rotación en sentido horario o antihorario de una sola cara del cubo. Con la rotación de la cara del cubo, también se giran los cuadrados que bordean la cara, permaneciendo conectados a la cara que estaban tocando anteriormente.
IO
Puede tomar el cubo de cualquier manera razonable. Si su idioma tiene algún tipo de "cara de cubo" incorporada, bueno para usted, está bien como entrada, de lo contrario puede tomar una matriz 2D de la red, del cubo, de 1 3 por 3 listas para cada cara. Solo se razonable. Si desea saber si un formato específico es aceptable, hágame un comentario o hágame ping en el chat y agregaré al desafío para indicar su validez.
Su formato de entrada solo necesita admitir hasta 9 colores posibles.
Para la salida, este es un problema de decisión, por lo que debe generar un valor constante para "Sí, este es un cubo de Rubik válido" y un valor constante diferente para "No, este no es un cubo de Rubik válido".
Este es el código de golf, por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.
Casos de prueba
Aquí hay casos de prueba. Están formateados como la red de un cubo con cada cuadrado como una sola letra. Diferentes letras representan diferentes colores. Se pueden agregar más casos de prueba a pedido.
Soluble
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YYY
YYY
YYY
GRR
GRR
ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
WYO
YYB
YYB
Insoluble
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
YWY
YYY
YYY
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YWY
YYY
YYY
RRR
RRR
GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
BBB
YWY
YYY
RRW
RRW
GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
BBB
YYW
YYO
fuente
Respuestas:
Cúbicamente ,
166416311089 bytesSalida si tiene solución:
Solved!
Salida si no tiene solución: (vacío, sin salida)
La entrada debe formatearse como un volcado de cubo cúbico (consulte la
Debug
sección). Esto fue explícitamente permitido por el OP.Explicación
Este programa adopta el enfoque de usar un Algoritmo del Diablo para iterar sobre cada estado posible del cubo en el mismo grupo que el cubo resuelto. Si el cubo tiene solución, se resolverá en algún momento antes de que el algoritmo haya finalizado (suponiendo que el algoritmo que utilicé funcione correctamente).
Cada línea que comienza con
⇒
(0x84 en la página de códigos de Cubically) es una definición de función; Estas funciones se complementan entre sí para formar el algoritmo del diablo real. La primera línea a ejecutar es la última:r
lee un cubo de stdin y establece el cubo de memoria en él.s
pone al intérprete en "modo de resolución", lo que significa que sale e imprimeSolved!
si el cubo se resuelve (después de no resolverse) en cualquier momento. El resto de los comandos (que simplemente se repitenf36f71
8 veces) corresponden al algoritmo final en la parte inferior de la página vinculada:¿Cómo puedo ejecutarlo?
Puedes probarlo en línea , pero ese enlace no funciona. TIO casi definitivamente expirará antes de que termine este algoritmo (el tiempo de ejecución máximo para un intérprete es de 60 segundos). Si el cubo no se puede resolver, este algoritmo tomará hasta 11 millones de años para que Cubically termine (a ~ 15.2 millones de movimientos por segundo, que es lo que obtiene mi IDE Cloud9 ).
Además, necesita mucha memoria para realizar 3 sextillones de movimientos. Cúbicamente puede realizar alrededor de 4 millones de movimientos por segundo, pero el proceso probablemente se cancele debido a la memoria comprometida en exceso . Muere después de 15 segundos en mi VM con 512 MB de memoria.¿Por qué realizar movimientos en una memoria de matriz plana ya asignada cuesta? Encontró una pérdida de memoria (o veinte) y la arregló .Aquí hay una versión mucho más legible que se comporta de la misma manera.
¡Pero realmente quiero ver que funciona!
El primer movimiento real que se ejecuta en el algoritmo de este demonio es
F2
, por lo que el cubo más rápido para resolver sería uno codificado conF2
:De hecho, esto se ejecuta en 0.007 segundos en TIO .
¿Cómo se puede mejorar esto?
Ciertamente hay más algoritmos del diablo; He encontrado uno que usa menos de la trigésima parte de los movimientos que este hace. Sin embargo, eso tendría un costo de varios miles de bytes (alrededor de 100 MB más) y varias docenas de horas de convertir un complejo circuito hamiltoniano a código cúbico.
También es posible eliminar algunas de las funciones y colocarlas directamente en el bucle en la parte inferior. Sin embargo, voy a sacrificar algunos bytes por cierta legibilidad.
Además, estoy considerando una modificación del comportamiento de bucle de Cubically para poder repetir más fácilmente los algoritmos 7 u 8 veces (en lugar de simplemente codificarlos con las llamadas de función repetidas 7 u 8 veces en la fuente). O haré algo de magia con el bloc de notas, y jugaré golf usando más bucles.
Tenga en cuenta que continuaré optimizando todo lo posible en el intérprete, ¡así que esto puede funcionar en una PC promedio en algún momento en el futuro!
Cúbicamente, 2 bytes
Me gusta más la respuesta anterior, así que estoy agregando esto como una solución alternativa. Esto se ejecuta en menos de un segundo, a diferencia de unos pocos millones de años.
Salida si el cubo tiene solución: (nada)
Salida si el cubo no tiene solución:
Error: The cube has reached an unsolvable state.
fuente
APL (Dyalog Classic) ,
190174 bytesPruébalo en línea!
El argumento es una matriz de 3x2 (fila0: frente atrás, fila1: izquierda derecha, fila2: arriba abajo) de matrices de 3x3 caracteres. Devuelve 1 para un cubo de Rubik solucionable, 0 de lo contrario.
En el enlace TIO, la función
t
, que no está incluida en el recuento de caracteres, lee 9 líneas de entrada, las convierte del formato de entrada predeterminado (una red) a la matriz 3x2 x 3x3 requerida, llama a la solución e imprime OK si el resultado es como se esperabaEl algoritmo divide el cubo dado en 26 cubos: cadenas de longitud 3 (esquinas), 2 (bordes) y 1 (centros). También genera los 26 cubos de un cubo resuelto con los mismos 6 cubos centrales. Deben cumplirse todos los siguientes criterios:
no hay duplicados entre los 6 centros
los conjuntos de cubos dados / resueltos coinciden, hasta la rotación, por ejemplo, considerar
'WBR'
y'BRW'
el mismo cubito, pero no'BWR'
las paridades tanto de la permutación de la esquina como de la permutación del borde son pares
la suma módulo 3 de los índices de rotación de esquina (por ejemplo, tomando la letra "más pequeño"
B
como punto de referencia que tenemos:'BRW'→0
,'WBR'→1
,'RWB'→2
) partido entre los cubos dados y resueltos; lo mismo para las esquinas módulo 2fuente