Tu tarea
.. es hacer lo que Brian Fantana aparentemente no pudo hacer, y resolver el Cubo de Rubik 2x2x2.
El diseño
- - A B - - - -
- - C D - - - -
E F G H I J K L
M N O P Q R S T
- - U V - - - -
- - W X - - - -
Y se le dará a través de stdin o la línea de comando (su elección, especifique en su respuesta) en el formato:
ABCDEFGHIJKLMNOPQRSTUVWX
Tenga en cuenta que AD conforma la cara U (arriba), EFMN conforma la cara L (izquierda), GHOP conforma la cara F (frente), IJQR conforma la cara R (derecha), KLST conforma la Cara B (parte posterior) y UX conforman la cara D (abajo).
Habrá seis caracteres únicos que representan cada color, pero pueden variar, así que prepárese para cualquier combinación de 6 caracteres ascii que se utilizarán para cada color.
Especificaciones
- Su código debe generar una solución usando solo las caras Derecha (R), Superior (U) y Frontal (F), y debe usar la notación estándar: R, R ', R2, U, U', U2, F, F ', F2. Puedes encontrar más información aquí . La restricción al subconjunto RUF es estándar para el cubo 2x2 (Sugerencia: trate la esquina inferior-posterior-izquierda como una base fija para trabajar).
- Su código debe ser capaz de resolver todas las permutaciones posibles del cubo de bolsillo.
- Cada solución debe tomar menos de 30 segundos en completarse.
- Cada solución debe tener menos de 30 movimientos.
- Se otorgará un bono de -20% para las soluciones que siempre brindan respuestas de menos de 20 movimientos (por favor, publíquelo en su respuesta para que pueda verificarlo a fondo)
- Se otorgará una bonificación de -50% para el código que siempre proporciona una solución óptima. - De nuevo, por favor anuncie en su respuesta
- Las soluciones no deben contener dos movimientos consecutivos en la misma cara, ya que se pueden combinar fácilmente en un solo movimiento.
- Las soluciones pueden contener opcionalmente un solo espacio, y solo un solo espacio, entre cada movimiento.
- La secuencia completa de la solución, si es necesario, puede estar contenida entre paréntesis, comillas, llaves, corchetes o puntos, pero no se permite ningún otro resultado extraño.
- Proporcione una versión brevemente comentada de su código o una explicación detallada de su código.
- Sin uso de archivos externos. Esto incluye Internet, tablas de datos y bibliotecas / paquetes creados para este tipo de problema.
- El código más corto por conteo de bytes gana.
- Ganador elegido el miércoles (30 de julio de 2014).
code-golf
puzzle-solver
permutations
rubiks-cube
Kyle McCormick
fuente
fuente
Respuestas:
Python 2.7: 544 bytes -50% = 272 bytes **
Stackexchange reemplaza las pestañas con múltiples espacios en blanco. Tan técnica que esta versión tiene 549 bytes. Simplemente reemplace los dos primeros espacios en las líneas 6-10 con un tabulador.
Idea detrás de mi programa: mi primera idea fue una primera búsqueda de aliento. Pero esto tomó demasiado tiempo. Alrededor de 2 minutos para una lucha difícil (11 movimientos óptimos). Entonces decidí abordar el problema desde ambos lados. Yo uso dos juegos. Genero secuencialmente todos los estados con distancia 1,2,3, ... a la codificación y los guardo en el set1, y al mismo tiempo todos los estados con distancia 1,2,3, ... al estado resuelto y los guardo en set2. La primera vez que un estado está en ambos conjuntos, encontramos la solución.
Para esto necesito los colores del cubo resuelto, que no se conocen. Los caracteres 13, 20 y 23 definen el color izquierdo, posterior y descendente. Pero estos 3 colores son suficientes para representar el cubo. Simplemente reemplazo los otros 3 colores con espacios en blanco y puedo representar mi estado resuelto como '____ll____bbll____dddd'.
Ah, y para acortar las permutaciones, utilicé una idea de /codegolf//a/34651/29577
Versión sin golf:
Estoy bastante contento con el resultado, porque soy bastante nuevo en Python. Este es uno de mis primeros programas de Python.
editar: medio año después: 427 - 50% = 213.5
Tengo un poco más de experiencia en Python y en golf. Así que revisé mi código original y pude guardar más de 100 caracteres.
Básicamente uso exactamente el mismo enfoque. El mayor cambio es que ya no defino una función. En lugar de
puedo hacer
También cambié un poco el movimiento lamda. Primero acorte, y luego integre el código directamente, ya que la llamada a la función solo aparece una vez.
Mantengo para cada estado una lista de números entre 0 y 11, para representar los movimientos, en lugar de una cadena que contiene los movimientos. Los números se convierten al final.
También combiné los dos bucles for
'for k in r(3):for j in r(3):
en unofor y in r(12)
. Por lo tanto, también tengo que hacer los movimientosU4, R4, F4
. Por supuesto, tal movimiento no aparece en la solución más corta, por lo que" 2'"[x%4]
funciona. (Six % 4 == 3
hubiera una excepción de índice fuera de rango)También es un poco más rápido, ya que busco la entrada en el segundo set anterior. Aproximadamente 0.5 segundos para una solución de 11 movimientos.
fuente
C, 366 - 50% de bonificación óptima = 183
Usando la recursividad, el programa busca a través de un árbol de hasta 11 movimientos de profundidad (la longitud máxima de una solución óptima de acuerdo con http://en.wikipedia.org/wiki/Pocket_Cube y la página mencionada a continuación) y cuando encuentra una solución lo imprime (hasta 22 caracteres de largo, seguido por el argumento de la función
m
). El orden utilizado es una especie de orden de diccionario, donde se buscan todas las rutas que comienzan con U, U2, U 'antes de buscar cualquier ruta que comience con R o F. Por lo tanto, no necesariamente encuentra la solución óptima primero.Cuando se imprime una solución,
r
se hace igual a lom
que garantiza que solo se imprimirán soluciones iguales o más cortas después. La colocaciónr=m-2
cuesta 2 caracteres adicionales, pero garantiza que solo se imprima una solución de cada longitud encontrada (hasta la óptima). Si desea que SOLO muestre la solución óptima, la mejor solución encontrada hasta ahora debe almacenarse en una variable, y la solución óptima impresa al final del programa (esto costaría unos 15 caracteres adicionales).la entrada se lee en la matriz
c[]
desde el índice 64 en adelante. Esto es necesario para usar caracteres alfabéticos en la tabla móvil. Los símbolos a@
travésW
se utilizan en lugar de A a X según la pregunta, porque es necesario comenzar en un número par para que la prueba de soluciones funcione.c['Z']
también se usa para almacenamiento temporal, porque para realizar una rotación de 4 veces se necesitan un total de 5 tareas. Debido a que la primera parte dec[]
no se utiliza, está disponible para almacenar la solución (que termina con un byte cero, como todas las cadenas C).for(i..)
pasa por una secuencia de 4 cuartos de vuelta de la cara especificada porn
.El primero
for(j..)
realiza el intercambio real de acuerdo con la tablat[]
.Para probar si el cubo está resuelto, solo es necesario verificar las cuatro caras laterales. Las piezas URF y DFR se pueden distinguir incluso con las pegatinas U y D quitadas, porque una pieza lee XRF en el sentido de las agujas del reloj y la otra XFR. Si las dos piezas se intercambian de modo que U se muestre en la cara inferior y viceversa, el color F se mostrará en la cara derecha y viceversa.
El segundo
for(j..)
cuenta el número de desajustes en las cuatro caras laterales. Por ejemplo, para la cara frontal, compara G y O, H y P y G y H (dos veces). Sie
== 0, el cubo está resuelto. Sie
<9 oe
<13, podría ser posible resolver el cubo en el siguiente movimiento o 2 movimientos respectivamente. De lo contrario, definitivamente no es posible resolver el cubo en este número de movimientos. Para ahorrar tiempo, esta heurística se utiliza para podar el árbol de búsqueda y evitar perder tiempo en muchas de las ramas de profundidad 10 u 11 que no tendrán éxito. Expresado como una fórmula, esto se conviertee<45-m*2
.Código sin golf
Actuación
El programa se probó con los patrones 1 a 13 en http://www.jaapsch.net/puzzles/cube2.htm
Los resultados de la siguiente manera dan el tiempo en mi máquina para encontrar TODAS las soluciones óptimas (para los curiosos). También para las posiciones más complejas, se da el tiempo para la modificación de 2 bytes mencionada anteriormente que encuentra una sola solución óptima. Para esto, se dan tiempos para encontrar la primera solución y para que el programa finalice. Las soluciones dadas (que generalmente son diferentes a las soluciones obtenidas al invertir los generadores en la página vinculada) se han verificado con un simulador de cubos en línea.
fuente