La bifurcación| Piensa como un programador, Episodio 8

Mira la lección completa en https://ed.ted.com/lessons/the-gauntlet-think-like-a-coder-ep-8

Este es el episodio 8 de nuestra serie animada "Piensa como un programador". Esta narrativa de 10 episodios sigue a una niña, Ética, y 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.

PIENSA COMO UN PROGRAMADOR

EPISODIO 8: LA BIFURCACIÓN

La caída desde la torre
envía a Ética y Hedge

a girar dentro de los rápidos
de un río de energía pura.

Este torrente fluye desde el Bradbarrier
todo el camino a Huxenborg.

Allí, en una ciudad entera de fábricas

construyen los robots y albergan
el Nodo de la Memoria,

el último de los tres artefactos
que Ética necesita recolectar.

Después de un largo día
y una noche aún más larga

se encuentran en un cañón
de ladrillo y acero.

Justo cuando van a alcanzar
el fin de la línea,

una cuerda los atrapa.

Su salvadora, Lemma,
los ha estado esperando.

Cuando Ética reclamó el Nodo de Creación
de la torre del bosque,

las radios de todo el país
volvieron a la vida.

Adila, la líder de la resistencia,
comenzó a contactar a sus aliados,

nada más importante que Lemma,

una científica genial que trabaja dentro
de Huxenborg para derribar las máquinas.

Desafortunadamente,
las radios también avisaron a los robots.

Por ello, han tomado medidas defensivas

para proteger el artefacto final
en su hogar en el corazón de la ciudad.

Solo hay una forma de llegar:
un desafiante camino de bifurcaciones.

Es una serie mortal de conductos luminosos
que serpentean por debajo de Huxenborg.

Empezando desde la posición actual,

cada sección recorre una distancia,
luego se divide en dos.

Cada rama hace lo mismo,
una y otra vez.

Hay miles de ramas.

Solo un camino conduce al artefacto;
todos los demás a la destrucción.

Afortunadamente, el Nodo de Creación
le ha otorgado a Hedge un extraño poder:

puede producir versiones
un poco más pequeñas de sí mismo.

Cada versión puede hacer solo dos cosas:

devolver información
por radio a la matriz,

y producir versiones
un poco más pequeñas de sí mismas...

quienes pueden hacer las mismas dos cosas,
al igual que sus copias,

durante tantas generaciones
como sea necesario.

Un patrulla se acerca a su posición,
así que el tiempo de Ética es limitado.

¿Qué instrucciones debería darle a Hedge
para encontrar el único camino seguro?

[Pausa el vídeo para resolverlo tú mismo]

Pista en: 3

Pista en: 2

Pista en: 1

Los programadores tienen
una elegante herramienta en su arsenal

llamada recursión.

La recursión es cuando
tienes un conjunto de instrucciones

que se refieren a sí mismo.

Es como usar una palabra
en su propia definición,

y aunque eso está mal visto,
es increíblemente efectivo.

La recursión implica la repetición,
pero de una manera diferente a los bucles.

Donde un bucle realiza una acción
y la repite una y otra vez,

la recursión inicia una acción,
y antes de que termine, la usa de nuevo,

y antes de que esa termine,
la usa de nuevo, y así sucesivamente.

Sigue haciendo esto hasta que
se alcanza algún estado final.

Luego pasa la información
de vuelta, capa tras capa,

hasta que alcanza la parte superior
y finaliza el ciclo.

La recursión es ideal para problemas
que implican autosimilitud,

en los que cada parte
se asemeja a un todo mayor.

Como, por ejemplo,
un sistema de defensa mortal

diseñado para acabar
con cualquier persona o cosa

que se atreva a pisarlo.

[Pausa el vídeo para resolverlo tú mismo]

Solución en: 3

Solución en: 2

Solución en: 1

El enigma de Ética parece
extenderse en la superficie,

pero hay una solución
notablemente simple usando la recursión.

Para encontrarlo,
veamos primero la versión más simple

de este rompecabezas:

¿Y si todo el laberinto
fueran solo dos caminos?

Si Hedge se copia a sí mismo,
la copia que va por el camino equivocado

será destruida.

Así que el otro,
que alcanzará el artefacto,

puede transmitir por radio
el camino que tomó,

y luego, sin importar
qué camino sea el correcto,

esa es la respuesta que recibirá Hedge.

Esto se llama el "caso base"
de la recursión.

Ahora, supongamos que el laberinto

se ramifica dos veces
desde el punto de partida,

y en cada intersección,
las copias de Hedge,

llamémoslas Twig 1 y Twig 2,

hacen más copias,

llamémoslas Leaves 1 a la 4.

Tres Leaves serán destruidas.

La que alcance el artefacto enviará
por radio la respuesta correcta,

pero solo a su matriz.

Así que si Twig 1 o 2
está esperando en una intersección

y oye algo por la radio,

ese es el camino correcto
de ir al artefacto desde donde está.

Para darle a Hedge la respuesta correcta
desde su perspectiva,

El Twig debería decir por dónde fue,

y luego la ruta que acaba
de escuchar en la radio.

Este mismo proceso funcionará
sin importar cuántas veces

se ramifique el laberinto.

Cualquier respuesta
que una copia escuche en la radio

debe ser el camino a
la sala de control desde su ubicación,

y si luego agrega el camino que tomó,

puede decirle a su matriz cómo llegar.

Podemos resumir las instrucciones
en una acción llamada Pathfinder

que cada versión de Hedge seguirá:

1. Si has alcanzado el artefacto,

avisa por radio a tu matriz si llegaste
yendo a la izquierda o a la derecha.

2. Cuando llegues a una intersección,
sal del conducto

y envía nuevas copias por los caminos
de la izquierda y la derecha.

Haz que cada uno ejecute el Pathfinder.

Aquí es donde la recursión entra en juego,

y esto puede suceder muchas veces

antes de que se desencadene
la última instrucción, que es:

3. Si escuchas algo en la radio,
debes decirle a tu matriz

si llegaste a tu lugar yendo
a la izquierda o a la derecha,

y luego repetir todo
lo que acabas de escuchar.

Pathfinder es un ejemplo
de lo que los programadores llaman

funciones, subrutinas o procedimientos.

No importa la terminología,
la idea es la misma:

es un conjunto de instrucciones
con una etiqueta

para que pueda ser fácilmente reutilizado,
tal vez incluso por sí mismo.

Y en nuestro caso
eso funcionará perfectamente,

una red entera de caminos mapeados
usando solo tres instrucciones.

Así que esto es lo que pasa.

Para cuando la patrulla
llegue a la esquina,

Ética y Lemma
habrán improvisado disfraces.

Tratan de confundir
a los bots lo suficiente

para comprarle tiempo a Hedge.

Finalmente, la radio de Hedge cobra vida
con una serie de direcciones.

Los tres saltan por el conducto
y huyen para salvar sus vidas,

con un escuadrón de robots
ejecutores persiguiéndolos.