作业3：沙堡与流沙（Sandcastles & Sand）

本作业分为两部分：Part 1 包含三个“沙堡”练习（列表拉链、编码字符串展开、森林火灾高亮）；Part 2 编写一个沙子模拟器，使用二维列表实现沙子的“下落 + 布朗运动”。建议按小步分解、逐步验证的方式完成每个函数，并使用 doctest 进行单元测试。参考材料来源：Stanford CS106A 作业说明。

Part 1：沙堡练习（Sandcastles）

1）Zip Lists：拉链合并两个列表

在 ziplists.py 中实现函数 zip2lists(list1, list2)。传入两个长度相同的字符串列表，返回一个新的“配对列表”，每个元素是形如 [list1[i], list2[i]] 的二元列表。

注意：不要修改传入的原列表。如果传入的是两个空列表，应返回一个空列表：

可以把它理解为：这是一个“不包含任何子列表”的空列表。

2）Expand Encoded Strings：展开编码字符串

在 encoded_string.py 中实现 expand_encoded_string(encoded)。编码串采用“游程编码”格式：由若干对 字符+数字 组成，其中数字范围为 1-9（不会为 0），表示该字符应当重复的次数。例如 'B4' → 'BBBB'，'m1e2t1' → 'meet'。函数需返回展开后的明文字符串。

3）Finding Forest Fires：高亮森林火灾

在 forestfire.py 中实现 highlight_fires，将“足够红”的像素标为纯红（255,0,0），其余像素转为灰度。判断规则：若 red >= average(R,G,B) * INTENSITY_THRESHOLD（已给定 INTENSITY_THRESHOLD = 1.35），则视为“足够红”。灰度处理为将三个通道设为其平均值。

Part 2：Sand（沙子模拟器）

在本作业的最后一部分，你将编写 sand.py，使用二维列表（网格）来实现一个“沙子世界”。当程序运行起来后，交互和效果都很有趣。

使用二维列表（网格）表示沙子世界。每个格子仅包含以下三者之一：'s'（沙），'r'（石头），None（空）

• 沙子：用字符串 's' 表示
• 岩石：用字符串 'r' 表示
• 空格：用 None 表示（Python 的 None，不是字符串）

下面是一个 3×2 网格（即“列表的列表”）的示意图，包含一些岩石和一粒沙。沙子 's' 位于第 0 行、第 1 列（等价坐标为 x = 1, y = 0）。注意：y 表示行号，x 表示列号；第 0 行（y = 0）是最上方一行。

该网格可表示为如下列表：

如果把沙子（'s'）从第 0 行第 1 列（x = 1, y = 0）下移到第 1 行第 1 列（x = 1, y = 1），网格将变成如下所示：

像这样把沙子向下移动一格，是该程序的核心操作。让每一粒沙子一次只下移一格，就能产生演示中“沙子下落”的效果。 你应该按以下五个阶段编写代码，并为每个阶段实现相应的辅助函数：

阶段1：移动元素

函数：do_move(grid, x1, y1, x2, y2)。将 (x1,y1) 的元素移动到 (x2,y2)，并将原位置置空，返回更新后的网格（用于 doctest 对比）。

编程任务：请为 do_move 函数编写代码。该函数接收一个网格 grid（列表的列表，表示上文描述的沙子世界）以及两组坐标 (x1, y1) 与 (x2, y2)。函数应将网格中 (x1, y1) 位置的内容移动到 (x2, y2)，并把 (x1, y1) 位置更新为空，最后返回更新后的 grid。

可假设传入的都是“合法”移动：坐标均在网格范围内，且 (x2, y2) 初始为空。之所以需要返回更新后的 grid，是为了配合我们提供的 doctest（这些测试通过比较函数的返回值来判断结果）。

do_move 的代码很短，但非常适合用 doctest 练习测试用例。我们提供了两个 doctest；你也可以自行添加更多用例。你可以右键 doctest 选择 “Run Doctest …” 来运行测试。在调试每个函数的过程中，反复运行 doctest 是很常见的。

# 这三行 doctest 分别做了什么：

IMPORTANT NOTE：访问二维列表元素时，第一个下标是行（y），第二个下标是列（x）。这与我们平时的 (x, y) 记法相反。要访问位置 (x = 1, y = 0) 的元素，应写 grid[0][1]。实现本作业时请务必牢记这一点。

阶段2：检查合法移动

函数：check_move(grid, x1, y1, x2, y2)。

请为 check_move 编写代码。该函数接受一次潜在移动的起点 (x1, y1) 与终点 (x2, y2)，若该移动合法则返回 True，否则返回 False。此操作不应修改 grid。

