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

翻訳: Moe Shoji 校正: Yasushi Aoki

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,

60秒が過ぎると エネルギーが勢いよく 上から降ってきて

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.

この形の場合は ４ユニット分― 左に３つ 右に１つです

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.

ブロックは５列あります

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,

エネルギーがいっぱいになる高さ４から

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

ブロックの高さ１を引いて ３という答えになります

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

３列目も同様で 左に４段 右に４段あり 高さが３なので

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

４引く３で１ユニット保持できます

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列すべてを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,

この場合は まず２ 最初の列のほうが高いので 再び２

then 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.

今度は右から左へ １、３、４、４、４となります

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回参照する代わりに 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.

エシックとヘッジは 力を合わせます

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.

警告もなしに エネルギーの昇降機は 突然消えてしまいました