Portuguese subtitles

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

Get Embed Code
20 Languages

Showing Revision 25 created 03/25/2020 by Margarida Ferreira.

  1. A Ética e o Hedge estão no piso térreo
    de uma torre enorme.
  2. Barreiras de energia separam-nos
    do seu segundo objetivo:
  3. o Nódulo da Criação.
  4. Para alcançá-lo, a Ética tem de usar três
    fluxos de energia para subir a torre.
  5. Assim que der um passo,
  6. um temporizador começará uma contagem
    decrescente de 60 segundos.
  7. No fundo da sala há
    um reservatório de torres invisíveis
  8. que podem reter a energia entre elas.
  9. Após um minuto, cai do alto
    uma torrente de energia,
  10. enchendo uma unidade de cada vez,
  11. com um campo de forças que impede
    derrames pela frente ou por trás.
  12. Durante esses calmos 60 segundos,
  13. a Ética e o Hedge têm de decidir o número
    exato de unidades de energia que vão cair.
  14. Para cada um dos três desafios,
  15. têm de escolher a quantidade exata
    que irá preencher o reservatório.
  16. Se o fizerem, a energia
    irá impulsioná-los para cima.
  17. Mas, se a quantidade for a errada,
    o elevador de energia irá falhar,
  18. e eles cairão.
  19. Os diagramas nas paredes
    ilustram alguns exemplos,
  20. Esta configuração irá capturar
    exatamente duas unidades de energia.
  21. Esta configuração irá capturar quatro:
    três aqui e uma aqui.
  22. E nesta também capturará quatro,
  23. uma vez que qualquer energia
    à direita transbordará.
  24. A energia cairá de uma forma
  25. que só transbordará
    se não houver espaço para a conter.
  26. O Hedge pode tornar visível
    uma coluna de blocos de cada vez
  27. e contar a sua altura,
  28. mas não poderá ver
    a estrutura inteira de uma só vez.
  29. Como irá a Ética programar
    o Hedge para calcular
  30. a capacidade exata de energia
    de cada reservatório?
  31. Faz uma pausa agora
    para chegares à solução sozinho.
  32. [Cada bacia tem uma série de torres
    de blocos que retêm a energia entre elas]
  33. [Hedge tem de calcular quantas unidades
    de energia uma dada bacia pode conter]
  34. Eis uma forma de pensar
    no que está a acontecer:
  35. cada célula vazia pode reter energia
  36. apenas e se existir
    uma parede à sua esquerda
  37. e uma parede à sua direita.
  38. Mas Hedge levaria demasiado tempo
    a verificar cada célula individual.
  39. E se em vez disso considerarmos
    uma coluna de blocos de cada vez?
  40. Por exemplo, quantas unidades de energia
    poderá esta coluna reter?
  41. Faz uma pausa agora para tentares
    chegar à solução sozinho.
  42. Vamos analisar o problema
    olhando para o nosso exemplo.
  43. Temos aqui cinco colunas de blocos.
  44. A coluna mais à esquerda
    não pode reter energia,
  45. porque não há nada mais alta que ela.
  46. A segunda coluna pode
    reter três unidades acima dela,
  47. uma vez que elas ficarão presas
    entre estas duas colunas de quatro blocos.
  48. Obtemos três unidades medindo a altura
    da coluna onde a energia ficará nivelada:
  49. — ou seja, quatro —
  50. e subtraindo-lhe a altura da coluna
    — ou seja, quatro menos um.
  51. A terceira coluna é similar
  52. — quatro à esquerda,
    quatro à direita, e três de altura,
  53. por isso manterá quatro menos
    três, ou seja, uma unidade.
  54. A quarta e a quinta colunas
    não têm nada mais alto que elas à direita,
  55. logo não podem reter nenhuma energia.
  56. Podemos adaptar esta ideia a um logaritmo.
  57. Considerando só uma coluna de cada vez
    como ponto de referência,
  58. o Hedge pode olhar para a esquerda,
    coluna a coluna,
  59. para encontrar a altura da mais alta.
  60. e olhar para a direita para encontrar
    a altura da mais alta.
  61. e considerar a mais baixa das duas
  62. como o limite máximo
    de contenção de energia.
  63. Se o resultado for mais alto
    do que a coluna em questão,
  64. subtraímos a altura da coluna original,
  65. e o resultado será o número de unidades
    que a coluna pode conter.
  66. Se for igual ou abaixo do nível
    da coluna em questão,
  67. a energia iriá transbordar.
  68. O Hedge pode aplicar isso a todo
    o reservatório com um "loop"
  69. que começa na coluna mais à esquerda
  70. e vai avançando para a direita,
    uma coluna de cada vez.
  71. Para cada coluna, dará os mesmos passos
  72. — ver a mais alta à esquerda,
    fazer o mesmo à direita,
  73. pegar na altura da mais baixa,
  74. subtrair a altura da coluna original,
  75. e adicionando ao total
    se o resultado for positivo.
  76. Este "loop" repete-se tantas vezes
    quanto o número de colunas.
  77. Isto poderá resultar, mas irá
    demorar se o reservatório for grande.
  78. A cada passo o Hedge repete a ação
    de olhar para a esquerda e para a direita.
  79. Se houver "n" colunas,
    olha "n" vezes para "n" colunas.
  80. Existirá uma forma mais rápida?
  81. Eis uma forma de poupar tempo:
    antes de qualquer coisa,
  82. ele pode começar pela esquerda.
  83. e manter uma contagem
    de qual é a coluna mais alta.
  84. Aqui seria dois, dois de novo,
    uma vez que a primeira era maior,
  85. depois quatro, quatro, quatro.
  86. Pode depois descobrir
    a mais alta à direita
  87. fazendo o mesmo
    da direita para a esquerda:
  88. Um, três, quatro, quatro quatro.
  89. No fim, terá uma tabela como esta
    na sua memória.
  90. Agora, o Hedge poderá dar mais um passo
    para calcular quanta energia
  91. será necessária
    usando a mesma equação anterior:
  92. verificar os valores das colunas
    mais baixas à esquerda e à direita,
  93. e subtrair a altura da coluna atual.
  94. Ao invés de verificar
    "n" colunas "n" vezes,
  95. irá verificar "n" colunas
    apenas três vezes,
  96. ao que chamamos "tempo linear".
  97. Existem formas de otimizar
    ainda mais esta solução,
  98. mas é o suficiente para os nossos heróis.
  99. A Ética e o Hedge
    trabalham como um só.
  100. A primeira cascata
    é fácil e ascendem na torre.
  101. A segunda um pouco mais difícil.
  102. A terceira é enorme
    com dezenas de colunas de blocos.
  103. O temporizador não para,
    mas o programa da Ética é veloz.
  104. Consegue colocar a manivela
    em posição mesmo a tempo,
  105. e a energia eleva-os
    até ao Nódulo da Criação.
  106. Tal como o primeiro, revela uma visão:
    a memória de anos passados.
  107. A máquina do mundo mudou tudo,
  108. e a Ética, na sua posição
    de engenheira chefe de robótica,
  109. ficou preocupada com o que viu.
  110. Quando a Bradbarreira surgiu
    para impedir as pessoas de sair,
  111. ela percebeu que algo
    estava mesmo muito mal.
  112. Por isso ela criou três artefatos
  113. com o poder de restaurar o poder,
    a criatividade e a memória das pessoas,
  114. e escondeu-as em três comunidades.
  115. Antes de poder ensinar
    as pessoas a usá-las,
  116. o governo soube das suas intenções
    e enviou robôs para a prender
  117. e aos outros programadores.
  118. A última coisa que a Ética criou
    com a máquina do mundo,
  119. foi um robô que protegesse
    o aparelho ancestral
  120. das forças da ignorância,
    fechando-a num labirinto gigante.
  121. Chamou Hedge à sua criação.
  122. Sem aviso prévio, o elevador de energia
    começa a piscar e apaga-se.