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

翻译人员: Sylvie Han 校对人员: Yolanda Zhang

Ethic and Hedge are on the ground floor of a massive tower.

Ethic 和 Hedge 站在巨大塔楼的底层。

Barriers of energy separate them from their quest’s second goal:

能量屏障把他们与第二个目标隔开了：

the Node of Creation.

创造之结。

To reach it, Ethic must use three energy streams to climb the tower.

为了拿到它， Ethic 要用三束能量流爬上塔楼。

As soon as she steps forward a timer will begin counting down from 60 seconds.

一旦她开始前进， 计时器就会启动 60 秒倒计时。

At the back of the room there’s a basin made of invisible towers

在房间后部， 有个由隐形柱子组成的容器，

that can hold energy between them.

可以储存能量。

After one minute, a torrent of energy will pour down from above,

一分钟后，能量会从上方倾泻而下，

filling one unit at a time,

一次填满一个单位，

with a force field preventing it from spilling out the front or back.

力场确保它不会向前或向后流动。

During the 60 calm seconds,

在 60 秒的冷却时间里，

Ethic and Hedge must decide exactly how many units of energy will fall.

Ethic 和 Hedge 必须确定 有多少能量会流下来。

For each of the three challenges,

对于这三个挑战，

they must choose the amount that will fill the basin exactly.

他们必须使能量正好填满底座。

If they do so, the energy will propel them further upwards.

如果他们做对了， 能量会助他们更进一步。

But if they get the amount at all wrong, the energy lift will fail,

但如果他们弄错了， 能量就会泄漏出来，

dropping them.

落向他们。

Diagrams on the walls illustrate some examples.

墙上的图是一个例子。

This configuration will capture exactly 2 units of energy.

这个结构能容纳 2 个单位的能量。

This configuration will capture 4— 3 here, and 1 here.

这个可以容纳 4 个单位—— 左边 3 个，右边 1 个。

And this one will also capture 4,

这个结构也可以容纳 4 个单位的能量，

because any energy on the right would spill out.

因为如果右边有能量 ，就会泄漏。

The energy will rain down in such a way

能量落下的方法

that it’ll only overflow if there’s no space that could hold it.

让它只会在空间容纳量不够时泄漏。

Hedge can make one tower of blocks visible at a time and count how tall it is,

Hedge 每次能让一个能量柱现形 并数出它的高度，

but he can’t look at the whole structure all at once.

但他不能一次看全整个结构。

How does Ethic program Hedge to figure out

Ethic 要怎样让 Hedge 计算出

exactly how much energy each basin can hold?

这个容器可以容纳多少能量呢？

Pause now to figure it out for yourself.

现在暂停来自己试试。

Here’s one way of thinking about what’s happening:

有一种方法来思考这个问题：

each unoccupied cell will hold energy

对于一个空的单元格， 当且仅当它左边有墙，

if and only if there is a wall eventually to its left,

右边也有墙时，

and a wall eventually to its right.

才可以容纳能量。

But it would take a long time for Hedge to check this for each individual cell.

但 Hedge 一个个检查 这些单元格会耗费很多时间。

So what if he were to consider a whole column of blocks at a time?

如果他一次考虑一整个纵列呢？

How many units of energy can this hold, for instance?

比如这个结构可以容纳多少能量？

Pause now to figure it out for yourself.

暂停来自己试试。

Let’s analyze the problem by looking at our example.

我们可以通过这个例子 来分析一下问题。

There are 5 columns of blocks here.

这里有 5 纵列单元格。

The leftmost one can’t hold any energy, because there’s nothing higher than it.

最左边的不能容纳任何能量， 因为没有比它更高的了。

The 2nd stack can have 3 units above it,

第二列能容纳3个单元格的能量，

as they would be trapped between these two 4 block stacks.

这两个四格高的纵列 可以把能量夹在中间。

We get 3 units by taking the height where the energy would level off— 4,

我们得出 3 格的结论，因为能量 最终会等于最高纵列——4，

and subtracting the height of the stack— so that’s 4 minus 1.

再减去这列的高度 —— 就是 4 减 1。

The 3rd stack is similar— 4 to the left, 4 to the right, and it’s 3 high,

第三列同理——左边 4 格， 右边 4 格，这列高 3 格，

so it’ll hold 4 minus 3 equals 1 unit.

所以 4 减 3 等于 1 个单位。

The 4th stack and 5th stacks have nothing higher than them to the right,

第四、第五列右边没有更高的，

so they can’t hold any energy.

所以它们无法容纳任何能量。

We can adapt this idea into an algorithm.

我们可以把这个方法 转变成一种算法。

Considering one column at a time as the point of reference,

每次选择一个纵列作为参考点，

Hedge can look to the left stack by stack to find the height of the tallest one,

Hedge 由此向左一点点检查， 找到最高的纵列，

look to the right to find the height of the tallest one,

再检查右边并找出最高的纵列，

