The Chasm | Think Like A Coder, Ep 6

翻译人员: Yizhuo He 校对人员: Yanyan Hong

[ 像程序员一样思考 ]

[ 地点：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 型方块 能被排列在左右两侧。

Then the B’s.

接着是 B 型方块。

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,

但剩下的 A 块 和 C 块就没地方放了，

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 个飘浮块就有 超过 300 万种组合方式。

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 有3个 E 而不是1个呢?

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

我们可以把新的两个 E 钉在两端， 仍能得到一个回文，

so 3 is ok.

所以字母出现 3 次是可以的。

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

但如果有 3 个 E 和 3 个 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.

但奥克塔维亚就没那么幸运了。