エシックとヘッジは
巨大な塔の1階にいます
エネルギーのバリアによって
2つめのアイテム「創造の石」から
隔てられています
手に入れるには 3つのエネルギーの流れに乗って
塔を登る必要があります
一歩前に出るやいなや
60秒のカウントダウンが始まります
部屋の奥には その中に
エネルギーを保持できる―
目に見えない塔がそびえています
60秒が過ぎると エネルギーが勢いよく
上から降ってきて
1ユニットずつ満たしていきます
力場によって エネルギーが前後から
漏れないようになっているのです
始まるまでの60秒の間に
エシックとヘッジはどれくらいのエネルギーを
降らせるかを決めなければなりません
3回の挑戦のたびに
塔のくぼみをちょうど満たす
エネルギー量を求めるのです
成功すれば エネルギーに乗って
上へと進むことができます
でも量を間違えると
エネルギーの昇降機は働かず
下に落ちてしまいます
壁にある図に
例が示されています
この形の場合は 2ユニット分の
エネルギーが入ります
この形の場合は 4ユニット分―
左に3つ 右に1つです
この場合も 4ユニット分です
なぜなら 右端に入ったエネルギーは
こぼれ出てしまうからです
降り注ぐエネルギーは
周囲に支えるものがなければ
あふれてしまうのです
ヘッジはブロックの列を1列ずつ可視化して
高さを測ることができますが
全体の構造を一度に
見ることはできません
エシックがヘッジを
どのようにプログラミングすれば
それぞれの塔がくぼみに保持できる
エネルギー量を把握できるでしょう?
ビデオをいったん止めて
自分で考えてみましょう
ひとつの考え方は こうです
それぞれの空の箱が
エネルギーを保持できるのは
その左方にも 右方にも
壁がある場合です
その左方にも 右方にも
壁がある場合です
でも これを各箱について確認すると
長い時間がかかってしまいます
1列まとめて考えることは
できないでしょうか?
例えば この場合は何ユニット分
保持できるでしょう?
[ビデオをいったん止めて
自分で考えてみましょう]
先程の例で 問題を
分析してみましょう
ブロックは5列あります
左端の列は 一番高いので
エネルギーを保持できません
2列目は3ユニット分
保持できます
両側にある4段のブロックに
囲まれているからです
エネルギーがいっぱいになる高さ4から
ブロックの高さ1を引いて
3という答えになります
3列目も同様で 左に4段 右に4段あり
高さが3なので
4引く3で1ユニット保持できます
4列目と5列目は
右手に自分より高いものがないので
エネルギーは保持できません
この考え方を
アルゴリズムにすることができます
エネルギー量を求めたい列を基準にして
ヘッジは1列ずつ見ていき
左方向で一番高い列を探し
それから右方向でも
一番高い列を探します
その2つの低い方が
エネルギーを貯められる高さです
この高さが
列自体の高さよりも高いならば
そこから列の高さを差し引きます
すると その答えが その列に
保持できるエネルギー量になります
エネルギーを貯められる高さが
列自体の高さ以下なら
エネルギーはこぼれてしまいます
ヘッジはループを使って
これをすべての列に適用できます
左端の列から右に向かって
1列ずつ調べていくのです
列ごとに同じ手順を踏みます
左方向に一番高い列を探し
右方向に一番高い列を探し
どちらか低い方から
列自体の高さを引いて
その答えが正の数なら
総和にその分を加算します
ヘッジはループを列の数だけ
繰り返します
これで上手くいくのですが
サイズが大きいと時間がかかります
ヘッジは各列について左方向と右方向に
たどる手順を繰り返すためです
列がN個あると
N列すべてをN回参照することになります
もっと速い方法はあるでしょうか?
ひとつの時間短縮法はこうです
手順を進める前に
ヘッジは左端から始めて
各列に対する「左側で一番高い列」を
前もって調べておけます
この場合は まず2
最初の列のほうが高いので 再び2
それから4、4、4、と続きます
それから「右側で一番高い列」も調べ
今度は右から左へ
1、3、4、4、4となります
結果として メモリ上に
こんな表が完成します
それから ヘッジはループをもう一回りさせ
さっきと同じ計算式を使い
各列に保持できるエネルギーを
計算できます
計算済みの左右の高さの
小さい方から
列自体の高さを引けばいいのです
N列をN回参照する代わりに
N列を3回参照するだけでよく
これは線形時間です
この解法をさらに最適化する方法も
ありますが
ここでは これで十分でしょう
エシックとヘッジは
力を合わせます
最初の問題は楽勝で
塔を上へと進みます
2つめは ちょっと手強いです
3つめは 大難問で
ブロックが何十列もあります
時間が刻々と過ぎますが
エシックのプログラムは高速で
ぎりぎりのところで
ハンドルの位置を合わせます
エネルギーに乗って 2人は
創造の石のありかへと導かれます
最初のアイテムの時と同じように映像が現れ
何年も前の記憶が蘇ります
世界を動かす機械が
すべてを変えてしまい
エシックはロボット主任技術者として
目にする現実に
不安を感じるようになりました
そしてブラッドバリアが人々を
囲い込み始めたとき
何かが決定的におかしいと
気づいたのでした
そこでエシックは
3つのアイテムを作り
「力」「創造性」「記憶」を
人々に取り戻させる力を付与しました
そしてアイテムを3つの共同体に
隠したのです
人々にその使い方を教える前に
政府はエシックのもくろみに気づき
彼女や他のプログラマーを
ロボットに逮捕させてしまいました
世界を動かす機械を使って
エシックが最後に作ったのは
無知の及ぼす力から
この古代の装置を守るため
それを巨大な迷路に
封じ込めるロボットで
そのロボットをヘッジと名付けたのです
警告もなしに エネルギーの昇降機は
突然消えてしまいました