A Bifurcação| Pensa como um programador, Episódio 8

Vejam a lição completa: https://ed.ted.com/lessons/the-gauntlet-think-like-a-coder-ep-8

Este é o episódio 8 da nossa série animada "Pensa como um Programador". Esta narrativa em 10 episódios acompanha uma rapariga, a Ética, e o Hedge, o seu companheiro robô, quando os dois tentam salvar o mundo. Os dois entram numa demanda para reunir três artefactos e têm de descobrir o caminho, através duma série de "puzzles" de programação.

Lição de Alex Rosenthal, realização de Kozmonot Animation Studio.

Quando caem da torre,
a Ética e o Hedge

mergulham nas águas revoltas
de um rio de pura energia.

Esta torrente flui da Bradbarrier
até ao Huxenborg.

Aí, uma cidade inteira de fábricas

fabrica os robôs e alberga
o Nódulo da Memória,

o último dos três poderosos artefactos
que a Ética tem de reunir.

Ao fim de um longo dia
e de uma noite ainda mais longa,

encontram-se num desfiladeiro
de tijolo e aço.

Quando estão prestes a chegar
ao fim da linha,

são apanhados por uma corda.

Lemma, a sua salvadora,
tem estado à espera deles.

Quando a Ética conquistou
o Nódulo da Criação na torre da floresta,

as rádios de todo o país
voltaram a entrar em atividade.

Adila, a líder da resistência,

iniciou imediatamente os contactos
com as suas aliadas,

entre as quais Lemma, a mais importante,

uma brilhante cientista
que trabalha em Huxenborg

para eliminar as máquinas

Infelizmente, os rádios
também alertaram os robôs.

Por isso, eles tomaram
medidas defensivas

para protegerem o último artefacto
no seu esconderijo, no centro da cidade.

Só há um caminho para lá chegar:
o desafio dos caminhos bifurcados.

É uma série mortal
de tapetes rolantes luminosos

que serpenteiam no subsolo de Huxenborg.

A partir da posição atual,

cada secção percorre uma certa distância
e depois divide-se em duas.

Cada ramal faz o mesmo,
e assim sucessivamente.

Há milhares de ramais.

Só um dos caminhos leva ao artefacto,
todos os outros levam à destruição.

Felizmente, o Nódulo da Criação
conferiu ao Hedge um poder estranho:

o Hedge pode produzir versões
mais pequenas de si mesmo.

Cada versão só pode fazer duas coisas;

prestar informações por rádio
ao seu progenitor,

e produzir versões
um pouco mais pequenas de si mesmo

que, por sua vez, podem fazer
as mesmas duas coisas,

tal como os seus filhos,

por tantas gerações
quantas sejam necessárias.

Uma patrulha está a aproximar-se
da posição deles,

por isso o tempo da Ética é limitado.

Que instruções deve dar ao Hedge
para encontrar o único caminho seguro?

[Suspende aqui o vídeo
para resolveres sozinho.]

[Hedge e as suas cópias podem entrar
e sair do sistema de tapetes rolantes

[mas não podem voltar atrás.]

Os programadores têm uma ferramenta
no seu arsenal, chamada "recursão".

A recursão é quando temos um conjunto
de instruções que se referem a si mesmas.

É como usar uma palavra
na sua própria definição.

Exceto quando é mal entendida,
é duma eficácia extraordinária.

A recursão envolve a repetição,
mas duma forma diferente do "loop",

Enquanto um "loop" faz uma ação
e repete-a vezes sem conta,

a recursão começa uma ação
e, antes de a terminar, usa-a de novo,

e antes de esta terminar,
usa-a outra vez, e assim sucessivamente.

Continua a fazer isso
até chegar a qualquer estado final.

Depois, passa a informação
para trás, passo por passo,

até chegar ao topo e terminar o ciclo.

A recursão é ideal para problemas
que envolvem autossemelhança,

em que cada parte é parecida
com o todo.

Como, por exemplo,
um sistema de defesa mortal

concebido para acabar
com qualquer pessoa ou coisa

que se atreva a percorrê-lo.

[Suspende aqui o vídeo
para resolveres sozinho.]

[Solução em 3:
Solução em 2:

[Solução em: 1]

O quebra-cabeças da Ética
parece estender-se à superfície

mas há uma solução muito simples
se usarmos a recursão.

Para a encontrar, vamos primeiro observar

a versão mais simples
deste quebra-cabeças:

E se todo o labirinto
tivesse apenas duas vias?

Se Hedge se copiar a si mesmo,

a cópia que percorrer
o caminho errado será destruída.

Portanto, a outra, que chega ao artefacto,

pode transmitir por rádio
o caminho que tomou

e, portanto, qualquer que seja
o caminho correto,

será essa a informação
que o Hedge receberá.

Isto chama-se o "caso base" da recursão.

Suponhamos agora que o labirinto
se ramifica em dois no ponto de partida

e, em cada interseção,
as cópias do Hedge

— chamemos-lhe Twig 1 e Twig 2 —

fazem novas cópias
— chamemos-lhe Leave 1 a 4.

Três Leaves serão destruídas.

A única que chegar ao artefacto
enviará por rádio a resposta correta

mas apenas para o seu progenitor.

Portanto, se o Twig 1 ou 2 estão à espera
numa interseção

e ouvem qualquer coisa pela rádio,

é o caminho certo
para chegar ao artefacto

a partir do sítio onde estão.

Para dar ao Hedge a resposta correta,
a partir da sua perspetiva,

o Twig tem de dizer
qual o caminho que percorreu

e depois esse caminho
é ouvido pelo rádio.

Este mesmo processo funciona sempre

sejam quantos forem
os ramais do labirinto.

Qualquer resposta
que uma cópia oiça por rádio

tem de ser o caminho
para a sala de controlo

a partir do local onde se encontra

e se acrescentar
qual o ramal que se seguiu,

pode indicar ao seu progenitor
como lá chegar.

Podemos resumir as instruções
numa ação chamada Pathfinder

que todas as versões do Hedge cumprirão:

1. Se chegares ao artefacto,

informa por rádio o teu progenitor

se lá chegaste virando
à direita ou à esquerda.

2. Quando chegares a uma interseção,
sai do tapete rolante

e envia novas cópias pelas vias
da direita e da esquerda.

Pede-lhes que sigam
o programa Pathfinder.

É aqui que entra a recursão.

Isto pode acontecer muitas vezes
antes da última instrução, que é:

3. Se ouvires qualquer coisa por rádio,
informa por rádio o teu progenitor

se a recebeste no teu local
pela esquerda ou pela direita,

e depois repete tudo
o que acabaste de ouvir.

O Pathfinder é um exemplo daquilo
a que os programadores chamam funções,

sub-rotinas ou procedimentos.

Qualquer que seja a terminologia,
a ideia é a mesma.

É um conjunto de instruções
a que se dá um nome,

para poderem ser facilmente reutilizadas

— talvez pelo próprio.

No nosso caso, isso funciona perfeitamente

— uma rede inteira de vias mapeadas
que usam apenas três instruções.

Então, o que acontece é isto:

Quando a patrulha aparece à esquina,
a Ética e a Lemma arranjaram disfarces.

Tentam distrair os robôs
para o Hedge ter tempo suficiente.

Por fim, o rádio do Hedge crepita
indicando uma série de direções.

Os três mergulham no tapete rolante
e fogem a sete pés.

com um esquadrão de robôs polícias
em sua perseguição.