约定：把 (x1, y1) 视为“起点”，(x2, y2) 视为“目的地”。在沙子世界中，相对起点允许的五种方向为：左、右、下、左下、右下。合法移动需满足以下规则：

1.目的地必须在网格范围内。

我们提供了三个与此规则相关的 doctest：构造一个 3 列 × 2 行的网格，验证越界的若干移动返回 False。

2.目的格子必须为空（也就是说其中应为 None）。

下面提供了一些 doctest，用来验证当目的格是否为空时，你的函数应分别返回 True 或 False。

3.对于对角线的左下或右下移动，“角点”必须为空（应为 None）。

考虑一个 3 列 × 2 行网格中位于 (x=1, y=0) 的一粒沙的两种对角移动：左下与右下。

“角点规则”要求：进行左下或右下对角移动时，目的地正上方的那个格子也必须为空。因此，上图中左下可行（因为 (0, 0) 为空），而右下不可行（因为 (2, 0) 有岩石 'r'）。如果 (2, 0) 是沙子 's'，同样会阻挡该移动。

请注意，这里的“角点”并不是指网格的四个角；只要是网格内的任意对角移动，都有对应的“角点”（即目的地正上方的格子），即使它不在网格的边角位置。

我们为“角点规则”提供了两个 doctest，与上面的示意图一致。

关于 check_move 的代码结构，有多种合理写法。一个常见且清晰的做法是在函数末尾仅保留一次 return True，并在前面针对各种非法情形编写多条 if ... : return False 的判断。编写过程中请配合上面的 doctest，一条条让测试通过再进入下一小节！

注意：在比较时直接使用 == 与 != 是可以的，例如：

如果你的 IDE（如 PyCharm）对上面这一行给出告警，请忽略。本作业语境下该告警并不适用。PyCharm 很强大，但并非完美。

阶段3：实现重力

函数：do_gravity(grid, x, y)。

请为 do_gravity 编写代码。该函数模拟沙子世界中单粒沙的重力效果。基本思路：考虑网格中的 (x,y) 位置（作为参数传入），若该位置有沙子则执行一次“重力移动”，具体算法按以下顺序尝试：

1. 1.若 (x,y) 位置不是沙子 's'，则不做任何操作，移动结束。
2. 2.若沙子可以下移，则执行下移，移动结束。
3. 3.否则，若沙子可以左下移，则执行左下移，移动结束。
4. 4.否则，若沙子可以右下移，则执行右下移，移动结束。

注意：这些情况是互斥的，意味着最多只发生一次移动（也可能不发生）。无论哪种情况，函数结束时都应返回网格。正如前面提到的，返回网格是为了配合 doctest 正常工作。

请充分复用前面步骤中编写的辅助函数——这是实现本函数的关键。如何判断沙子能否从一处移动到另一处？你已经有辅助函数了！我们为这个函数提供了 doctest，你也可以自行添加更多测试用例。

阶段4：整网格迭代

函数：do_whole_grid(grid, brownian)

下一步是编写 do_whole_grid 的代码。暂时忽略 brownian 参数，它将在后续步骤中处理。

为了创建沙子下落的效果，对网格中的每个 (x,y) 位置调用一次 do_gravity。函数完成时应返回网格（同样，这样做是为了让函数返回结果供 doctest 比较）。

关于遍历网格的重要说明：通常使用标准的 y/x 嵌套 for 循环从顶行向下遍历网格坐标是可以的。然而，在这种情况下，重要的是要反转 y 方向，让循环自底向上进行。也就是说，你应该先访问底行（y = height - 1），最后访问顶行（y = 0）。在这种情况下，使用 reversed 函数会很有帮助。reversed 函数可以应用于 range 来生成该范围的逆序元素。以下是在 for 循环中使用 reversed 函数的示例：

上面的代码会产生以下输出：

常规的自顶向下遍历行有什么问题？假设循环自顶向下进行，在顶行 (y=0)，一粒沙因重力从第 0 行移动到第 1 行。然后，当循环到达 y=1 时，同一粒沙又会再次移动。由于在后台，我们使用类似于之前见过的动画循环技术来为 Sand 图形制作动画，我们不希望一粒沙在单个时间步内移动超过一次！自底向上可以避免这个问题。

do_whole_grid 函数只是对沙子世界中的整个网格进行一次遍历，对每个格子调用一次 do_gravity（稍后在你实现下一步时，还会调用 do_brownian）。提供的图形代码会反复调用你的 do_whole_grid 函数来运行整个模拟。

里程碑：运行 sand.py！

