峡谷 | 像程序员一样思考 第六集 Alex Rosenthal: The Chasm | Think Like A Coder, Ep 6

上映日期: 0

语言:

影片类型:

导演:

演员: Alex Rosenthal


台词
Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.
[ 像程序员一样思考 ]
It’s the only thing between them and the tower
[ 地点:198 森林 ]
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,
首先,A 型方块 能被排列在左右两侧。
so the whole thing falls apart.
接着是 B 型方块。
The Node of Power enables Hedge to energize a single stack of blocks.
最后,C 型方块正好 能被放在两块 B 之间。
What instructions can Ethic give Hedge to allow him to efficiently find
但假设多一块 A 型方块的话。
and power a stable palindromic stack?
首先两块 A 排列好, 然后两块 B 也排列好,
Pause now to figure it out for yourself.
但剩下的 A 块 和 C 块就没地方放了,
Examples of palindromes include ANNA, RACECAR, and 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—
回文排列的例子如:ANNA、RACECAR、 以及 MADAM IM ADAM。
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
那么只有 10 块的飘浮块堆, 需要 42 天才能算完。
will never form one.
这是因为总时间
Why?
是总块数的阶乘。
The first and last blocks can’t be the same if there are no repeats.
10 个飘浮块就有 超过 300 万种组合方式。
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.
首先,很明显的是, 一堆各不相同的飘浮块
RACECAR has 2 R’s, 2 A’s, 2 C’s, and 1 E.
永远不可能形成回文结构。
And MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 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?
ANNA 有两个 A 和两个 N,
We could tack the new E’s onto the ends and still get a palindrome,
RACECAR 有两个 R、 两个 A、两个 C 和一个 E,
so 3 is ok.
MADAM IM ADAM 中, 有四个 M、四个 A、两个 D 和 一个 I。
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,
如果 RACECAR 有3个 E 而不是1个呢?
which is a tidy way of storing information.
我们可以把新的两个 E 钉在两端, 仍能得到一个回文,
A loop could then go through and count how many times odd numbers appear.
所以字母出现 3 次是可以的。
If there are less than 2 odd characters, the stack can be made into a palindrome.
但如果有 3 个 E 和 3 个 C , 最后一个 C 就没有地方放了。
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.
它只需线性时间, 而不是阶乘时间。