WEBVTT

00:00:31.587 --> 00:00:37.288
Ethic and Hedge are on the ground floor 
of a massive tower.

00:00:37.288 --> 00:00:41.945
Barriers of energy separate them 
from their quest’s second goal:

00:00:41.945 --> 00:00:43.945
the Node of Creation.

00:00:52.667 --> 00:00:57.409
To reach it, Ethic must use 
three energy streams to climb the tower.

00:00:57.409 --> 00:01:03.359
As soon as she steps forward a timer 
will begin counting down from 60 seconds.

00:01:07.359 --> 00:01:11.659
At the back of the room 
there’s a basin made of invisible towers

00:01:11.659 --> 00:01:14.735
that can hold energy between them.

00:01:14.735 --> 00:01:18.865
After one minute, a torrent of energy 
will pour down from above,

00:01:18.865 --> 00:01:21.015
filling one unit at a time,

00:01:21.015 --> 00:01:25.495
with a force field preventing it 
from spilling out the front or back.

00:01:25.495 --> 00:01:27.625
During the 60 calm seconds,

00:01:27.625 --> 00:01:32.723
Ethic and Hedge must decide exactly 
how many units of energy will fall.

00:01:32.723 --> 00:01:34.423
For each of the three challenges,

00:01:34.423 --> 00:01:38.088
they must choose the amount 
that will fill the basin exactly.

00:01:38.088 --> 00:01:41.938
If they do so, the energy will propel them
further upwards.

00:01:41.938 --> 00:01:46.558
But if they get the amount at all wrong, 
the energy lift will fail,

00:01:46.558 --> 00:01:48.048
dropping them.

00:01:48.048 --> 00:01:51.348
Diagrams on the walls 
illustrate some examples.

00:01:51.348 --> 00:01:55.618
This configuration 
will capture exactly 2 units of energy.

00:01:55.618 --> 00:02:00.735
This configuration will capture 4—
3 here, and 1 here.

00:02:00.735 --> 00:02:03.275
And this one will also capture 4,

00:02:03.275 --> 00:02:06.688
because any energy on the right 
would spill out.

00:02:06.688 --> 00:02:08.908
The energy will rain down in such a way

00:02:08.908 --> 00:02:13.538
that it’ll only overflow 
if there’s no space that could hold it.

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,

00:02:18.865 --> 00:02:22.725
but he can’t look at 
the whole structure all at once.

00:02:22.725 --> 00:02:25.530
How does Ethic program Hedge 
to figure out

00:02:25.530 --> 00:02:29.340
exactly how much energy 
each basin can hold?

00:02:29.340 --> 00:02:38.805
Pause now to figure it out for yourself.

00:02:38.805 --> 00:02:41.635
Here’s one way of thinking about 
what’s happening:

00:02:41.635 --> 00:02:44.550
each unoccupied cell will hold energy

00:02:44.550 --> 00:02:48.790
if and only if there is a wall 
eventually to its left,

00:02:48.790 --> 00:02:51.517
and a wall eventually to its right.

00:02:51.517 --> 00:02:56.322
But it would take a long time for Hedge 
to check this for each individual cell.

00:02:56.322 --> 00:03:01.185
So what if he were to consider 
a whole column of blocks at a time?

00:03:01.185 --> 00:03:05.025
How many units of energy 
can this hold, for instance?

00:03:05.025 --> 00:03:10.389
Pause now to figure it out for yourself.

00:03:10.389 --> 00:03:13.759
Let’s analyze the problem 
by looking at our example.

00:03:13.759 --> 00:03:15.914
There are 5 columns of blocks here.

00:03:15.914 --> 00:03:20.484
The leftmost one can’t hold any energy, 
because there’s nothing higher than it.

00:03:20.484 --> 00:03:23.118
The 2nd stack can have 3 units above it,

00:03:23.118 --> 00:03:27.244
as they would be trapped 
between these two 4 block stacks.

00:03:27.244 --> 00:03:32.186
We get 3 units by taking the height 
where the energy would level off— 4,

00:03:32.186 --> 00:03:36.346
and subtracting the height of the stack— 
so that’s 4 minus 1.

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,

00:03:41.808 --> 00:03:46.537
so it’ll hold 4 minus 3 equals 1 unit.

00:03:46.537 --> 00:03:50.957
The 4th stack and 5th stacks have 
nothing higher than them to the right,

00:03:50.957 --> 00:03:53.427
so they can’t hold any energy.

00:03:53.427 --> 00:03:57.245
We can adapt this idea into an algorithm.

00:03:57.245 --> 00:04:01.025
Considering one column at a time 
as the point of reference,

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,

00:04:05.436 --> 00:04:08.156
look to the right to find the height 
of the tallest one,

00:04:08.156 --> 00:04:12.833
and take the smaller of the two 
as the height the energy can fill up to.

00:04:12.833 --> 00:04:15.963
If the result is higher than the column 
in question,

