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 n = 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:
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--
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--
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.
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).
Sí, es verdad sobre la cuenta de los pasos de Claudio Meller, es un paso menos en cada solución. Ya lo corregí, gracias.
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.
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.
Publicar un comentario