0:00:31.587,0:00:37.288
Ethic and Hedge are on the ground floor [br]of a massive tower.

0:00:37.288,0:00:41.945
Barriers of energy separate them [br]from their quest’s second goal:

0:00:41.945,0:00:43.945
the Node of Creation.

0:00:52.667,0:00:57.409
To reach it, Ethic must use [br]three energy streams to climb the tower.

0:00:57.409,0:01:03.359
As soon as she steps forward a timer [br]will begin counting down from 60 seconds.

0:01:07.359,0:01:11.659
At the back of the room [br]there’s a basin made of invisible towers

0:01:11.659,0:01:14.735
that can hold energy between them.

0:01:14.735,0:01:18.865
After one minute, a torrent of energy [br]will pour down from above,

0:01:18.865,0:01:21.015
filling one unit at a time,

0:01:21.015,0:01:25.495
with a force field preventing it [br]from spilling out the front or back.

0:01:25.495,0:01:27.625
During the 60 calm seconds,

0:01:27.625,0:01:32.723
Ethic and Hedge must decide exactly [br]how many units of energy will fall.

0:01:32.723,0:01:34.423
For each of the three challenges,

0:01:34.423,0:01:38.088
they must choose the amount [br]that will fill the basin exactly.

0:01:38.088,0:01:41.938
If they do so, the energy will propel them[br]further upwards.

0:01:41.938,0:01:46.558
But if they get the amount at all wrong, [br]the energy lift will fail,

0:01:46.558,0:01:48.048
dropping them.

0:01:48.048,0:01:51.348
Diagrams on the walls [br]illustrate some examples.

0:01:51.348,0:01:55.618
This configuration [br]will capture exactly 2 units of energy.

0:01:55.618,0:02:00.735
This configuration will capture 4—[br]3 here, and 1 here.

0:02:00.735,0:02:03.275
And this one will also capture 4,

0:02:03.275,0:02:06.688
because any energy on the right [br]would spill out.

0:02:06.688,0:02:08.908
The energy will rain down in such a way

0:02:08.908,0:02:13.538
that it’ll only overflow [br]if there’s no space that could hold it.

0:02:13.538,0:02:18.865
Hedge can make one tower of blocks visible[br]at a time and count how tall it is,

0:02:18.865,0:02:22.725
but he can’t look at [br]the whole structure all at once.

0:02:22.725,0:02:25.530
How does Ethic program Hedge [br]to figure out

0:02:25.530,0:02:29.340
exactly how much energy [br]each basin can hold?

0:02:29.340,0:02:38.805
Pause now to figure it out for yourself.

0:02:38.805,0:02:41.635
Here’s one way of thinking about [br]what’s happening:

0:02:41.635,0:02:44.550
each unoccupied cell will hold energy

0:02:44.550,0:02:48.790
if and only if there is a wall [br]eventually to its left,

0:02:48.790,0:02:51.517
and a wall eventually to its right.

0:02:51.517,0:02:56.322
But it would take a long time for Hedge [br]to check this for each individual cell.

0:02:56.322,0:03:01.185
So what if he were to consider [br]a whole column of blocks at a time?

0:03:01.185,0:03:05.025
How many units of energy [br]can this hold, for instance?

0:03:05.025,0:03:10.389
Pause now to figure it out for yourself.

0:03:10.389,0:03:13.759
Let’s analyze the problem [br]by looking at our example.

0:03:13.759,0:03:15.914
There are 5 columns of blocks here.

0:03:15.914,0:03:20.484
The leftmost one can’t hold any energy, [br]because there’s nothing higher than it.

0:03:20.484,0:03:23.118
The 2nd stack can have 3 units above it,

0:03:23.118,0:03:27.244
as they would be trapped [br]between these two 4 block stacks.

0:03:27.244,0:03:32.186
We get 3 units by taking the height [br]where the energy would level off— 4,

0:03:32.186,0:03:36.346
and subtracting the height of the stack— [br]so that’s 4 minus 1.

0:03:36.346,0:03:41.808
The 3rd stack is similar— 4 to the left,[br]4 to the right, and it’s 3 high,

0:03:41.808,0:03:46.537
so it’ll hold 4 minus 3 equals 1 unit.

0:03:46.537,0:03:50.957
The 4th stack and 5th stacks have [br]nothing higher than them to the right,

0:03:50.957,0:03:53.427
so they can’t hold any energy.

0:03:53.427,0:03:57.245
We can adapt this idea into an algorithm.

0:03:57.245,0:04:01.025
Considering one column at a time [br]as the point of reference,

0:04:01.025,0:04:05.436
Hedge can look to the left stack by stack [br]to find the height of the tallest one,

0:04:05.436,0:04:08.156
look to the right to find the height [br]of the tallest one,

0:04:08.156,0:04:12.833
and take the smaller of the two [br]as the height the energy can fill up to.

