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

譯者: Clement Fu 審譯者: Thomas Tam

[TED-Ed 原創系列]

《時代女神 x 程式邏輯革命》

[地點：一九八樹林]

[第七集：覺醒]

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

踏進巨塔的底層

彥霖和凌杰要先越過能量布陣

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.

彥霖要藉三道能量流登上塔頂

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.

彥霖、凌杰要決定降下多少格能量

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.

這範例蓄積恰恰兩格能量

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

範例二則蓄積四格：

第二欄 3 格、第三欄 1 格

And this one will also capture 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,

凌杰可逐次顯現一座能量塔再數高度

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

但不能一窺整個能量池的全豹

How does Ethic program Hedge to figure out

彥霖要為凌杰設計一個怎樣的程式

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.

但凌杰每一格都左顧右盼會很費時

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,

算法是將能量塔 最高平整的高度——4

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

減去能量塔本身的高度——1

即 4 減 1 得 3

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,

靠左，逐欄找最高一座塔的高度

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

凌杰可用一個迴圈橫越整個能量池

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.

每個步驟凌杰都要向左、向右查看

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,

凌杰從最左開始一邊數一邊做小抄

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

現在凌杰只消多一重功夫

用先前同一條等式

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 次，現在只消 3 次

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.

彥霖、凌杰雙劍合璧

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.

計時器快歸零，幸好編寫程式夠快

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,

彥霖身為機器人總工程師看在眼裡

怵惕惻隱之心不禁戚戚

grew troubled by what she saw.

When the Bradbarrier went up to keep the people in,

當「八達圍」築起，把人圍堵城牆內

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

在最後關頭，彥霖再一次善用創世機

創造了一個機器人，囑託他至死守護

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.

彥霖給了守護機器人一個名字：凌杰

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

能量階梯一閃消失，送上無情的迫降