The Chasm | Think Like A Coder, Ep 6

翻訳: Moe Shoji 校正: Yasushi Aoki

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

エシック、ヘッジ、オクタヴィアは 底なしの谷の縁に立っています

It’s the only thing between them and the tower

塔と彼らを隔てる この谷さえ渡れば

that houses the second of three powerful artifacts.

３つの強力なアイテムの ２つめが手に入るのです

They’ve got a brief window of time to get across before the guards return.

警備ロボットが戻ってくるまでの 短い時間に渡らなければなりません

With Hedge’s fuel gauge on empty he won’t be able to fly Ethic across,

ヘッジが燃料切れで エシックを連れて飛べないので

so the only option is to make a bridge.

橋を作るしかありません

Fortunately, the floating stacks of stones nearby are bridge components—

幸い 橋の部品となるブロックの山が 近くに浮かんでいます

invented by Octavia herself— called hover-blocks.

オクタヴィアが発明した 浮遊ブロックです

Activate a pile with a burst of energy,

エネルギーをかけて ブロックの山を起動させれば

and they’ll self-assemble to span the ravine as Ethic walks across.

エシックが歩いて渡れる橋が 自動的に組み上がります

But there is, of course, a catch.

もちろん 問題もあります

The hover-blocks are only stable when they’re perfectly palindromic.

浮遊ブロックが安定するのは 完全な回文構造の時だけなのです

Meaning they have to form a sequence

つまり 前から見ても 後ろから見ても

that’s the same when viewed forwards and backwards.

並び順が同じでなければなりません

The stacks start in random orders,

ブロックは最初ランダムに 積み重なっていても

but will always put themselves into a palindromic configuration

可能な限り 回文構造を作ろうとします

if they can.

If they get to a point where a palindrome isn’t possible,

回文構造が作れないときには

the bridge will collapse,

橋は崩れてしまい

and whoever’s on it will fall into the ravine.

上にいる人は 谷底に落ちることになります

Let’s look at an example.

例を見てみましょう

This stack would make itself stable.

このブロックの山は 安定した構造を作れます

First the A blocks hold themselves in place.

まずＡが両端につきます

Then the B’s.

それからＢがきて

And finally the C would nestle right between the B’s.

最後にＣが Ｂの間に入ります

However, suppose there was one more A.

でもＡが もう１つあったとしたら？

First two A blocks form up, then two B’s,

まずはＡが２個 次にＢが２個 入りますが

but now the remaining C and A have nowhere to go,

残ったＣとＡには 行き場がないので

so the whole thing falls apart.

全体が崩れてしまいます

The Node of Power enables Hedge to energize a single stack of blocks.

力の石を使ってヘッジは ブロックの山を１つだけ起動できます

What instructions can Ethic give Hedge to allow him to efficiently find

エシックがどんな指示を ヘッジに与えれば

回文構造を作れる山を効率的に見つけ 起動させられるでしょうか？

and power a stable palindromic stack?

Pause now to figure it out for yourself.

［ビデオをいったん止めて 自分で考えてみましょう］

Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.

回文の例としては ANNAや RACECARや MADAM IM ADAMなどがあります

Counting the number of times a given letter appears in a palindrome

回文の中に各文字が 何度現れるかを数えると

役に立つ規則性が 見えてくるでしょう

will reveal a helpful pattern.

Pause now to figure it out for yourself.

［ビデオをいったん止めて 自分で考えてみましょう］

Let’s first look at a naïve solution to this problem.

まずは 素朴な解決法を 考えてみましょう

A naïve solution is a simple, brute-force approach that isn’t optimized—

素朴な方法とは 最適化されていない 単純なしらみつぶしのやり方ですが

but will get the job done.

目的は果たせるような もののことです

Naïve solutions are helpful ways to analyze problems,

素朴な方法は 問題を分析する役に立ち

and work as stepping stones to better solutions.

よりよい解決法を見つける 糸口になります

In this case, a naïve solution is to approach a pile of blocks,

この場合 素朴な方法は ブロックの山ごとに

try all the arrangements,

すべての並び順を試し

and see if one is a palindrome by reading it forward and then backwards.

