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.