主显节塔 | 像程序员一样思考 - 第 7 集 Alex Rosenthal: The Tower of Epiphany | Think Like A Coder, Ep 7

上映日期: 0




演员: Alex Rosenthal

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,
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.
在没有任何警告的情况下, 能量电梯开始闪烁,然后消散了。