在测试完你的函数后，你可以通过在终端中输入 python3 sand.py（在 Windows 计算机上用 py 或 python 替换 python3）来尝试运行整个程序。重力功能应该可以工作，但"布朗运动"还没有完成。通常程序第一次运行时会有很多问题。但在这里，我们依靠分解和逐个测试构建的组件，所以你的代码第一次运行就完美工作的可能性很大。如果你的程序第一次就工作，请记住这个时刻。更常见的情况是，新代码测试不够充分，第一次运行时会出现一些 bug。

当 Sand 窗口出现时，你可以点击（并按住鼠标）窗口中的任何位置来开始生成"沙子"。单选按钮"Sand"、"Rock"、"Erase"和"Big Erase"允许你在选择它们并点击窗口时生成不同的效果（允许你创建岩石并擦除现有的沙子/岩石）。你可以使用相应的复选框来开启/关闭重力和布朗运动。目前，布朗运动应该看起来没有任何效果。

阶段5：创建布朗运动

函数：do_brownian(grid, x, y, brownian)

你快要完成了！布朗运动是一个真实的物理过程，最早由 Robert Brown 记录，他观察到显微镜载玻片上的微小花粉颗粒在抖动。

我们说对 (x,y) 位置进行"布朗"移动意味着该位置的沙子有一定概率随机移动一点点——向左或向右移动一格。brownian 参数是一个 0 到 100（含）之间的整数：0 表示从不进行布朗移动，100 表示总是进行布朗移动。这个值是从 Sand 应用程序窗口顶部的小滑块实时获取的。此函数没有测试（随机性和测试是一个尴尬的组合）。

以下是在沙子世界中实现布朗运动的步骤：

1. 1. 检查该格子是否为沙子。只有当它是沙子时才继续下一步。如果不是沙子，该格子不能有布朗运动。
2. 2. 创建一个 0 到 99 范围内的随机数。注意 Python 函数 random.randrange(n)（来自 random 库）返回一个在 0 到 n-1（含）范围内均匀分布的随机数。因此，你可以使用以下调用：

只有当 num < brownian 时才继续下面的步骤 3（记住 brownian 是此函数的参数）。这样，例如如果 brownian 是 50，我们将在大约 50% 的时间进行布朗运动。

3. 要决定向左还是向右移动，通过随机生成 0 或 1 来"抛硬币"，如下所示：

4. 如果 coin 是 0，尝试将当前 (x,y) 位置的沙子向左移动一格。如果 coin 是 1，尝试将当前 (x,y) 位置的沙子向右移动一格。使用你的辅助函数检查移动是否可能，如果可能则移动沙子。不要尝试两个方向；如果你抛到 0 但发现无法向左移动，不要尝试向右移动。

在实现 do_brownian 函数后，你应该编辑 do_whole_grid 中的循环体，使其在调用 (x,y) 位置的 do_gravity 后，也调用该位置的 do_brownian。

现在，尝试像之前一样从终端运行 Sand 程序，并确保应用程序中的布朗复选框已开启。希望你会看到一个生动、不那么人工的外观。摆弄滑块（布朗复选框旁边）来创建不同级别的布朗运动。

总结

给自己一个鼓励 - 在这个作业中你学到了很多！查看以下部分来了解更多关于你精彩的新 Sand 程序的信息。

使用不同尺寸运行

你可以提供两个命令行参数（数字）来指定 Sand 模拟中网格的宽度和高度的方格数。以下行将使用 100 x 50 方格的网格运行 Sand 模拟：

可选的第三个命令行参数指定每个方格应该有多少像素宽。例如，以下行将运行 Sand 模拟，使用 100 x 50 方格网格，其中每个方格只有 4 像素：

大量计算！

Sand 程序可能对你的计算机要求很高 - 它需要持续进行大量计算。你可能会注意到笔记本电脑的风扇开始转动。在窗口的右上角有一个小灰色数字，这是程序在沙子动画中当前达到的每秒帧数（fps）。当 fps 更高时，动画具有流畅、美观的外观。

网格方格越多，沙子颗粒越多，程序运行得越慢。对于每个重力回合，你的代码需要至少查看每个方格和每粒沙子，我们希望每秒执行 40 次。尝试不同的网格和像素尺寸来体验不同的美学效果。

扩展

完成作业的所有必需部分后，你可能想要考虑添加一个可选的扩展。记住不要修改你已完成的作业文件，而是将扩展放在新文件中，比如 extension.py。

虽然我们没有为扩展提供任何指导方针，但你可以尝试的一些想法包括：

• 编写一个与 encoded_string.py 相反的程序 - 即将普通文本转换为其游程编码。
• 创建一个不同的图像处理程序。
• 创建一个具有不同物理特性的 Sand 版本。