Karel the Robot

问题
过程抽象
函数调用
总结

最近整理了斯坦福 CS106A 的 Assignment 1，走进了一个叫做 Karel 的世界。

原本以为这只是一个简单的上手项目，激发学生对课程的兴趣而已，所以也没怎么重视。但是做完这几个题目之后，我的观念转变了，又回头仔细看了课程中的几个关键点。

Karel 是个经典的计算机科学教学项目，值得好好揣摩。设计这个课程的家伙，应该不仅自己掌握了计算机科学的精髓，而且还懂得怎样去做教学。所以，这真不是一个简简单单的上手项目，不然斯坦福每年也不会都用这个来教学。

在回看时，我仔细梳理了问题求解的过程，并深入思考了课程中反复提及的自顶向下分解策略（top-down decomposition）和函数调用的前置/后置条件（pre/post condition）。结合 Assignment 可以发现，作业的设计完全就是为了强化这些概念。

独立完成这些作业，一定会有一种豁然开朗的感觉。虽然说不清楚到底是啥感觉，但我知道，下次再遇到问题求解的时候，在大方向上，应该会更有把握，避免走太多弯路！

问题

下面就以画棋盘那道题为例，分析一下问题求解的过程。

NOTE

顺便提一下，这个题整整耗了我半天时间！原因嘛，就是没有应用课程中的关键点，没有按照老师教的方法来做……细品！

问题很简单，就是让 Karel 从起点，每放置完一个 Beeper 跳一个格子。问题的难点主要体现在两个方面：

只能使用 Karel 编程语言，不能使用 Java 里面的东西，特别是变量；
地图不固定，不仅要满足多行多列，甚至单行单列，都要能够应付。

INFO

Karel 编程语言

所谓 Karel 编程语言，就是 Karel 的世界了，它只包含有限的几个程序构件块。你想用高级一点的东西？对不起，没有！

Why？我觉得，只有这样的限制才会迫使你去思考：为了解决问题，编程语言的那些奇技淫巧是否真有必要？

过程抽象

这个策略，也可以称为逐步求精。但课件里，直译过来不是分而治之吗？至于为什么我不翻译为分而治之，是因为这个词，我把它给了更重要的递归策略。后续课程会专门训练递归思维。

对于棋盘这个问题，使用逐步求精的方法，很容易这么去思考：先让 Karel 从起点往上，走完所有的格子。暂且把放置 Beeper 的任务放一放，以便简化问题求解。那么首先需要解决的问题是：

Q: Karel 撞墙后如何移动到上一层？

A: 我们可以用一个 moveUp 函数来抽象这个过程。

继续细分，又有两种情况：一种是面朝东撞墙，另一种是面朝西撞墙。所以，我们可以使用一个 if ... else ... 条件分支，来区分这两种情况：

private void moveUp() {
  if (facingEast()) {
    // 向东的情况
  } else {
    // 向西的情况
  }
}

现在，我们再解决移动到上一格的问题。但在移动之前，其实还需要检测上方是否到顶。这就顺便解决了第二个问题：

Q: Karel 何时停止？

A: 如果到顶了，那么不作任何操作；如果没到顶，那么移动到上一层并改变方向（即转身向上、走一步到上层、再转身改变方向，三个步骤一气呵成）。

这一步无论向东还是向西，除了转动方向不同外，程序结构是一模一样的：

// pre-condition: 前方有障碍
// post-condition: 跳到上一格，并转身
private void moveUp() {
  if (facingEast()) {
    if (leftIsClear()) { // 对于这个条件检测
      turnLeft();
      move();
      turnLeft();
    }
  } else {
    if (rightIsClear()) { // 思考函数调用的时机问题
      turnRight();
      move();
      turnRight();
    }
  }
}

注意，每次移动到上一层会改变之前的方向，可以看作是 Karel 又到了一个新的起点。这一步很重要，因为条件没变，所以可以复用很多过程。

moveUp 函数的抽象过程是通用的，能够满足所有的情况。但要仔细思考函数调用的时机！至此，我们的程序已经能够让 Karel 从起点走到终点，并且适用于所有的地图。

函数调用

接下来，我们进一步解决 Karel 如何放置 Beeper 的问题。

有点编程经验的人，可能会想到设置一个 FLAG 标记，来记录间隔放置的状态。但这样不符合题目的要求，因为要求只能使用 Karal 编程语言，所以不存在变量的概念。

仔细看一下 Karel 提供的构件块，目前只能使用过程的方式来确定 Karel 跳过一个格子放置一个 Beeper 的事情，即

走一步
再走一步
放置一个 Beeper

