Dispersión en color |
Este puzle está formado por dos ruedas. Ambas ruedas pueden rotar tanto en sentido horario como anti-horario. Cada rueda contiene 21 piezas coloreadas, 10 de las cuales son triángulos redondeados y 11 que son separadores. La figura 1 muestra la posición final de cada una de las piezas. Notar que para hacer una rotación debes girar la rueda hasta avanzar un triángulo y un separador.
Figura 1. Configuración final del puzzle
Tu trabajo es escribir un programa que lea una configuración inicial del puzzle y escriba por pantalla la secuencia mínima de movimientos que se requieren para alcanzar la configuración final. Usaremos los siguientes valores enteros para codificar cada tipo de pieza:
0 | separador gris |
1 | triángulo amarillo |
2 | separador amarillo |
3 | triángulo azul |
4 | separador azul |
5 | triángulo violeta |
6 | separador violeta |
7 | triángulo verde |
8 | separador verde |
9 | triángulo rojo |
10 | separador rojo |
Una configuración del puzzle será descrita usando 24 números enteros, los 12 primeros
para describir la configuración de la rueda de la izquierda y los últimos 12 para la rueda de la derecha.
El primer entero representa el separador de abajo a la derecha en la rueda de la izquierda, y los once
siguientes enteros describen la rueda izquierda en sentido horario. El decimotercer entero representa
el separador de abajo a la izquierda de la rueda derecha, y los once siguientes enteros describen la rueda
derecha en sentido anti-horario.
Por lo tanto, la posición final es codificado de la siguiente manera:
Por ejemplo, si rotamos la rueda izquierda en sentido horario una posición empezando en la configuración final (como se muestra en la figura 2) la configuración del puzzle sería codificada así:
Figura 2. El puzzle después de rotar la rueda de la izquierda en sentido horario una posición
empezando en la configuración final.
La entrada al programa consistirá en varios puzzles. La primera línea de la entrada contendrá un entero n especificando el número de puzzles. A continuación vienen n líneas, cada una con 24 enteros separados por un espacio en blanco, describiendo la configuración inicial del puzzle como se ha explicado antes.
Para cada puzzle de entrada, el programa debe escribir una línea con un número representando la solución. Cada movimiento es codificado usando un dígito de 1 a 4 de la siguiente manera:
1 | Rotación en sentido horario de la rueda de la izquierda |
2 | Rotación en sentido horario de la rueda de la derecha |
3 | Rotación en sentido anti-horario de la rueda de la izquierda |
4 | Rotación en sentido anti-horario de la rueda de la derecha |
No escribir espacios entre los dígitos. Puesto que pueden existir muchas soluciones, debes escribir la que sea codificada con el menor número. La solución nunca requerirá más de 16 movimientos.
Si no se puede encontrar solución debes escribir: "NO SOLUTION WAS FOUND IN 16 STEPS". Si la entrada es la posición final, debes escribir: "PUZZLE ALREADY SOLVED".
3 0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1 0 3 4 5 0 3 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1 0 9 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 3 0 1 2 1
PUZZLE ALREADY SOLVED 1434332334332323 NO SOLUTION WAS FOUND IN 16 STEPS