English subtitles

← The Tower of Epiphany | Think Like A Coder, Ep 7

Get Embed Code
20 Languages

Showing Revision 2 created 02/27/2020 by lauren mcalpine .

  1. Ethic and Hedge are on the ground floor
    of a massive tower.
  2. Barriers of energy separate them
    from their quest’s second goal:
  3. the Node of Creation.
  4. To reach it, Ethic must use
    three energy streams to climb the tower.
  5. As soon as she steps forward a timer
    will begin counting down from 60 seconds.
  6. At the back of the room
    there’s a basin made of invisible towers
  7. that can hold energy between them.
  8. After one minute, a torrent of energy
    will pour down from above,
  9. filling one unit at a time,
  10. with a force field preventing it
    from spilling out the front or back.
  11. During the 60 calm seconds,
  12. Ethic and Hedge must decide exactly
    how many units of energy will fall.
  13. For each of the three challenges,
  14. they must choose the amount
    that will fill the basin exactly.
  15. If they do so, the energy will propel them
    further upwards.
  16. But if they get the amount at all wrong,
    the energy lift will fail,
  17. dropping them.
  18. Diagrams on the walls
    illustrate some examples.
  19. This configuration
    will capture exactly 2 units of energy.
  20. This configuration will capture 4—
    3 here, and 1 here.
  21. And this one will also capture 4,
  22. because any energy on the right
    would spill out.
  23. The energy will rain down in such a way
  24. that it’ll only overflow
    if there’s no space that could hold it.
  25. Hedge can make one tower of blocks visible
    at a time and count how tall it is,
  26. but he can’t look at
    the whole structure all at once.
  27. How does Ethic program Hedge
    to figure out
  28. exactly how much energy
    each basin can hold?
  29. Pause now to figure it out for yourself.
  30. Here’s one way of thinking about
    what’s happening:
  31. each unoccupied cell will hold energy
  32. if and only if there is a wall
    eventually to its left,
  33. and a wall eventually to its right.
  34. But it would take a long time for Hedge
    to check this for each individual cell.
  35. So what if he were to consider
    a whole column of blocks at a time?
  36. How many units of energy
    can this hold, for instance?
  37. Pause now to figure it out for yourself.
  38. Let’s analyze the problem
    by looking at our example.
  39. There are 5 columns of blocks here.
  40. The leftmost one can’t hold any energy,
    because there’s nothing higher than it.
  41. The 2nd stack can have 3 units above it,
  42. as they would be trapped
    between these two 4 block stacks.
  43. We get 3 units by taking the height
    where the energy would level off— 4,
  44. and subtracting the height of the stack—
    so that’s 4 minus 1.
  45. The 3rd stack is similar— 4 to the left,
    4 to the right, and it’s 3 high,
  46. so it’ll hold 4 minus 3 equals 1 unit.
  47. The 4th stack and 5th stacks have
    nothing higher than them to the right,
  48. so they can’t hold any energy.
  49. We can adapt this idea into an algorithm.
  50. Considering one column at a time
    as the point of reference,
  51. Hedge can look to the left stack by stack
    to find the height of the tallest one,
  52. look to the right to find the height
    of the tallest one,
  53. and take the smaller of the two
    as the height the energy can fill up to.
  54. If the result is higher than the column
    in question,
  55. subtract the height
    of the original column,
  56. and the result will be the number of units
    that column can hold.
  57. If it's equal to or below the level
    of the column in question,
  58. the energy would spill off.
  59. Hedge can apply that
    to an entire basin with a loop
  60. that starts on the left-most column
    and moves right, one column at a time.
  61. For each column, he’ll run the same steps—
    look all the way left for the tallest,
  62. do the same to the right,
    take the lower height of the two,
  63. subtract the original column height,
  64. and increase the grand total
    if that number is positive.
  65. His loop will repeat
    as many times as there are columns.
  66. That will work, but it’ll take a long time
    for a large basin.
  67. At every step Hedge repeats the action
    of looking left and looking right.
  68. If there are N stacks,
    he’ll look at all N stacks N times.
  69. Is there a faster way?
  70. Here’s one time saver:
    before doing anything else,
  71. Hedge can start on the left,
  72. and keep a running tally
    of what the highest stack is.
  73. Here that would be 2, 2 again,
    since the first was higher,
  74. then 4, 4, 4.
  75. He can then find
    the highest right-most stacks
  76. by doing the same going right-to-left:
    1, 3, 4, 4, 4.
  77. In the end he’ll have a table
    like this in his memory.
  78. Now, Hedge can take one more pass
    to calculate how much energy there will be
  79. above every stack
    with the same equation from before:
  80. take the smaller of the stored left
    and right values,
  81. and subtract the height
    of the current tower.
  82. Instead of looking at N stacks N times,
    he’ll look at N stacks just 3 times—
  83. which is what’s called linear time.
  84. There are ways to optimize
    the solution even further,
  85. but this is good enough for our heroes.
  86. Ethic and Hedge work as one.
  87. The first cascade is a breeze,
    and they rise up the tower.
  88. The second is a little tougher.
  89. The third is huge,
    with dozens of stacks of blocks.
  90. The timer ticks down towards zero,
    but Ethic’s program is fast.
  91. She gets the wheel in position
    just in time,
  92. and the energy lifts them
    to the Node of Creation.
  93. Like the first, it reveals a vision:
    memories of years gone by.
  94. The world machine changed everything,
  95. and Ethic, in her position
    as chief robotics engineer,
  96. grew troubled by what she saw.
  97. When the Bradbarrier went up
    to keep the people in,
  98. she knew something was seriously wrong.
  99. So she created three artifacts
  100. with the ability to restore people’s
    power, creativity, and memory,
  101. and smuggled them to three communities.
  102. Before she could tell people
    how to use them,
  103. the government discovered her efforts
    and sent bots to arrest her
  104. and the other programmers.
  105. The last thing Ethic
    used the world machine to create
  106. was a robot that would protect
    the ancient device
  107. from the forces of ignorance
    by enclosing it in a giant maze.
  108. She named her creation Hedge.
  109. Without warning, the energy lift flickers,
    then fizzles out.