把这三个动作当成一个整体来考虑，然后通过循环控制结构，直到顶部结束。大概的过程如下：

while (frontIsClear()) {
  move();
  move();
  putBeeper();
}

这个时候，我们应该思考函数调用这件事。

Q: 函数可以随便调用吗？如果不是，调用函数的条件是什么呢？

为了回答这个问题，依次来分析每个函数调用的前置后置条件。

走第一步调用 move 函数：前置条件有循环控制条件来保证，而后置条件可能出现撞墙的情况，所以我们还需要利用之前写好的 moveUp 函数重写上述过程：

while (frontIsClear()) { // pre-con
    move();
    if (frontIsClear()) {  // post-con
        move(); // 无遮挡情况
        putBeeper();
    } else {
        moveUp(); // 有遮挡情况
        putBeeper();
    }
}

无遮挡情况走第二步同样调用 move 函数：前置条件是无遮挡情况的，移动会很顺利，紧接着就应该放置一个 Beeper。但是，后置条件同样可能会出现遮挡的情况，所以要追加一个处理过程，让 Karel 恢复自由状态：

while (frontIsClear()) {
    move();
    if (frontIsClear()) {
        move();
        putBeeper();
        if (frontIsBlocked()) { // 结束后有遮挡的情况，恢复Karel自由身
        moveUp();
        move();
        putBeeper();
        }
    } else {
        moveUp();
        putBeeper();
    }
}

有遮挡情况走第二步调用的是 moveUp 函数：前置条件是有遮挡情况的，可能出现到顶的情况，也就是说 moveUp 调用会失败。所以是否向上或者放置 Beeper，我们需要再加一个判断：

while (frontIsClear()) {
    move();
    if (frontIsClear()) {
        move();
        putBeeper();
        if (frontIsBlocked()) {
        moveUp();
        if(frontIsClear()){ // moveUp失败的情况
            move();
            putBeeper();
        }
        }
    } else {
        moveUp();
        if (frontIsClear()) { // moveUp失败的情况
        putBeeper();
        }
    }
}

至此我们完成了整个过程的调用分析，对每个函数的前置后置条件加以区分和约束，使程序最终达到稳定。

回答前面的问题：

Q: 函数可以随便调用吗？如果不是，调用函数的条件是什么呢？

A: 函数是对过程的一个抽象，每次调用都必须检查前置条件和后置条件。

最后，我们将整个过程放置到 fixGeneralCase 函数中，对于只有一列的情况，我们做一个 fixOneColumnCase 函数单独处理就好。

总结

CheckerboardKarel

完整的代码如下：

/*
 * File: CheckerboardKarel.java
 * ----------------------------
 * When you finish writing it, the CheckerboardKarel class should draw
 * a checkerboard using beepers, as described in Assignment 1.  You
 * should make sure that your program works for all of the sample
 * worlds supplied in the starter folder.
 */

import stanford.karel.*;

public class CheckerboardKarel extends SuperKarel {
  public void run() {
    putBeeper();
    if (frontIsBlocked()) {
      fixOneColumnCase(); // Special case
    } else {
      fixGeneralCase(); // General case
    }
  }

  // pre-condition: front is blocked
  // post-condition: front is blocked
  private void fixOneColumnCase() {
    turnLeft();
    while (frontIsClear()) {
      move();
      if (frontIsClear()) {
        move();
        putBeeper();
      }
    }
  }

  // pre-condition: front is clear
  // post-condition: front is blocked
  private void fixGeneralCase() {
    while (frontIsClear()) { // General case
      // pre-condition: front is clear
      move();
      // post-condition: front is clear/blocked

      // So, you need to deal with two conditions.
      if (frontIsClear()) {
        // condition 1: front is clear
        move();
        putBeeper();
        // post-condition: front is clear/blocked

        // Again, you need to double check the blocked condition.
        // pre-condition: front is blocked
        if (frontIsBlocked()) {
          moveUp();
          if (frontIsClear()) { // just in case moveUp() is failure
            move();
            putBeeper();
          }
        }
        /* post-condition: front is clear */
      } else {
        // condition 2: front is blocked
        moveUp();
        if (frontIsClear()) // just in case moveUp() is failure
          putBeeper();
        /* post-condition: front is clear */
      }
    }
  }

  // pre-condition: front is blocked
  // post-condition: move to the next row and change direction
  private void moveUp() {
    if (facingEast()) {
      if (leftIsClear()) {
        turnLeft();
        move();
        turnLeft();
      }
    } else {
      if (rightIsClear()) {
        turnRight();
        move();
        turnRight();
      }
    }
  }
}