1
00:00:31,587 --> 00:00:37,288
Ethic and Hedge are on the ground floor 
of a massive tower.

2
00:00:37,288 --> 00:00:41,945
Barriers of energy separate them 
from their quest’s second goal:

3
00:00:41,945 --> 00:00:43,945
the Node of Creation.

4
00:00:52,667 --> 00:00:57,409
To reach it, Ethic must use 
three energy streams to climb the tower.

5
00:00:57,409 --> 00:01:03,359
As soon as she steps forward a timer 
will begin counting down from 60 seconds.

6
00:01:07,359 --> 00:01:11,659
At the back of the room 
there’s a basin made of invisible towers

7
00:01:11,659 --> 00:01:14,735
that can hold energy between them.

8
00:01:14,735 --> 00:01:18,865
After one minute, a torrent of energy 
will pour down from above,

9
00:01:18,865 --> 00:01:21,015
filling one unit at a time,

10
00:01:21,015 --> 00:01:25,495
with a force field preventing it 
from spilling out the front or back.

11
00:01:25,495 --> 00:01:27,625
During the 60 calm seconds,

12
00:01:27,625 --> 00:01:32,723
Ethic and Hedge must decide exactly 
how many units of energy will fall.

13
00:01:32,723 --> 00:01:34,423
For each of the three challenges,

14
00:01:34,423 --> 00:01:38,088
they must choose the amount 
that will fill the basin exactly.

15
00:01:38,088 --> 00:01:41,938
If they do so, the energy will propel them
further upwards.

16
00:01:41,938 --> 00:01:46,558
But if they get the amount at all wrong, 
the energy lift will fail,

17
00:01:46,558 --> 00:01:48,048
dropping them.

18
00:01:48,048 --> 00:01:51,348
Diagrams on the walls 
illustrate some examples.

19
00:01:51,348 --> 00:01:55,618
This configuration 
will capture exactly 2 units of energy.

20
00:01:55,618 --> 00:02:00,735
This configuration will capture 4—
3 here, and 1 here.

21
00:02:00,735 --> 00:02:03,275
And this one will also capture 4,

22
00:02:03,275 --> 00:02:06,688
because any energy on the right 
would spill out.

23
00:02:06,688 --> 00:02:08,908
The energy will rain down in such a way

24
00:02:08,908 --> 00:02:13,538
that it’ll only overflow 
if there’s no space that could hold it.

25
00:02:13,538 --> 00:02:18,865
Hedge can make one tower of blocks visible
at a time and count how tall it is,

26
00:02:18,865 --> 00:02:22,725
but he can’t look at 
the whole structure all at once.

27
00:02:22,725 --> 00:02:25,530
How does Ethic program Hedge 
to figure out

28
00:02:25,530 --> 00:02:29,340
exactly how much energy 
each basin can hold?

29
00:02:29,340 --> 00:02:38,805
Pause now to figure it out for yourself.

30
00:02:38,805 --> 00:02:41,635
Here’s one way of thinking about 
what’s happening:

31
00:02:41,635 --> 00:02:44,550
each unoccupied cell will hold energy

32
00:02:44,550 --> 00:02:48,790
if and only if there is a wall 
eventually to its left,

33
00:02:48,790 --> 00:02:51,517
and a wall eventually to its right.

34
00:02:51,517 --> 00:02:56,322
But it would take a long time for Hedge 
to check this for each individual cell.

35
00:02:56,322 --> 00:03:01,185
So what if he were to consider 
a whole column of blocks at a time?

36
00:03:01,185 --> 00:03:05,025
How many units of energy 
can this hold, for instance?

37
00:03:05,025 --> 00:03:10,389
Pause now to figure it out for yourself.

38
00:03:10,389 --> 00:03:13,759
Let’s analyze the problem 
by looking at our example.

39
00:03:13,759 --> 00:03:15,914
There are 5 columns of blocks here.

40
00:03:15,914 --> 00:03:20,484
The leftmost one can’t hold any energy, 
because there’s nothing higher than it.

41
00:03:20,484 --> 00:03:23,118
The 2nd stack can have 3 units above it,

42
00:03:23,118 --> 00:03:27,244
as they would be trapped 
between these two 4 block stacks.

43
00:03:27,244 --> 00:03:32,186
We get 3 units by taking the height 
where the energy would level off— 4,

44
00:03:32,186 --> 00:03:36,346
and subtracting the height of the stack— 
so that’s 4 minus 1.

45
00:03:36,346 --> 00:03:41,808
The 3rd stack is similar— 4 to the left,
4 to the right, and it’s 3 high,

46
00:03:41,808 --> 00:03:46,537
so it’ll hold 4 minus 3 equals 1 unit.

47
00:03:46,537 --> 00:03:50,957
The 4th stack and 5th stacks have 
nothing higher than them to the right,

48
00:03:50,957 --> 00:03:53,427
so they can’t hold any energy.

49
00:03:53,427 --> 00:03:57,245
We can adapt this idea into an algorithm.

50
00:03:57,245 --> 00:04:01,025
Considering one column at a time 
as the point of reference,

51
00:04:01,025 --> 00:04:05,436
Hedge can look to the left stack by stack 
to find the height of the tallest one,

52
00:04:05,436 --> 00:04:08,156
look to the right to find the height 
of the tallest one,

53
00:04:08,156 --> 00:04:12,833
and take the smaller of the two 
as the height the energy can fill up to.

