A Torre da Epifania | Pense Como um Programador, Episódio 7

Veja a lição completa: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

Este é o sétimo episódio de nossa série de animação “Pense Como um Programador”. Esta narrativa de dez episódios acompanha uma garota, Ethic, e seu amigo robô, Hedge, enquanto tentam salvar o mundo. Os dois embarcam em uma missão para reunir três artefatos e devem encontrar o caminho, passando por uma série de enigmas de programação. Lição de Alex Rosenthal, dirigido por Kozmonot Animation Studio.

Ethic e Hedge estão no andar térreo
de uma imensa torre.

Barreiras de energia os separam
do alvo da segunda busca deles:

o "Node da Criação".

Para chegar até ele,

Ethic deve usar três correntes
de energia para escalar a torre.

Assim que ela avançar, uma contagem
regressiva de 60 segundos terá início.

Atrás da sala, há um reservatório
feito de torres invisíveis

que podem reter energia entre elas.

Depois de um minuto,
uma cascata de energia descerá,

preenchendo uma unidade de cada vez,
com um campo de força

que impede a dissipação da energia
para frente ou para trás.

Durante 60 segundos de silêncio,

Ethic e Hedge devem decidir exatamente
quantas unidades de energia descerão.

Para cada um dos três desafios,

eles devem escolher a quantidade exata
que preencherá o reservatório.

Se fizerem assim, a energia
os impulsionará para cima.

Mas se eles usarem a quantidade errada,
o "elevador de energia" não funcionará,

fazendo com que eles caiam.

Diagramas nas paredes
ilustram alguns exemplos.

Esta configuração capturará
exatamente duas unidades de energia.

Esta configuração capturará quatro
unidades: três aqui e uma aqui.

E esta aqui também capturará
quatro unidades,

porque qualquer energia
à direita se dissiparia.

A energia descerá de tal maneira

que somente transbordará
se não houver espaço para retê-la.

Hedge pode fazer uma torre de blocos
visíveis de cada vez e calcular a altura,

mas não consegue olhar
para a estrutura toda de uma só vez.

Como será que Ethic pode programar
Hedge para que ele descubra

a quantidade exata de energia
que cada reservatório pode reter?

Um pausa agora
para que você descubra sozinho.

[Regra 1] [Regra 2]

Eis uma maneira de pensar
sobre o que está acontecendo:

cada célula vazia reterá energia

somente se houver
uma parede à sua esquerda

e uma parede à direita.

Mas levaria muito tempo para que Hedge
verificasse isso para cada célula.

Então, e se ele verificasse uma coluna
inteira de blocos de cada vez?

Por exemplo, quantas unidades
de energia ela pode armazenar?

[Uma pausa agora
para que você descubra sozinho.]

Vamos analisar o problema
olhando para o nosso exemplo.

Há cinco colunas de blocos aqui.

A da esquerda não pode reter
qualquer quantidade de energia,

pois não há nada mais alto.

A segunda coluna pode ter
três unidades acima,

já que elas ficariam presas
entre estas duas colunas de quatro blocos.

Temos três unidades ao calcular a altura

na qual a energia se nivelaria,
ou seja, quatro,

e subtraindo a altura da coluna,
então quatro menos um.

A terceira coluna é parecida:

quatro à esquerda, quatro à direita
e tem três blocos de altura.

Ou seja, ela reterá quatro menos três,
que é igual a uma unidade.

A quarta e a quinta colunas
não têm nada mais alto à direita,

então elas podem reter qualquer energia.

Podemos adaptar essa ideia
para um algoritmo.

Considerando uma coluna de cada vez
como o ponto de referência,

Hedge pode olhar para a esquerda,
coluna por coluna,

para descobrir quanto mede a mais alta,
olhar para a direita e fazer o mesmo,

e usar a menor das duas como a altura
a ser preenchida por energia.

Se o resultado for maior
que a coluna em questão,

subtraia a altura da coluna original,

e o resultado será o número
de unidades que a coluna pode reter.

Se for igual ou abaixo do nível
da coluna em questão,

a energia transbordará.

Hedge pode usar um loop para aplicar
isso a um reservatório inteiro,

que se inicia na coluna à esquerda,

e se move para a direita,
uma coluna por vez.

Para cada coluna, ele seguirá
os mesmos passos:

procurar pela mais alta à esquerda,
fazer o mesmo à direita,

calcular a menor das duas,
subtrair a altura da coluna original

e aumentar o total geral
se o número for positivo.

O loop se repetirá
conforme o número de colunas.

Isso funcionará, mas levará muito tempo
para verificar um reservatório grande.

A cada passo, Hedge repete a ação
de olhar à esquerda e à direita.

Se houver colunas N,
ele deverá olhar para todas elas, N vezes.

Há um modo mais rápido?

Eis como economizar tempo:

antes de fazer qualquer coisa,
Hedge pode começar à esquerda

e manter um registro
de qual coluna é a mais alta.

Aqui, seriam dois, novamente dois,
já que a primeira coluna era mais alta,

então quatro, quatro, quatro.

Assim, ele pode encontrar
as colunas mais altas à direita

fazendo o mesmo,
movendo-se da direita à esquerda:

um, três, quatro, quatro, quatro.

Por fim, ele terá na memória
uma tabela como esta.

Agora, Hedge pode ir além
para calcular quanta energia haverá

acima de cada coluna,
com a mesma equação de antes:

utilize o menor dos valores
armazenados à esquerda e à direita,

e subtraia a altura da torre atual.

Ao invés de olhar para N colunas N vezes,

ele olhará para N colunas
apenas três vezes,

o que chamamos de "tempo linear".

Há maneiras de otimizar
a solução ainda mais,

mas isso basta para nossos heróis.

Ethic e Hedge trabalham em conjunto.

A primeira cascata de energia
é muito fácil, e eles sobem a torre.

A segunda é um pouco mais difícil.

A terceira é grande,
com dezenas de colunas de blocos.

O tempo se esgota,
mas o programa de Ethic é rápido.

Ela consegue colocar o volante
na posição correta bem a tempo,

e a energia os leva até o Node da Criação.

Assim como o primeiro artefato,
este contém uma visão:

memórias de anos passados.

A máquina do mundo mudou tudo,

e Ethic, na posição
de engenheira-chefe de robótica,

ficou preocupada com o que viu.

Quando Bradbarrier foi construída
para aprisionar as pessoas,

Ethic sabia que algo estava muito errado.

Então, ela criou três artefatos

capazes de restaurar o poder,
a criatividade e a memória das pessoas,

e os contrabandeou para três comunidades.

Antes que ela pudesse dizer
às pessoas como usá-los,

o governo descobriu
suas intenções e enviou os robôs

para prendê-la e os outros programadores.

Ethic usou a máquina do mundo
para criar uma última coisa:

um robô que protegeria o artefato antigo
das forças da ignorância,

encerrando-o em um enorme labirinto.

Ela deu o nome de Hedge à sua criação.

Sem nenhum aviso, a corrente de energia
oscila e então é interrompida.