MALOS MOMENTOS

Parece ser que está, vivencialmente, comprobado.

CAPACHA - Cuenta atrás


MANOS

Y ES QUE SIGUE HABIENDO MUCHAS CAPACHAS NECESITANDO MANOS PARA SER TRANSPORTADAS. ¿TE ANIMAS?

CAPACHA - Cuenta atrás


El ABC de la creación (2): soluciones y nuevos desafíos.

Espacio versus tiempo
Las reglas del juego y los primeros desafíos pueden verse en este enlace

Marcos Donnantuoni propone una variante para todos los desfíos que consiste en buscar la solución que ocupe el menos espacio posible, en lugar del menor tiempo. Es decir, ahora buscamos la solución que pueda ser desarrollada en la cinta de menor longitud (a igualdad en espacio, será mejor la solución en menor tiempo).

Éstas son, hasta ahora, las mejores soluciones para los tres primeros desafíos en esta variante.

(a) Pasar de la cinta vacía a ABC y (b) pasar de ABC a BCA: Las soluciones óptimas en tiempo (ambas de Marcos, con 5 pasos) son también hasta ahora las mejores en espacio, con 4 espacios cada una (no parece que se pueda mejorar). Las copio aquí:
0 ----
1 --AA
2 AAAA
3 A--A
4 ABBA
5 ABC-

0 ABC-
1 AA--
2 AAAA
3 A--A
4 ABBA
5 -CBA

(c) A partir de ABC recorrer las otras cinco permutaciones de esas letras: MFR tiene una solución en 25 pasos (óptima en tiempo) que sólo usa 5 espacios (la de Marcos, también de 25 pasos, pblicada en el entrada anterior, si no conté mal -y pude haber contado mal- usa 10 espacios):
00   ABC--
01   C-C--
02   C-CAA
03   C--BA
04   CCCBA
05   --CBA
06   --C-C
07   BBC-C
08   BA--C
09   BACCC
10   BAC--
11   B-B--
12   B-BAA
13   B--CA
14   BBBCA
15   --BCA
16   --B-B
17   AAB-B
18   AC--B
19   ACBBB
20   ACB--
21   -BB--
22   -BBBB
23   -B--B
24   -BAAB
25   --CAB

Dos nuevos desafíos:

El caminante (propuesto por Leonardo): pide hacer "caminar" una letra A n pasos hacia la derecha o hacia la izquierda. MFR pudo hacer "caminar" una A una cantidad par n de casillas, a la izquierda o a la derecha, en exactamente n pasos; por ejemplo para = 4:

00   A----
01   AAA--
02   --A--
03   --AAA
04   ----A

"Para moverla sólo un lugar", dice MFR, "cuesta un poquito más de trabajo, a mí me salió en 5 pasos (y utilizando dos 'espacios' adicionales en sentido opuesto al que queremos 'avanzar')":
00   --A-
01   BBA-
02   BC--
03   BCAA
04   BB-A
05   ---A

Leonardo, por su parte, tiene una solución para mover A un paso a la derecha en 3 tiempos (y 4 espacios):
00 -A--
01 -ABB
02 --CB
03 --A-

Actualización del 15.11.13: Escribe Leonardo en los comentarios.
Conclusiones sobre traslados de A:
Para cualquier número n de pasos, con n par, la cantidad mínima es n. 
Para cualquier número n de pasos, con n impar, la cantidad mínima es n+2.
Por otra lado, y como consecuencia de esto, dado un número n cualquiera, si se lo escribe de la forma q+w, siendo q y w enteros positivos, entonces la cantidad de pasos necesarios para moverlo n lugares será igual a la de q sumada a la de w.
En otras palabras, si definimos una función P(n) que es la mínima cantidad de pasos necesarios para trasladar una A n lugares, entonces P(n)=P(q+w)=P(q)+P(w) siempre que q+w=n.

Desafío escatológico (propuesto por Marcos): pide pasar de BABA a CACA...
...(1) en la menor cantidad de tiempo
...(2) usando el menor espacio.

Claudio Meller tiene una solución en 7 pasos y 6 espacios, y otra en 8 pasos y 5 espacios.
7 PASOS  SEIS ESPACIOS
0. --BABA
1. CCBABA
2. CA-ABA
3. CA--CA
4. CACCCA
5. CAC--A
6. CACAAA
7. CACA

8 PASOS CINCO ESPACIOS
0. -BABA
1. --CBA
2. CCCBA
3. C--BA
4. CAABA
5. CA-CA
6. CA--B
7. CACCB
8. CACA-

La solución ¿óptima? de Marcos tiene 6 pasos y 5 espacios:
0 BABA-
1 BAC--
2 BACAA
3 B - BAA
4 B--CA
5 BAACA
6 -CACA

CAPACHA - Cuenta atrás