El abismo | Piensa como un programador, Episodio 6

Vea la lección completa en: https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6

Este es el episodio 6 de nuestra serie animada "Piensa como un programador". Esta narración de 10 episodios sigue a una chica, Ética, y a su compañero robot, Hedge, mientras intentan salvar el mundo. Los dos se embarcan en una búsqueda para reunir tres artefactos y deberán resolver a lo largo de su camino una serie de puzzles de programación.

Lección impartida por Alex Rosenthal, dirigido por Kozmonot Animation Studio.

[Una serie original de TEDEd]

[Diseñada y animada por Kozmonot Studio]

[Piensa como un programador]

[Localización: Bosque198]

Episodio 6: El Abismo

Ética, Hedge y Octavia se encuentran
al borde de un barranco sin fondo.

Es lo único entre ellos y la torre

que custodia el segundo de
los tres poderosos artefactos.

Tienen un breve período de tiempo para
cruzar antes de que los guardias regresen.

Con el indicador de combustible casi
vacío, Hedge no podrá transportar a Ética,

así que la única opción es
construir un puente.

Por suerte, las pilas de piedras flotantes
cercanas son componentes del puente

- inventadas por la propia Octavia -
llamadas bloques flotantes.

Activa una pila con
un estallido de energía,

y se autoensamblarán para abarcar
el barranco mientras Ética cruza.

Pero hay, por supuesto, una trampa.

Los bloques flotantes solo son estables
cuando son palíndromos perfectos

Lo que significa que tienen que
formar una secuencia idéntica

cuando se vea por delante y por detrás.

Las pilas empiezan en órdenes aleatorios,

pero siempre que puedan se colocarán en
una configuración palindrómica.

Si llegan a un punto donde
no es posible un palíndromo,

el puente colapsará y, quien se encuentre
sobre él, caerá hacia el barranco.

Veamos un ejemplo.

Esta pila se haría estable.

Primero, los bloques A
se sitúan en su lugar.

Posteriormente, los B.

Y, finalmente, el C se ubicaría
justo entre los B.

Sin embargo, imagina que
hay un bloque A más.

Primero, se forman dos
bloques A; después, dos B;

pero, ahora, los bloques C y A restantes
no tienen donde ir y todo se derrumba.

El nodo de poder permite a Hedge
energizar una única pila de bloques.

¿Qué instrucciones puede dar Ética
a Hedge para permitirle encontrar

y alimentar eficientemente
una pila palindrómica estable?

[Pausa el vídeo si quieres
descubrirlo por ti mismo.]

[Pista en: 5]

[Pista en: 4]

[Pista en: 3]

[Pista en: 2]

[Pista en: 1]

Ejemplos de palíndromos incluyen
ANNA, RACECAR, y MADAM IM ADAM.

Contando el número de veces que
una letra dada aparece en un palíndromo

revelará un patrón útil.

[Pausa el vídeo si quieres
descubrirlo por ti mismo.]

[Solución en: 3]

[Solución en: 2]

[Solución en: 1]

Primeros veamos una solución
ingenua a este problema.

Una solución ingenua es una aproximación
simple con fuerza bruta no optimizada,

pero que hará el trabajo.

Las soluciones ingenuas son
formas útiles de analizar problemas,

y sirven como peldaños
para mejorar soluciones.

En este caso, una solución ingenua
es acercarse a una pila de bloques,

probar todas las combinaciones,

y ver si una de ellas es un palíndromo
al leerlo hacia delante y atrás.

El problema con este enfoque

es que tomaría una tremenda
cantidad de tiempo.

Si Hedge intentara una
combinación cada segundo,

una pila de solo 10 bloques diferentes
le llevaría 42 días hasta el agotamiento.

Esto se debe a que el tiempo total
es una función del factorial

del número de bloques que hay.

10 bloques tienen más de
tres millones de combinaciones.

Lo que muestra la solución ingenua
es que necesitamos una manera rápida

de decir si una pila de bloques
pueden forman un palíndromo.

Para empezar, se puede intuir que
una pila con todos los bloques diferentes

nunca formará una pila.
¿Por qué?

El primer y último bloque no pueden
ser iguales si no hay repeticiones.

Así que, ¿cuándo una secuencia
dada puede convertirse en un palíndromo?

Una forma de resolverlo es
analizar algunos palíndromos existentes.

En ANNA hay 2 bloques A y 2 N.

RACECAR tiene 2 R, 2 A, 2 C y 1 E.

Y MADAM IM ADAM tiene
4 M, 4 A, 2 D y 1 I.

El patrón aquí es que
la mayoría de letras aparecen

un número par de veces,

y hay al menos una que
aparece solo una vez.

¿Es así?

¿Qué pasa si RACECAR tuviera
3 E en lugar de 1?

Podemos colocar la nueva E en los extremos
y obtener también un palíndromo,

así que tres está bien.

Pero haz eso con 3 E y 3 C, y
no hay dónde colocar la última C.

Entonces, la idea más generalizada es que,

como máximo, una letra puede
aparecer un número impar de veces,

pero el resto tiene que ser par.

Hedge puede contar las letras en cada
pila y organizarlas en un diccionario,

que es una forma ordenada
de almacenar la información.

Un ciclo podría pasar y contar cuántas
veces aparecen los números impares.

Si hay menos de dos caracteres impares,
las pilas pueden ordenarse en palíndromos.

Este enfoque es mucho, mucho más
rápido que la solución ingenua.

En lugar de tiempo factorial,
se necesita tiempo lineal.

El tiempo aumentará de forma proporcional
al número de bloques que hay.

Ahora, escribe un bucle temporal para
que Hedge se aproxime

a las pilas individuales,

y pare cuando encuentre una buena,
y estarás listo para irte.

Esto es lo que ocurre:

Hedge es rápido, pero hay tantas
pilas que lleva mucho tiempo.

Demasiado.

Ética y Hedge están a salvo.

Pero Octavia no ha tenido tanta suerte.