0:04:12.833,0:04:15.963
If the result is higher than the column [br]in question,

0:04:15.963,0:04:18.537
subtract the height [br]of the original column,

0:04:18.537,0:04:23.634
and the result will be the number of units[br]that column can hold.

0:04:23.634,0:04:27.194
If it's equal to or below the level [br]of the column in question,

0:04:27.194,0:04:29.397
the energy would spill off.

0:04:29.397,0:04:32.917
Hedge can apply that [br]to an entire basin with a loop

0:04:32.917,0:04:38.662
that starts on the left-most column [br]and moves right, one column at a time.

0:04:38.662,0:04:43.671
For each column, he’ll run the same steps—[br]look all the way left for the tallest,

0:04:43.671,0:04:47.231
do the same to the right, [br]take the lower height of the two,

0:04:47.231,0:04:49.318
subtract the original column height,

0:04:49.318,0:04:53.178
and increase the grand total [br]if that number is positive.

0:04:53.178,0:04:56.848
His loop will repeat [br]as many times as there are columns.

0:04:56.848,0:05:00.798
That will work, but it’ll take a long time[br]for a large basin.

0:05:00.798,0:05:05.328
At every step Hedge repeats the action [br]of looking left and looking right.

0:05:05.328,0:05:10.280
If there are N stacks, [br]he’ll look at all N stacks N times.

0:05:10.280,0:05:12.260
Is there a faster way?

0:05:12.260,0:05:15.608
Here’s one time saver: [br]before doing anything else,

0:05:15.608,0:05:17.468
Hedge can start on the left,

0:05:17.468,0:05:21.338
and keep a running tally [br]of what the highest stack is.

0:05:21.338,0:05:25.098
Here that would be 2, 2 again,[br]since the first was higher,

0:05:25.098,0:05:27.848
then 4, 4, 4.

0:05:27.848,0:05:30.628
He can then find [br]the highest right-most stacks

0:05:30.628,0:05:36.882
by doing the same going right-to-left: [br]1, 3, 4, 4, 4.

0:05:36.882,0:05:40.722
In the end he’ll have a table [br]like this in his memory.

0:05:40.722,0:05:45.961
Now, Hedge can take one more pass [br]to calculate how much energy there will be

0:05:45.961,0:05:50.001
above every stack [br]with the same equation from before:

0:05:50.001,0:05:53.638
take the smaller of the stored left [br]and right values,

0:05:53.638,0:05:56.708
and subtract the height [br]of the current tower.

0:05:56.708,0:06:02.293
Instead of looking at N stacks N times, [br]he’ll look at N stacks just 3 times—

0:06:02.293,0:06:04.573
which is what’s called linear time.

0:06:04.573,0:06:07.814
There are ways to optimize [br]the solution even further,

0:06:07.814,0:06:10.564
but this is good enough for our heroes.

0:06:10.564,0:06:12.334
Ethic and Hedge work as one.

0:06:14.992,0:06:18.836
The first cascade is a breeze, [br]and they rise up the tower.

0:06:21.573,0:06:23.583
The second is a little tougher.

0:06:33.051,0:06:36.911
The third is huge, [br]with dozens of stacks of blocks.

0:06:36.911,0:06:41.344
The timer ticks down towards zero, [br]but Ethic’s program is fast.

0:06:41.344,0:06:44.308
She gets the wheel in position [br]just in time,

0:06:49.015,0:06:51.935
and the energy lifts them [br]to the Node of Creation.

0:06:55.640,0:07:01.067
Like the first, it reveals a vision: [br]memories of years gone by.

0:07:01.067,0:07:03.187
The world machine changed everything,

0:07:03.187,0:07:06.856
and Ethic, in her position [br]as chief robotics engineer,

0:07:06.856,0:07:08.906
grew troubled by what she saw.

0:07:08.906,0:07:11.946
When the Bradbarrier went up [br]to keep the people in,

0:07:11.946,0:07:14.586
she knew something was seriously wrong.

0:07:14.586,0:07:16.676
So she created three artifacts

0:07:16.676,0:07:21.221
with the ability to restore people’s [br]power, creativity, and memory,

0:07:21.221,0:07:24.131
and smuggled them to three communities.

0:07:24.131,0:07:26.449
Before she could tell people [br]how to use them,

0:07:26.449,0:07:29.959
the government discovered her efforts [br]and sent bots to arrest her

0:07:29.959,0:07:31.889
and the other programmers.

0:07:31.889,0:07:35.209
The last thing Ethic [br]used the world machine to create

0:07:35.209,0:07:37.999
was a robot that would protect [br]the ancient device

0:07:37.999,0:07:42.329
from the forces of ignorance [br]by enclosing it in a giant maze.

0:07:42.329,0:07:44.743
She named her creation Hedge.

0:07:51.801,0:07:55.631
Without warning, the energy lift flickers,[br]then fizzles out.