and take the smaller of the two as the height the energy can fill up to.

两个高度中较小的 就是最终能量可以填满的高度。

If the result is higher than the column in question,

如果这个结果高过某列原高度，

subtract the height of the original column,

那么减去这列的原有高度，

and the result will be the number of units that column can hold.

就能得出这个纵列的容纳量。

If it's equal to or below the level of the column in question,

如果低于某列的原有高度，

the energy would spill off.

能量就会泄漏。

Hedge can apply that to an entire basin with a loop

Hedge 可以对整个底座 依次这样操作，

that starts on the left-most column and moves right, one column at a time.

从左到右，一次一列。

For each column, he’ll run the same steps— look all the way left for the tallest,

对于每一纵列都重复同样的操作—— 向左找到最高的，

do the same to the right, take the lower height of the two,

右边也是， 取两个高度中较小的一个，

subtract the original column height,

减去原纵列原有的高度，

and increase the grand total if that number is positive.

如果得到正数就算进总容量里。

His loop will repeat as many times as there are columns.

这一流程的运行次数和纵列数相等。

That will work, but it’ll take a long time for a large basin.

这样的确可行，但如果底座很大， 这样做会耗费很多时间。

At every step Hedge repeats the action of looking left and looking right.

每一步，Hedge 都要反复地左看右看。

If there are N stacks, he’ll look at all N stacks N times.

如果有 N 个纵列， 他就需要把每个纵列都看 N 遍。

Is there a faster way?

有没有更快的方法呢？

Here’s one time saver: before doing anything else,

有个节省时间的方法：

Hedge can start on the left,

首先，Hedge 从左边开始，

and keep a running tally of what the highest stack is.

并连续记录最高纵列的高度。

Here that would be 2, 2 again, since the first was higher,

这样就是 2，然后还是 2， 因为第一个更高，

then 4, 4, 4.

然后是 4，4，4。

He can then find the highest right-most stacks

然后他可以找到最高纵列的右端，

by doing the same going right-to-left: 1, 3, 4, 4, 4.

只要同样从右到左再做一遍： 1，3，4，4，4。

In the end he’ll have a table like this in his memory.

最终，他会记下这样一个表格。

Now, Hedge can take one more pass to calculate how much energy there will be

现在 Hedge 可以再扫描一次，

above every stack with the same equation from before:

按照之前的等式计算每个纵列 可以容纳多少能量：

take the smaller of the stored left and right values,

在存储的左右最高值中选较小的，

and subtract the height of the current tower.

再减去当前纵列的高度。

Instead of looking at N stacks N times, he’ll look at N stacks just 3 times—

与把 N 个纵列每个看 N 遍相比， 他只需把每个纵列看三遍——

which is what’s called linear time.

这就是我们所说的线性时间。

There are ways to optimize the solution even further,

还有很多更优解决方法，

but this is good enough for our heroes.

但这个已经够好了。

Ethic and Hedge work as one.

Ethic 和 Hedge 配合默契。

The first cascade is a breeze, and they rise up the tower.

他们轻而易举地通过了 第一个瀑布，塔楼地板上升了。

The second is a little tougher.

第二个难一些。

The third is huge, with dozens of stacks of blocks.

第三个容器非常大， 每列有数十个单元格。

The timer ticks down towards zero, but Ethic’s program is fast.

计时器显示出 0， 但 Ethic 的动作很快。

She gets the wheel in position just in time,

她在最后时刻找到了正确位置，

and the energy lifts them to the Node of Creation.

能量让他们上升至创造之结。

Like the first, it reveals a vision: memories of years gone by.

和第一次一样，它显现出了幻象： 多年前的记忆。

The world machine changed everything,

世界机器改变了一切，

and Ethic, in her position as chief robotics engineer,

Ethic 作为首席机器人工程师，

grew troubled by what she saw.

对她目击到的现象感到不安。

When the Bradbarrier went up to keep the people in,

当 Brad 障碍升起并围住人群时，

she knew something was seriously wrong.

她知道大事不妙了。

So she created three artifacts

于是她造出了三个物品，

with the ability to restore people’s power, creativity, and memory,

它们拥有修复人们的力量、 创造力以及记忆的能力，

and smuggled them to three communities.

并把它们偷运到了三个社区里。

Before she could tell people how to use them,

在她告诉人们如何使用之前，

the government discovered her efforts and sent bots to arrest her

政府发现了她的成果， 并派出机器人

and the other programmers.

抓捕她以及其他程序员。

The last thing Ethic used the world machine to create

Ethic 用世界机器创造的 最后一件物品是个机器人，

was a robot that would protect the ancient device

它可以把古老的装置

from the forces of ignorance by enclosing it in a giant maze.

围在大型迷宫中， 使它远离愚昧的力量。

She named her creation Hedge.

她给这个物品起名叫 Hedge。

Without warning, the energy lift flickers, then fizzles out.

在没有任何警告的情况下， 能量电梯开始闪烁，然后消散了。