Contenidos
Charla «El abismo» de TED-Ed en español.
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.
- Autor/a de la charla: Alex Rosenthal
- Fecha de grabación: 2020-01-30
- Fecha de publicación: 2020-01-30
- Duración de «El abismo»: 384 segundos
Traducción de «El abismo» en español.
[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.
https://www.ted.com/talks/alex_rosenthal_the_chasm_think_like_a_coder_ep_6/