00:04:15.963 --> 00:04:18.537
subtract the height 
of the original column,

00:04:18.537 --> 00:04:23.634
and the result will be the number of units
that column can hold.

00:04:23.634 --> 00:04:27.194
If it's equal to or below the level 
of the column in question,

00:04:27.194 --> 00:04:29.397
the energy would spill off.

00:04:29.397 --> 00:04:32.917
Hedge can apply that 
to an entire basin with a loop

00:04:32.917 --> 00:04:38.662
that starts on the left-most column 
and moves right, one column at a time.

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,

00:04:43.671 --> 00:04:47.231
do the same to the right, 
take the lower height of the two,

00:04:47.231 --> 00:04:49.318
subtract the original column height,

00:04:49.318 --> 00:04:53.178
and increase the grand total 
if that number is positive.

00:04:53.178 --> 00:04:56.848
His loop will repeat 
as many times as there are columns.

00:04:56.848 --> 00:05:00.798
That will work, but it’ll take a long time
for a large basin.

00:05:00.798 --> 00:05:05.328
At every step Hedge repeats the action 
of looking left and looking right.

00:05:05.328 --> 00:05:10.280
If there are N stacks, 
he’ll look at all N stacks N times.

00:05:10.280 --> 00:05:12.260
Is there a faster way?

00:05:12.260 --> 00:05:15.608
Here’s one time saver: 
before doing anything else,

00:05:15.608 --> 00:05:17.468
Hedge can start on the left,

00:05:17.468 --> 00:05:21.338
and keep a running tally 
of what the highest stack is.

00:05:21.338 --> 00:05:25.098
Here that would be 2, 2 again,
since the first was higher,

00:05:25.098 --> 00:05:27.848
then 4, 4, 4.

00:05:27.848 --> 00:05:30.628
He can then find 
the highest right-most stacks

00:05:30.628 --> 00:05:36.882
by doing the same going right-to-left: 
1, 3, 4, 4, 4.

00:05:36.882 --> 00:05:40.722
In the end he’ll have a table 
like this in his memory.

00:05:40.722 --> 00:05:45.961
Now, Hedge can take one more pass 
to calculate how much energy there will be

00:05:45.961 --> 00:05:50.001
above every stack 
with the same equation from before:

00:05:50.001 --> 00:05:53.638
take the smaller of the stored left 
and right values,

00:05:53.638 --> 00:05:56.708
and subtract the height 
of the current tower.

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—

00:06:02.293 --> 00:06:04.573
which is what’s called linear time.

00:06:04.573 --> 00:06:07.814
There are ways to optimize 
the solution even further,

00:06:07.814 --> 00:06:10.564
but this is good enough for our heroes.

00:06:10.564 --> 00:06:12.334
Ethic and Hedge work as one.

00:06:14.992 --> 00:06:18.836
The first cascade is a breeze, 
and they rise up the tower.

00:06:21.573 --> 00:06:23.583
The second is a little tougher.

00:06:33.051 --> 00:06:36.911
The third is huge, 
with dozens of stacks of blocks.

00:06:36.911 --> 00:06:41.344
The timer ticks down towards zero, 
but Ethic’s program is fast.

00:06:41.344 --> 00:06:44.308
She gets the wheel in position 
just in time,

00:06:49.015 --> 00:06:51.935
and the energy lifts them 
to the Node of Creation.

00:06:55.640 --> 00:07:01.067
Like the first, it reveals a vision: 
memories of years gone by.

00:07:01.067 --> 00:07:03.187
The world machine changed everything,

00:07:03.187 --> 00:07:06.856
and Ethic, in her position 
as chief robotics engineer,

00:07:06.856 --> 00:07:08.906
grew troubled by what she saw.

00:07:08.906 --> 00:07:11.946
When the Bradbarrier went up 
to keep the people in,

00:07:11.946 --> 00:07:14.586
she knew something was seriously wrong.

00:07:14.586 --> 00:07:16.676
So she created three artifacts

00:07:16.676 --> 00:07:21.221
with the ability to restore people’s 
power, creativity, and memory,

00:07:21.221 --> 00:07:24.131
and smuggled them to three communities.

00:07:24.131 --> 00:07:26.449
Before she could tell people 
how to use them,

00:07:26.449 --> 00:07:29.959
the government discovered her efforts 
and sent bots to arrest her

00:07:29.959 --> 00:07:31.889
and the other programmers.

00:07:31.889 --> 00:07:35.209
The last thing Ethic 
used the world machine to create

00:07:35.209 --> 00:07:37.999
was a robot that would protect 
the ancient device

00:07:37.999 --> 00:07:42.329
from the forces of ignorance 
by enclosing it in a giant maze.

00:07:42.329 --> 00:07:44.743
She named her creation Hedge.

00:07:51.801 --> 00:07:55.631
Without warning, the energy lift flickers,
then fizzles out.