前からも 後ろからも読んで 回文構造か確かめるというものです

The problem with this approach

この方法の問題は

is that it would take a tremendous amount of time.

とても長い時間がかかることです

If Hedge tried one combination every second,

ヘッジが１つの並びを試すのに １秒かかるとすると

a stack of just 10 different blocks would take him 42 days to exhaust.

異なる10個のブロックからなる山を １つ調べるのに42日間もかかります

That’s because the total time is a function of the factorial

なぜなら かかる時間は ブロックの個数の

of the number of blocks there are.

階乗に等しくなるからです

10 blocks have over 3 million combinations.

ブロックが10個なら ３百万以上の並び順があります

What this naïve solution shows is that we need a much faster way

この素朴な方法から分かるのは もっと速い方法で

ブロックの山が回文構造になるか 見分ける必要があるということです

to tell whether a pile of blocks can form a palindrome.

To start, it may be intuitively clear that a pile of all different blocks

まず 直観的に分かるのは

「ブロックが全部違っていたら不可」 ということです

will never form one.

Why?

なぜなら 重複しているブロックがなければ 両端のブロックが同じになり得ないからです

The first and last blocks can’t be the same if there are no repeats.

So when can a given sequence become a palindrome?

では 回文構造になり得るのは どのような場合なのでしょう？

One way to figure that out is to analyze a few existing palindromes.

いくつかの回文を分析することで 答えを見つけることができます

In ANNA, there are 2 A’s and 2 N’s.

ANNA には Ａが２個 Ｎが２個あります

RACECAR has 2 R’s, 2 A’s, 2 C’s, and 1 E.

RACECAR には Ｒが２個 Ａが２個、Ｃが２個、Ｅが１個

And MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 I.

MADAM IM ADAM には Ｍが４個 Ａが４個、Ｄが２個、Ｉが１個です

The pattern here is that most of the letters occur

ここで見られるパターンは

ほとんどの文字が偶数回 現れているということです

an even number of times,

and there’s at most 1 that occurs just once.

そして１回しか現れない文字は あっても１つだけです

Is that it?

それだけでしょうか？

What if RACECAR had 3 E’s instead of 1?

RACECAR にＥが１個でなく ３個あったとしたら？

We could tack the new E’s onto the ends and still get a palindrome,

増えたＥを両端につければ また回文構造になるので

so 3 is ok.

３回現れてもOKです

But make that 3 E’s and 3 C’s, and there’s nowhere for the last C to go.

でも Ｅが３個で Ｃも３個なら 最後のＣの行き場がなくなります

So the most generalized insight is that

ですから 一般化した考え方は

at most one letter can appear an odd number of times,

奇数回現れる文字は 多くて１個で

but the rest have to be even.

残りの文字はすべて偶数回現れる ということです

Hedge can count the letters in each stack and organize them into a dictionary,

ヘッジはブロックの山ごとに 文字の出現回数を数えて辞書の形に整理でき

which is a tidy way of storing information.

これは上手い情報格納法です

A loop could then go through and count how many times odd numbers appear.

ここでループを使って 奇数が何度現れるかを数えます

If there are less than 2 odd characters, the stack can be made into a palindrome.

奇数回現れる文字が２個未満であれば そのブロックの山は回文構造にできます

This approach is much, much faster than the naïve solution.

このやり方は 素朴な方法よりも ずっと速く実行でき

Instead of factorial time, it takes linear time.

文字数の階乗時間ではなく 線形時間しか かかりません

That’s where the time increases

つまり ブロックの数に 比例した時間しか

in proportion to the number of blocks there are.

かからないということです

Now write a loop for Hedge to approach the piles individually,

ヘッジがそれぞれの山を分析して

回文になるものを見つけ次第 やめるようなループを書いたら

and stop when he finds a good one, and you’ll be ready to go.

準備は万端です

Here’s what happens:

さて どうなるでしょう

Hedge is fast, but there are so many piles it takes a long time.

ヘッジは素早いものの 山がたくさんあって手間取り

Too long.

時間がかかりすぎました

Ethic and Hedge are safe.

エシックとヘッジは無事でしたが

But Octavia is not so lucky.

オクタヴィアは 運が悪かったようです