A Torre da Epifania | Pensem como um Programador, Episódio 7

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

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

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

A Ética e o Hedge estão no piso térreo
de uma torre enorme.

Barreiras de energia separam-nos
do seu segundo objetivo:

o Nódulo da Criação.

Para alcançá-lo, a Ética tem de usar três
fluxos de energia para subir a torre.

Assim que der um passo,

um temporizador começará uma contagem
decrescente de 60 segundos.

No fundo da sala há
um reservatório de torres invisíveis

que podem reter a energia entre elas.

Após um minuto, cai do alto
uma torrente de energia,

enchendo uma unidade de cada vez,

com um campo de forças que impede
derrames pela frente ou por trás.

Durante esses calmos 60 segundos,

a Ética e o Hedge têm de decidir o número
exato de unidades de energia que vão cair.

Para cada um dos três desafios,

têm de escolher a quantidade exata
que irá preencher o reservatório.

Se o fizerem, a energia
irá impulsioná-los para cima.

Mas, se a quantidade for a errada,
o elevador de energia irá falhar,

e eles cairão.

Os diagramas nas paredes
ilustram alguns exemplos,

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

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

E nesta também capturará quatro,

uma vez que qualquer energia
à direita transbordará.

A energia cairá de uma forma

que só transbordará
se não houver espaço para a conter.

O Hedge pode tornar visível
uma coluna de blocos de cada vez

e contar a sua altura,

mas não poderá ver
a estrutura inteira de uma só vez.

Como irá a Ética programar
o Hedge para calcular

a capacidade exata de energia
de cada reservatório?

Faz uma pausa agora
para chegares à solução sozinho.

[Cada bacia tem uma série de torres
de blocos que retêm a energia entre elas]

[Hedge tem de calcular quantas unidades
de energia uma dada bacia pode conter]

Eis uma forma de pensar
no que está a acontecer:

cada célula vazia pode reter energia

apenas e se existir
uma parede à sua esquerda

e uma parede à sua direita.

Mas Hedge levaria demasiado tempo
a verificar cada célula individual.

E se em vez disso considerarmos
uma coluna de blocos de cada vez?

Por exemplo, quantas unidades de energia
poderá esta coluna reter?

Faz uma pausa agora para tentares
chegar à solução sozinho.

Vamos analisar o problema
olhando para o nosso exemplo.

Temos aqui cinco colunas de blocos.

A coluna mais à esquerda
não pode reter energia,

porque não há nada mais alta que ela.

A segunda coluna pode
reter três unidades acima dela,

uma vez que elas ficarão presas
entre estas duas colunas de quatro blocos.

Obtemos três unidades medindo a altura
da coluna onde a energia ficará nivelada:

— ou seja, quatro —

e subtraindo-lhe a altura da coluna
— ou seja, quatro menos um.

A terceira coluna é similar

— quatro à esquerda,
quatro à direita, e três de altura,

por isso manterá quatro menos
três, ou seja, uma unidade.

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

logo não podem reter nenhuma energia.

Podemos adaptar esta ideia a um logaritmo.

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

o Hedge pode olhar para a esquerda,
coluna a coluna,

para encontrar a altura da mais alta.

e olhar para a direita para encontrar
a altura da mais alta.

e considerar a mais baixa das duas

como o limite máximo
de contenção de energia.

Se o resultado for mais alto
do que a coluna em questão,

subtraímos a altura da coluna original,

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

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

a energia iriá transbordar.

O Hedge pode aplicar isso a todo
o reservatório com um "loop"

que começa na coluna mais à esquerda

e vai avançando para a direita,
uma coluna de cada vez.

Para cada coluna, dará os mesmos passos

— ver a mais alta à esquerda,
fazer o mesmo à direita,

pegar na altura da mais baixa,

subtrair a altura da coluna original,

e adicionando ao total
se o resultado for positivo.

Este "loop" repete-se tantas vezes
quanto o número de colunas.

Isto poderá resultar, mas irá
demorar se o reservatório for grande.

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

Se houver "n" colunas,
olha "n" vezes para "n" colunas.

Existirá uma forma mais rápida?

Eis uma forma de poupar tempo:
antes de qualquer coisa,

ele pode começar pela esquerda.

e manter uma contagem
de qual é a coluna mais alta.

Aqui seria dois, dois de novo,
uma vez que a primeira era maior,

depois quatro, quatro, quatro.

Pode depois descobrir
a mais alta à direita

fazendo o mesmo
da direita para a esquerda:

Um, três, quatro, quatro quatro.

No fim, terá uma tabela como esta
na sua memória.

Agora, o Hedge poderá dar mais um passo
para calcular quanta energia

será necessária
usando a mesma equação anterior:

verificar os valores das colunas
mais baixas à esquerda e à direita,

e subtrair a altura da coluna atual.

Ao invés de verificar
"n" colunas "n" vezes,

irá verificar "n" colunas
apenas três vezes,

ao que chamamos "tempo linear".

Existem formas de otimizar
ainda mais esta solução,

mas é o suficiente para os nossos heróis.

A Ética e o Hedge
trabalham como um só.

A primeira cascata
é fácil e ascendem na torre.

A segunda um pouco mais difícil.

A terceira é enorme
com dezenas de colunas de blocos.

O temporizador não para,
mas o programa da Ética é veloz.

Consegue colocar a manivela
em posição mesmo a tempo,

e a energia eleva-os
até ao Nódulo da Criação.

Tal como o primeiro, revela uma visão:
a memória de anos passados.

A máquina do mundo mudou tudo,

e a Ética, na sua posição
de engenheira chefe de robótica,

ficou preocupada com o que viu.

Quando a Bradbarreira surgiu
para impedir as pessoas de sair,

ela percebeu que algo
estava mesmo muito mal.

Por isso ela criou três artefatos

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

e escondeu-as em três comunidades.

Antes de poder ensinar
as pessoas a usá-las,

o governo soube das suas intenções
e enviou robôs para a prender

e aos outros programadores.

A última coisa que a Ética criou
com a máquina do mundo,

foi um robô que protegesse
o aparelho ancestral

das forças da ignorância,
fechando-a num labirinto gigante.

Chamou Hedge à sua criação.

Sem aviso prévio, o elevador de energia
começa a piscar e apaga-se.