1.11.13

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

7 comentarios:

MFR dijo...

Vamos con el desafío escatológico en 10 pasos y 7 espacios:

00   BABA---
01   -CBA---
02   -CC----
03   -CCBB--
04   -CA-B--
05   -CA-BAA
06   -CA--CA
07   -CACCCA
08   -CAC--A
09   -CACAAA
10   -CACA--


MFR dijo...

Que en realidad se puede hacer en 10 pasos y 6 espacios,
(evitando desperdiciar el espacio inicial):

00   BABA--
01   C-BA--
02   C--C--
03   CAAC--
04   CA-B--
05   CA-BAA
06   CA--CA
07   CACCCA
08   CAC--A
09   CACAAA
10   CACA--

Marcos dijo...

Yo pude hacerlo en menos pasos y menos espacio, a ver quién se anima...
Mañana posteo la solución óptima si nadie la averigua.

MFR dijo...

Encontré una solución en 7 pasos y 6 espacios:

00   --BABA
01   CCBABA
02   CA-ABA
03   CA--CA
04   CAAACA
05   C--ACA
06   CCCACA
07   --CACA


Es parecida a la de Claudio Meller en 8 pasos y 6 espacios, pero creo que él está contando la posición inicial BABA como paso 1 cuando debería ser 0 (no es un paso).

Gustavo Piñeiro dijo...

Sí, es verdad sobre la cuenta de los pasos de Claudio Meller, es un paso menos en cada solución. Ya lo corregí, gracias.

Leonardo dijo...

Estaba pensando, si para mover A un lugar hacia la derecha, usé 3 pasos, está claro que en 6 pasos se puede mover otro lugar y en otros 3 pasos un tercer lugar, con lo que para mover A tres lugares hacia la derecha, estaríamos necesitando 9 pasos, pero algo me dice, sin haberlo probado aún, que debe hacer una forma de mover A 3 lugares en menos de 9 pasos.

Leonardo dijo...

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.