La Torre de la Epifanía | Piensa como en programación, Episodio 7

Ver la lección completa en: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

Este es el episodio 7 de nuestra serie animada "Piensa como en programación". 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 recolectar tres artefactos y deben resolver su camino a través de una serie de rompecabezas de programación.

Lección de Alex Rosenthal, dirigida por Kozmonot Animation Studio.

Ética y Hedge están en la planta baja
de una torre masiva.

Las barreras de energía los separan
del segundo objetivo de su búsqueda:

El Nodo de la Creación.

Para alcanzarlo, Ética debe usar tres
corrientes de energía para subirla.

Al avanzar un temporizador comenzará
la cuenta regresiva de 60 segundos.

Al fondo de la sala
hay una cuenca hecha de torres invisibles

que pueden mantener la energía entre sí.

Después de un minuto,
un torrente de energía

se derramará desde arriba
llenando una unidad a la vez,

con un campo de fuerza que impide
derramarse hacia delante o detrás.

Durante los 60 segundos de calma,

Ética y Hedge deben decidir exactamente
cuántas unidades de energía caerán.

Para cada uno de los tres desafíos,

deben elegir la cantidad
que llenará exactamente la cuenca.

Si lo hacen, la energía los impulsará
más hacia arriba.

Pero si se equivocan en la cantidad,
la elevación de energía fallará,

dejándolos caer.

Diagramas en las paredes
ilustran algunos ejemplos

Esta configuración capturará
exactamente 2 unidades de energía.

Esta configuración capturará 4,
3 aquí y 1 aquí.

Y este también capturará 4,

porque cualquier energía a la derecha
se derramaría.

La energía lloverá de tal manera

que solo se desbordará
si no hay espacio que pueda contenerla.

Hedge puede hacer visible una torre de
bloques a la vez y cuenta lo alta que es,

pero no puede mirar
toda la estructura a la vez.

¿Cómo programa Ética a Hedge
para averiguar

exactamente cuánta energía
puede sostener cada cuenca?

Piensa ahora para resolverlo solo o sola.

Aquí hay una forma de pensar
sobre lo qué esta pasando:

cada célula desocupada retendrá energía

si y solo si hay al final
un muro a su izquierda,

y al final un muro a su derecha.

Pero a Hedge le tomaría mucho tiempo
verificar esto para cada celda individual.

¿Y si tuviera que considerar
una columna entera de bloques a la vez?

¿Cuántas unidades de energía
podrían sostenerse, por ejemplo?

Piensa ahora para resolverlo solo o sola.

Analicemos el problema
mirando nuestro ejemplo.

Hay 5 columnas de bloques aquí.

El que está más a la izquierda
no puede contener energía,

porque no hay nada más alto.

La segunda pila puede
tener 3 unidades encima,

ya que estarían atrapadas
entre estas dos pilas de 4 bloques.

Obtenemos 3 unidades tomando la altura
donde la energía se nivelaría: 4,

y restando la altura de la pila
entonces eso es 4 menos 1.

La tercera pila es similar: 4 a la
izquierda, 4 a la derecha y 3 alto,

entonces tendrá 4 menos 3
es igual a 1 unidad.

La cuarta pila y la quinta pila no tienen
nada más alto que ellas a la derecha,

así que no puedan retener energía.

Podemos adaptar esta idea en un algoritmo.

Considerando una columna a la vez
como punto de referencia,

Hedge puede mirar
hacia la izquierda pila por pila

para encontrar la altura del más alta,

mirar a la derecha
para encontrar la altura más alta

y tomar la más pequeña de las dos
como la altura de la energía puede llenar.

Si el resultado es más alto
que la columna en cuestión,

se resta la altura de la columna original,

y el resultado será el número de unidades
que esa columna puede aguantar.

Si es igual o inferior al nivel
de la columna en cuestión,

la energía se derramaría.

Hedge puede aplicar eso a una cuenca
completa con un bucle que comienza

en la columna de la izquierda y se mueve
a la derecha, una columna a la vez.

En cada columna, ejecuta los mismos pasos:
mira todo el camino hacia el más alto,

hace lo mismo a la derecha,
toma la altura más baja de los dos,

resta la altura original de la columna,

y aumenta el gran total
si ese número es positivo

Su bucle se repetirá
tantas veces como columnas haya.

Eso funcionará, pero llevará
mucho tiempo para una cuenca grande.

A cada paso, Hedge repite la acción.
de mirar a la izquierda y a la derecha.

Si hay N pilas,
mirará todas las N pilas N veces.

¿Hay una manera mas rápida?

Aquí hay un ahorro de tiempo:
antes de hacer cualquier otra cosa,

Hedge puede comenzar a la izquierda,

y mantener una cuenta corriente
de cuál es la pila más alta.

Aquí eso sería 2, 2 otra vez,
ya que el primero fue más alto,

entonces 4, 4, 4.

Luego puede encontrar
las pilas más altas de la derecha

haciendo lo mismo yendo
de derecha a izquierda: 1, 3, 4, 4, 4.

Al final tendrá una mesa
así en su memoria.

Ahora, Hedge puede dar un pasa más
para calcular cuánta energía habrá

sobre cada pila
con la misma ecuación de antes:

tomando el más pequeño de la izquierda
almacenado y valores correctos,

y restando la altura de la torre actual.

En lugar de mirar N pilas N veces,
mirará N pilas solo 3 veces

que es lo que se llama tiempo lineal.

Hay formas de optimizar
la solución aún más,

Pero esto es lo suficientemente
bueno para nuestros héroes.

Ética y Hedge funcionan como una sola.

La primera cascada es muy fácil
y elevan la torre.

La segunda es un poco más dura.

La tercera es enorme
con docenas de pilas de bloques.

El temporizador avanza hacia cero,
pero el programa de Ética es rápido.

Ella pone la rueda en posición
justo a tiempo,

y la energía las levanta
al Nodo de la Creación.

Como el primero, revela una visión:
recuerdos de años pasados.

La máquina del mundo lo cambió todo,

y Ética, en su posición
como ingeniera jefe de robótica,

se preocupó por lo que vio.

Cuando subió el Bradbarrier
para mantener a la gente adentro,

sabía que algo estaba muy mal.

Entonces creó tres artefactos

con la capacidad de restaurar poder,
creatividad y memoria a las personas,

y los pasó de contrabando
a tres comunidades.

Antes de que pudiera decirle
a la gente cómo usarlos,

el gobierno descubrió sus esfuerzos
y envió bots para arrestarla a ella

y a los otros programadores.

De último, Ética usó
la máquina del mundo para crear

un robot que protegería
el dispositivo antiguo

de las fuerzas de la ignorancia
encerrándolo en un laberinto gigante.

A su creación la denominó Hedge.

Sin previo aviso, el elevador
de energía parpadea, luego se esfuma.