54
00:04:12,833 --> 00:04:15,963
If the result is higher than the column 
in question,

55
00:04:15,963 --> 00:04:18,537
subtract the height 
of the original column,

56
00:04:18,537 --> 00:04:23,634
and the result will be the number of units
that column can hold.

57
00:04:23,634 --> 00:04:27,194
If it's equal to or below the level 
of the column in question,

58
00:04:27,194 --> 00:04:29,397
the energy would spill off.

59
00:04:29,397 --> 00:04:32,917
Hedge can apply that 
to an entire basin with a loop

60
00:04:32,917 --> 00:04:38,662
that starts on the left-most column 
and moves right, one column at a time.

61
00:04:38,662 --> 00:04:43,671
For each column, he’ll run the same steps—
look all the way left for the tallest,

62
00:04:43,671 --> 00:04:47,231
do the same to the right, 
take the lower height of the two,

63
00:04:47,231 --> 00:04:49,318
subtract the original column height,

64
00:04:49,318 --> 00:04:53,178
and increase the grand total 
if that number is positive.

65
00:04:53,178 --> 00:04:56,848
His loop will repeat 
as many times as there are columns.

66
00:04:56,848 --> 00:05:00,798
That will work, but it’ll take a long time
for a large basin.

67
00:05:00,798 --> 00:05:05,328
At every step Hedge repeats the action 
of looking left and looking right.

68
00:05:05,328 --> 00:05:10,280
If there are N stacks, 
he’ll look at all N stacks N times.

69
00:05:10,280 --> 00:05:12,260
Is there a faster way?

70
00:05:12,260 --> 00:05:15,608
Here’s one time saver: 
before doing anything else,

71
00:05:15,608 --> 00:05:17,468
Hedge can start on the left,

72
00:05:17,468 --> 00:05:21,338
and keep a running tally 
of what the highest stack is.

73
00:05:21,338 --> 00:05:25,098
Here that would be 2, 2 again,
since the first was higher,

74
00:05:25,098 --> 00:05:27,848
then 4, 4, 4.

75
00:05:27,848 --> 00:05:30,628
He can then find 
the highest right-most stacks

76
00:05:30,628 --> 00:05:36,882
by doing the same going right-to-left: 
1, 3, 4, 4, 4.

77
00:05:36,882 --> 00:05:40,722
In the end he’ll have a table 
like this in his memory.

78
00:05:40,722 --> 00:05:45,961
Now, Hedge can take one more pass 
to calculate how much energy there will be

79
00:05:45,961 --> 00:05:50,001
above every stack 
with the same equation from before:

80
00:05:50,001 --> 00:05:53,638
take the smaller of the stored left 
and right values,

81
00:05:53,638 --> 00:05:56,708
and subtract the height 
of the current tower.

82
00:05:56,708 --> 00:06:02,293
Instead of looking at N stacks N times, 
he’ll look at N stacks just 3 times—

83
00:06:02,293 --> 00:06:04,573
which is what’s called linear time.

84
00:06:04,573 --> 00:06:07,814
There are ways to optimize 
the solution even further,

85
00:06:07,814 --> 00:06:10,564
but this is good enough for our heroes.

86
00:06:10,564 --> 00:06:12,334
Ethic and Hedge work as one.

87
00:06:14,992 --> 00:06:18,836
The first cascade is a breeze, 
and they rise up the tower.

88
00:06:21,573 --> 00:06:23,583
The second is a little tougher.

89
00:06:33,051 --> 00:06:36,911
The third is huge, 
with dozens of stacks of blocks.

90
00:06:36,911 --> 00:06:41,344
The timer ticks down towards zero, 
but Ethic’s program is fast.

91
00:06:41,344 --> 00:06:44,308
She gets the wheel in position 
just in time,

92
00:06:49,015 --> 00:06:51,935
and the energy lifts them 
to the Node of Creation.

93
00:06:55,640 --> 00:07:01,067
Like the first, it reveals a vision: 
memories of years gone by.

94
00:07:01,067 --> 00:07:03,187
The world machine changed everything,

95
00:07:03,187 --> 00:07:06,856
and Ethic, in her position 
as chief robotics engineer,

96
00:07:06,856 --> 00:07:08,906
grew troubled by what she saw.

97
00:07:08,906 --> 00:07:11,946
When the Bradbarrier went up 
to keep the people in,

98
00:07:11,946 --> 00:07:14,586
she knew something was seriously wrong.

99
00:07:14,586 --> 00:07:16,676
So she created three artifacts

100
00:07:16,676 --> 00:07:21,221
with the ability to restore people’s 
power, creativity, and memory,

101
00:07:21,221 --> 00:07:24,131
and smuggled them to three communities.

102
00:07:24,131 --> 00:07:26,449
Before she could tell people 
how to use them,

103
00:07:26,449 --> 00:07:29,959
the government discovered her efforts 
and sent bots to arrest her

104
00:07:29,959 --> 00:07:31,889
and the other programmers.

105
00:07:31,889 --> 00:07:35,209
The last thing Ethic 
used the world machine to create

106
00:07:35,209 --> 00:07:37,999
was a robot that would protect 
the ancient device

107
00:07:37,999 --> 00:07:42,329
from the forces of ignorance 
by enclosing it in a giant maze.

108
00:07:42,329 --> 00:07:44,743
She named her creation Hedge.

109
00:07:51,801 --> 00:07:55,631
Without warning, the energy lift flickers,
then fizzles out.