主显节塔 | 像程序员一样思考 - 第 7 集

观看完整课程: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

本视频是《像程序员一样思考》系列动画的第 7 集。全部 10 集都跟随女孩 Ethic 和她的机器人伙伴 Hedge 的脚步，记录着他们尝试拯救世界的行为。他们需要收集三样物品，同时必须面对一系列的编程谜题。

授课：Alex Rosenthal；导演：Kozmonot Animation Studio。

Ethic 和 Hedge 站在巨大塔楼的底层。

能量屏障把他们与第二个目标隔开了：

创造之结。

为了拿到它，
Ethic 要用三束能量流爬上塔楼。

一旦她开始前进，
计时器就会启动 60 秒倒计时。

在房间后部，
有个由隐形柱子组成的容器，

可以储存能量。

一分钟后，能量会从上方倾泻而下，

一次填满一个单位，

力场确保它不会向前或向后流动。

在 60 秒的冷却时间里，

Ethic 和 Hedge 必须确定
有多少能量会流下来。

对于这三个挑战，

他们必须使能量正好填满底座。

如果他们做对了，
能量会助他们更进一步。

但如果他们弄错了，
能量就会泄漏出来，

落向他们。

墙上的图是一个例子。

这个结构能容纳 2 个单位的能量。

这个可以容纳 4 个单位——
左边 3 个，右边 1 个。

这个结构也可以容纳
4 个单位的能量，

因为如果右边有能量 ，就会泄漏。

能量落下的方法

让它只会在空间容纳量不够时泄漏。

Hedge 每次能让一个能量柱现形
并数出它的高度，

但他不能一次看全整个结构。

Ethic 要怎样让 Hedge 计算出

这个容器可以容纳多少能量呢？

现在暂停来自己试试。

有一种方法来思考这个问题：

对于一个空的单元格，
当且仅当它左边有墙，

右边也有墙时，

才可以容纳能量。

但 Hedge 一个个检查
这些单元格会耗费很多时间。

如果他一次考虑一整个纵列呢？

比如这个结构可以容纳多少能量？

暂停来自己试试。

我们可以通过这个例子
来分析一下问题。

这里有 5 纵列单元格。

最左边的不能容纳任何能量，
因为没有比它更高的了。

第二列能容纳3个单元格的能量，

这两个四格高的纵列
可以把能量夹在中间。

我们得出 3 格的结论，因为能量
最终会等于最高纵列——4，

再减去这列的高度 ——
就是 4 减 1。

第三列同理——左边 4 格，
右边 4 格，这列高 3 格，

所以 4 减 3 等于 1 个单位。

第四、第五列右边没有更高的，

所以它们无法容纳任何能量。

我们可以把这个方法
转变成一种算法。

每次选择一个纵列作为参考点，

Hedge 由此向左一点点检查，
找到最高的纵列，

再检查右边并找出最高的纵列，

两个高度中较小的
就是最终能量可以填满的高度。

如果这个结果高过某列原高度，

那么减去这列的原有高度，

就能得出这个纵列的容纳量。

如果低于某列的原有高度，

能量就会泄漏。

Hedge 可以对整个底座
依次这样操作，

从左到右，一次一列。

对于每一纵列都重复同样的操作——
向左找到最高的，

右边也是，
取两个高度中较小的一个，

减去原纵列原有的高度，

如果得到正数就算进总容量里。

这一流程的运行次数和纵列数相等。

这样的确可行，但如果底座很大，
这样做会耗费很多时间。

每一步，Hedge 都要反复地左看右看。

如果有 N 个纵列，
他就需要把每个纵列都看 N 遍。

有没有更快的方法呢？

有个节省时间的方法：

首先，Hedge 从左边开始，

并连续记录最高纵列的高度。

这样就是 2，然后还是 2，
因为第一个更高，

然后是 4，4，4。

然后他可以找到最高纵列的右端，

只要同样从右到左再做一遍：
1，3，4，4，4。

最终，他会记下这样一个表格。

现在 Hedge 可以再扫描一次，

按照之前的等式计算每个纵列
可以容纳多少能量：

在存储的左右最高值中选较小的，

再减去当前纵列的高度。

与把 N 个纵列每个看 N 遍相比，
他只需把每个纵列看三遍——

这就是我们所说的线性时间。

还有很多更优解决方法，

但这个已经够好了。

Ethic 和 Hedge 配合默契。

他们轻而易举地通过了
第一个瀑布，塔楼地板上升了。

第二个难一些。

第三个容器非常大，
每列有数十个单元格。

计时器显示出 0，
但 Ethic 的动作很快。

她在最后时刻找到了正确位置，

能量让他们上升至创造之结。

和第一次一样，它显现出了幻象：
多年前的记忆。

世界机器改变了一切，

Ethic 作为首席机器人工程师，

对她目击到的现象感到不安。

当 Brad 障碍升起并围住人群时，

她知道大事不妙了。

于是她造出了三个物品，

它们拥有修复人们的力量、
创造力以及记忆的能力，

并把它们偷运到了三个社区里。

在她告诉人们如何使用之前，

政府发现了她的成果，
并派出机器人

抓捕她以及其他程序员。

Ethic 用世界机器创造的
最后一件物品是个机器人，

它可以把古老的装置

围在大型迷宫中，
使它远离愚昧的力量。

她给这个物品起名叫 Hedge。

在没有任何警告的情况下，
能量电梯开始闪烁，然后消散了。