Portuguese, Brazilian subtitles

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

Get Embed Code
20 Languages

Showing Revision 14 created 03/09/2020 by Maricene Crus.

  1. Ethic e Hedge estão no andar térreo
    de uma imensa torre.
  2. Barreiras de energia os separam
    do alvo da segunda busca deles:
  3. o "Node da Criação".
  4. Para chegar até ele,
  5. Ethic deve usar três correntes
    de energia para escalar a torre.
  6. Assim que ela avançar, uma contagem
    regressiva de 60 segundos terá início.
  7. Atrás da sala, há um reservatório
    feito de torres invisíveis
  8. que podem reter energia entre elas.
  9. Depois de um minuto,
    uma cascata de energia descerá,
  10. preenchendo uma unidade de cada vez,
    com um campo de força
  11. que impede a dissipação da energia
    para frente ou para trás.
  12. Durante 60 segundos de silêncio,
  13. Ethic e Hedge devem decidir exatamente
    quantas unidades de energia descerão.
  14. Para cada um dos três desafios,
  15. eles devem escolher a quantidade exata
    que preencherá o reservatório.
  16. Se fizerem assim, a energia
    os impulsionará para cima.
  17. Mas se eles usarem a quantidade errada,
    o "elevador de energia" não funcionará,
  18. fazendo com que eles caiam.
  19. Diagramas nas paredes
    ilustram alguns exemplos.
  20. Esta configuração capturará
    exatamente duas unidades de energia.
  21. Esta configuração capturará quatro
    unidades: três aqui e uma aqui.
  22. E esta aqui também capturará
    quatro unidades,
  23. porque qualquer energia
    à direita se dissiparia.
  24. A energia descerá de tal maneira
  25. que somente transbordará
    se não houver espaço para retê-la.
  26. Hedge pode fazer uma torre de blocos
    visíveis de cada vez e calcular a altura,
  27. mas não consegue olhar
    para a estrutura toda de uma só vez.
  28. Como será que Ethic pode programar
    Hedge para que ele descubra
  29. a quantidade exata de energia
    que cada reservatório pode reter?
  30. Um pausa agora
    para que você descubra sozinho.
  31. [Regra 1] [Regra 2]
  32. Eis uma maneira de pensar
    sobre o que está acontecendo:
  33. cada célula vazia reterá energia
  34. somente se houver
    uma parede à sua esquerda
  35. e uma parede à direita.
  36. Mas levaria muito tempo para que Hedge
    verificasse isso para cada célula.
  37. Então, e se ele verificasse uma coluna
    inteira de blocos de cada vez?
  38. Por exemplo, quantas unidades
    de energia ela pode armazenar?
  39. [Uma pausa agora
    para que você descubra sozinho.]
  40. Vamos analisar o problema
    olhando para o nosso exemplo.
  41. Há cinco colunas de blocos aqui.
  42. A da esquerda não pode reter
    qualquer quantidade de energia,
  43. pois não há nada mais alto.
  44. A segunda coluna pode ter
    três unidades acima,
  45. já que elas ficariam presas
    entre estas duas colunas de quatro blocos.
  46. Temos três unidades ao calcular a altura
  47. na qual a energia se nivelaria,
    ou seja, quatro,
  48. e subtraindo a altura da coluna,
    então quatro menos um.
  49. A terceira coluna é parecida:
  50. quatro à esquerda, quatro à direita
    e tem três blocos de altura.
  51. Ou seja, ela reterá quatro menos três,
    que é igual a uma unidade.
  52. A quarta e a quinta colunas
    não têm nada mais alto à direita,
  53. então elas podem reter qualquer energia.
  54. Podemos adaptar essa ideia
    para um algoritmo.
  55. Considerando uma coluna de cada vez
    como o ponto de referência,
  56. Hedge pode olhar para a esquerda,
    coluna por coluna,
  57. para descobrir quanto mede a mais alta,
    olhar para a direita e fazer o mesmo,
  58. e usar a menor das duas como a altura
    a ser preenchida por energia.
  59. Se o resultado for maior
    que a coluna em questão,
  60. subtraia a altura da coluna original,
  61. e o resultado será o número
    de unidades que a coluna pode reter.
  62. Se for igual ou abaixo do nível
    da coluna em questão,
  63. a energia transbordará.
  64. Hedge pode usar um loop para aplicar
    isso a um reservatório inteiro,
  65. que se inicia na coluna à esquerda,
  66. e se move para a direita,
    uma coluna por vez.
  67. Para cada coluna, ele seguirá
    os mesmos passos:
  68. procurar pela mais alta à esquerda,
    fazer o mesmo à direita,
  69. calcular a menor das duas,
    subtrair a altura da coluna original
  70. e aumentar o total geral
    se o número for positivo.
  71. O loop se repetirá
    conforme o número de colunas.
  72. Isso funcionará, mas levará muito tempo
    para verificar um reservatório grande.
  73. A cada passo, Hedge repete a ação
    de olhar à esquerda e à direita.
  74. Se houver colunas N,
    ele deverá olhar para todas elas, N vezes.
  75. Há um modo mais rápido?
  76. Eis como economizar tempo:
  77. antes de fazer qualquer coisa,
    Hedge pode começar à esquerda
  78. e manter um registro
    de qual coluna é a mais alta.
  79. Aqui, seriam dois, novamente dois,
    já que a primeira coluna era mais alta,
  80. então quatro, quatro, quatro.
  81. Assim, ele pode encontrar
    as colunas mais altas à direita
  82. fazendo o mesmo,
    movendo-se da direita à esquerda:
  83. um, três, quatro, quatro, quatro.
  84. Por fim, ele terá na memória
    uma tabela como esta.
  85. Agora, Hedge pode ir além
    para calcular quanta energia haverá
  86. acima de cada coluna,
    com a mesma equação de antes:
  87. utilize o menor dos valores
    armazenados à esquerda e à direita,
  88. e subtraia a altura da torre atual.
  89. Ao invés de olhar para N colunas N vezes,
  90. ele olhará para N colunas
    apenas três vezes,
  91. o que chamamos de "tempo linear".
  92. Há maneiras de otimizar
    a solução ainda mais,
  93. mas isso basta para nossos heróis.
  94. Ethic e Hedge trabalham em conjunto.
  95. A primeira cascata de energia
    é muito fácil, e eles sobem a torre.
  96. A segunda é um pouco mais difícil.
  97. A terceira é grande,
    com dezenas de colunas de blocos.
  98. O tempo se esgota,
    mas o programa de Ethic é rápido.
  99. Ela consegue colocar o volante
    na posição correta bem a tempo,
  100. e a energia os leva até o Node da Criação.
  101. Assim como o primeiro artefato,
    este contém uma visão:
  102. memórias de anos passados.
  103. A máquina do mundo mudou tudo,
  104. e Ethic, na posição
    de engenheira-chefe de robótica,
  105. ficou preocupada com o que viu.
  106. Quando Bradbarrier foi construída
    para aprisionar as pessoas,
  107. Ethic sabia que algo estava muito errado.
  108. Então, ela criou três artefatos
  109. capazes de restaurar o poder,
    a criatividade e a memória das pessoas,
  110. e os contrabandeou para três comunidades.
  111. Antes que ela pudesse dizer
    às pessoas como usá-los,
  112. o governo descobriu
    suas intenções e enviou os robôs
  113. para prendê-la e os outros programadores.
  114. Ethic usou a máquina do mundo
    para criar uma última coisa:
  115. um robô que protegeria o artefato antigo
    das forças da ignorância,
  116. encerrando-o em um enorme labirinto.
  117. Ela deu o nome de Hedge à sua criação.
  118. Sem nenhum aviso, a corrente de energia
    oscila e então é interrompida.