Código acm.uva.es: 704

  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:

0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1

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í:

2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1


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.

Entrada 

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.

Salida 

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".

Ejemplo de entrada 

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

Ejemplo de salida 

PUZZLE ALREADY SOLVED
1434332334332323
NO SOLUTION WAS FOUND IN 16 STEPS