Tarea 5 de Análisis y Diseño de Algoritmos

Trimestre 2014 Invierno
Entrega: 10 de febrero de 2014 a las 22:00.

En un juego infantil se tienen 2N+1 espacios en línea recta, en los N espacios de la izquierda hay canicas blancas, luego hay un espacio vacío y en los N espacios de la derecha hay canicas negras. El objetivo del juego es mover las N canicas blancas a los N espacios de la derecha y las N canicas negras a los N espacios de la izquierda. Para ello, se puede usar cualquiera de los siguientes cuatro movimientos:
  1. mover una canica blanca una posición a la derecha (si está vacía)
  2. mover una canica blanca dos posiciones a la derecha (saltando una canica negra a una posición vacía)
  3. mover una canica negra una posición a la izquierda (si está vacía)
  4. mover una canica negra dos posiciones a la izquierda (saltando una canica blanca a una posición vacía)
Escriba un programa llamado canicasZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea un entero N y que calcule alguna forma de lograr el objetivo, indicando la cantidad P de pasos necesarios, seguido de los pasos. Puede suponer que 1 <= N <= 30. Por ejemplo si N = 2, entonces el objetivo se puede lograr en P = 8 pasos de la siguiente forma:
  1. 11022 (posición inicial)
  2. 10122 (canica blanca una posición a la derecha).
  3. 12102 (canica negra dos posiciones a la izquierda).
  4. 12120 (canica negra una posición a la izquierda).
  5. 12021 (canica blanca dos posiciones a la derecha).
  6. 02121 (canica blanca dos posiciones a la derecha).
  7. 20121 (canica negra una posición a la izquierda).
  8. 22101 (canica negra dos posiciones a la izquierda).
  9. 22011 (canica blanca una posición a la derecha).
Arriba (y en la salida) se indican las canicas blancas con 1, las negras con 2 y el espacio con 0.

Ejemplo de entrada
 Ejemplo de salida
2
 8
1 1 0 2 2
1 0 1 2 2
1 2 1 0 2
1 2 1 2 0
1 2 0 2 1
0 2 1 2 1
2 0 1 2 1
2 2 1 0 1
2 2 0 1 1

Notas: Sus programas no deben leer ni escribir nada adicional a lo que se indica en el enunciado. El tiempo de ejecución de sus algoritmos será considerado como parte de la evaluación.