The Chasm | Think Like A Coder, Ep 6

譯者: Lilian Chiu 審譯者: H_L Au

[用程式設計的方式思考]

[地點：198 森林]

[第六集　裂谷]

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.

A 懸浮塊會先就位。再到 B。

Then the B’s.

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

最後是 C，在兩個 B 之間。

However, suppose there was one more A.

然而，如果有再多一個 A，

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

兩個 A 會先排好， 接著是兩個 B，

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

但，現在就剩下一個 C 及一個 A，無處可去，

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.

若一疊中有十種不同的懸浮塊， 就要花四十二天試盡所有組合。

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.

十個懸浮塊就會有三百萬種組合。

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 中， 有兩個 A、兩個 N。

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

RACECAR 有兩個 R、 兩個 A、兩個 C、一個 E。

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

MADAM IM ADAM 有四個 M、

四個 A、兩個 D、一個 I。

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 有三個 E， 而不是一個呢？

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

我們可以把新增加的兩個 E 補在兩端，仍然會對稱，

so 3 is ok.

所以三個也可以。

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

但如果有三個 E 和三個 C，

最後一個 C 就沒地方放了。

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.

但奧特薇雅卻沒這麼幸運。