初探 ES6：构建和解决数织

这是一篇旧文，其中的内容可能已经过时。

项目经过了大量重构，将与本文示例有所差别。

这是一个交互式解数织的应用，给大家先睹为快。

大一暑假时用 C++写了个两百行的小程序，用来解 10×10 的数织。后来整理硬盘时发现了这份遗留文件，惊叹于它的丑陋的同时，用 JavaScript 改写了它。刚好当时接触到 ES6 和程序设计方面的指导规范，于是照着它们一边学习，一边重构代码。本文介绍了数织的规则、解法、程序实现，以及构建一个用来玩的数织游戏。

什么是数织？

数织是一种逻辑游戏，以猜谜的方式绘画位图。在一个网格中，每一行和列都有一组数，玩家需根据它们来填满或留空格子，最后就可以由此得出一幅图画。例如，『4 8 3』的意思就是指该行或列上有三条独立的线，分别占了 4、8 和 3 格，而每条线最少要由一个空格分开。传统上，玩家以黑色填满格子，以『×』号标记一定不需要填充的格子。

——维基百科

当然了，一图胜千言：

怎么样，规则是不是很清晰易懂？那么先来个小挑战吧（答案见下一页）：

刚才走到了第几关？想看答案，点击下方的刷新图标就可以了。

解法

和数独一样，数织也是一个 NP 完全问题。这里介绍一种简单暴力但是不完全的解法，意为不保证能找出某个数织的唯一解。它就是穷举法。

我们来单看某一行：假设这行有 7 格宽，提示数字为 2 和 3。穷举出所有情况： 2 3 |█|█|X|█|█|█|X| 2 3 |█|█|X|X|█|█|█| 2 3 |X|█|█|X|█|█|█| 可以发现无论哪种情况下，第 2、5、6 位都是被填满的，那么可以标记为填满。接着去处理其他的行列。假如下一次处理到这行的时候，第一位已被标记为空，即 2 3 |X|█|?|?|█|█|?| 那么上述的前两种情况都与其矛盾，所以这行的最终结果就是第三种情况。

有些数织（左）本身有不止一个解。还有的（右）的确有唯一解，但是也不能被这种方法解出，这种情况就需要进行递归猜测了。

你可以点击用来表示不确定的浅灰色方块，以将它标记为填充，接着程序会按照当前的状态试着再解一次。

戳GitHub可以看到两份源代码，其中一份是 ES5 版本，另一份是 ES6 版本。虽然目前火狐 45 已经涵盖了用到的 ES6 语法了，但为了照顾大多数浏览器，本文包括 GitHub Pages 里的 demo 运行的都是 ES5 版本的。

比较两个版本，一个显著的差别是 ES5 版的代码都写在一个匿名函数里，而 ES6 版没有。有人问这样难道不会污染全局空间吗？答案是不会，因为 ES6 引入了模块的概念。作为一个模块，它并不是通过<script>标签来引入，而是在另一份文件中通过import语句来导入所需要的方法和函数。这点是不是和 Python 很像？

‘use strict’;

历史上有过『少写了一个var而弄崩了一个网站』的例子。开发者用 Node.js 做服务端，在某个函数中不用var声明变量就使用，于是当多个用户共同访问网站时，该变量被绑定在了全局空间上，导致用户数据相互干扰。那么如何防范这一点呢？用 JSLint 等工具审查代码当然也不错，但我将要介绍严格模式。

严格模式并不是 ES6 的新内容，它在 ES5 时代就被引入了。开启严格模式的方法为：在代码顶部或者函数内顶部放置'use strict'; 。严格模式有着更少的容错率，即非严格模式下能正常执行的语句在严格模式下可能会抛出错误。看起来像自讨苦吃？那我来说说它的好处。

JavaScript 是一种对开发者相当友好的弱类型语言，有很多内置方法即使出现了内部错误，也不会报错，取而代之的是静默失败。 多数情况下，它会让你免于处理各式各样的错误；然而事物都是有两面性的，当你的项目出现 bug 却迟迟找不到原因时，它有可能就是罪魁祸首。而严格模式让所有静默失败的操作都抛出错误。像我在上一篇文章里提到的，越能坚持严格的代码风格，就越能回避语法陷阱。关于严格模式的更多介绍，参见MDN。

严于律己。

——中国先贤

抽象

有了之前的铺垫，就可以专注于实现了。想想我要做什么？一种自动解答的数织（NonogramSolve），一种用来玩的数织（NonogramPlay），还有一种能直接编辑网格的数织（NonogramEdit），用来创建各种图案，让人或者机器来解。当然，它们都叫数织，就有一些公共的属性。

我用：

  • grid来表示数织的网格，是一个二维数组；对于每一个元素，用不同的常量标识它的状态；
  • rowHints来表示所有行的提示数字；
  • colHints来表示所有列的提示数字。

为了后面使用方便，再用：

  • m来表示网格的高度，即行数rowHints.length；
  • n来表示网格的宽度，即列数colHints.length。

它们也有一些公共的方法，比如说展示部分的。这部分将放到它们的基类中。我创建了一个叫做Nonogram的基类，用来存放展示方法。抛开展示部分不谈，NonogramPlay和NonogramEdit两个类几乎不剩下什么了。

我们先来看NonogramSolve。细致地梳理一遍解答步骤：

  1. 将所有步骤封装到solve方法里。
  2. 从第一行开始解起，解完之后顺延到下一行。如果这行已被完全解完，即不存在未确定的方格，那么作个标记，下次来到这里时不必花时间再解一遍。
  3. 所有行解完之后，解第一列；所有列解完之后，解第一行。用函数updateScanner控制行列的流程。如果连续地解完了所有的行列，没有一个网格发生变化，那么可以让过程结束，因为即使继续解也不会产生变化。
  4. 用方法solveSingleLine封装对每一行或者列的解答过程。传入两个参数，方向和行列数。将这两个参数传给工具方法getSingleLine，得到该行列的网格状态和提示数字。
  5. 如果网格中不存在未确定的方格，那么用工具方法checkCorrectness判断网格和提示数字是否一致。如果是，标记为已解决，否则报错。
  6. 按照提示数字，用getAllSituations方法取得网格所有可能的分布情况。对于每一种情况，用mergeSituation试着将它整合到先前的结果中。当所有情况都处理完之后，用setBackToGrid将解答结果放回网格中去。

最后一步还没有详细说明。我们得先看看单个网格在解答过程中的所有状态。当刚刚获取该行列的网格时，网格中可能存在三种状态：

  • FILLED：已填充；
  • EMPTY：已标空；
  • UNSET：未确定。

其中前两种状态都是某种最终状态，不论如何都不会变化。那么在通过getAllSituations方法取得若干种情况时，每种情况又包含了已填充和已标空的各种分布，而这种已填充和已标空必须能被后面的情况所覆盖。所以还要新增另外三种状态：

  • TEMPORARILY_FILLED：暂时填充；
  • TEMPORARILY_EMPTY：暂时标空；
  • INCONSTANT：已出现矛盾。

现在可以说明mergeSituation的作用了：每当传入一种情况，与现有的结果进行整合。规则为：

  • 如果出现TEMPORARILY_FILLED + EMPTY或TEMPORARILY_EMPTY + FILLED ，则跳出；
  • UNSET + TEMPORARILY_* = TEMPORARILY_*；
  • TEMPORARILY_FILLED + TEMPORARILY_FILLED = TEMPORARILY_FILLED；
  • TEMPORARILY_EMPTY + TEMPORARILY_EMPTY = TEMPORARILY_EMPTY；
  • TEMPORARILY_FILLED + TEMPORARILY_EMPTY = INCONSTANT。
  • 网格中的FILLED、EMPTY、INCONSTANT都是最终情况，不再变化。

当所有中可能情况都被处理完，执行setBackToGrid方法，三种临时状态要被转换为一般状态。TEMPORARILY_FILLED对应FILLED、TEMPORARILY_EMPTY对应EMPTY、INCONSTANT对应UNSET。

所有流程就是这样。另外，有句话叫做『永远不要信任用户的输入』，假如用户给的提示数字根本就没有解，那应该怎么办？当然有没有解不是一开始就能看出来的，不过可以在方法中多加一点判断，来处理这种特殊情况。

宽以待人。

——中国先贤

在执行getAllSituations之前，设置某个表示错误的变量为真。执行mergeSituation时，如果未出现TEMPORARILY_FILLED + EMPTY或TEMPORARILY_EMPTY + FILLED的冲突，就把那个变量设为假。这样就能完美地处理所有合理或不合理的输入了。

我们再来看看NonogramEdit。这个类的功能相当简单，事实上它的代码也是最短的。它可以按照给定的宽、高、阈值随机生成一个数织；按照网格计算出提示数字；以及响应点击事件，切换被点击方格的状态。按下不表。

最后来看看NonogramPlay。它的功能只有一个，即响应玩家的点击、拖动事件，然而操作方法却很讲究。我参考了许多数织游戏，选择了一种最自然合理的，然而实现起来略显复杂的操作方式：给玩家两种笔刷，『填充』和『标空』；假如玩家选择了『填充』笔刷，第一笔画在的格子状态为：

  • 已标空，那么程序不会做出任何响应；
  • 未确定，那么笔刷模式为『画笔』，即把接下来碰到的未确定的方格都变为已填充，已标空的和已填充的保持不变；
  • 已填充，那么笔刷模式为『橡皮』，即把接下来碰到的已填充的方格都变为未确定，已标空的和未确定的保持不变。

另外，笔刷能影响的范围也有所限制，即它只能影响接触的第一格和第二格所连成的线上。反过来，假如玩家选择了『标空』笔刷，那么将刚才规则的『已标空』和『已填充』字样对换，就是『标空』笔刷的规则。换句话说，这两种笔刷的地位是对等的。

三种类的功能都分析完了，下面可以着手构建基类Nonogram了。基类用来存放工具方法、展示相关方法 。

实现

在代码的开头，放置严格模式标识、全局工具函数和常量。

'use strict';

const sum = (array) => array.reduce((a, b) => a + b, 0);
const deepCopy = (object) => JSON.parse(JSON.stringify(object));
const eekwall = (object1, object2) => object1.toString() === object2.toString();
// eekwall 长得像 equal，听起来也像 equal，但毕竟不是真正的 equal

const FILLED = true;
const EMPTY = false;
const UNSET = undefined;
const TEMPORARILY_FILLED = 1;
const TEMPORARILY_EMPTY = -1;
const INCONSTANT = 0;

此时此刻我要记下一点想法，为了提醒未来的自己不进入一个误区，因为下面要说的是一个我非常容易犯的错误。

之前介绍过mergeSituation方法的作用。目前它的核心代码如下所示，当然这是好的：

status.forEach((cell, i) => {
  if (cell === TEMPORARILY_FILLED) {
    if (this.line[i] === TEMPORARILY_EMPTY) {
      this.line[i] = INCONSTANT;
    } else if (this.line[i] === UNSET) {
      this.line[i] = TEMPORARILY_FILLED;
    }
  } else if (cell === TEMPORARILY_EMPTY) {
    if (this.line[i] === TEMPORARILY_FILLED) {
      this.line[i] = INCONSTANT;
    } else if (this.line[i] === UNSET) {
      this.line[i] = TEMPORARILY_EMPTY;
    }
  }
});

但我通常觉得简短的代码看起来更加舒服：

const FILLED = true;
const EMPTY = false;
const UNSET = 0;
const TEMPORARILY_FILLED = Infinity;
const TEMPORARILY_EMPTY = -Infinity;
const INCONSTANT = NaN;

// ...

status.forEach((cell, i) => {
  if (this.line[i] !== FILLED && this.line[i] !== EMPTY) {
    this.line[i] += cell;
  }
});

这是什么魔法，让代码短了这么多？如果你熟悉Infinity、-Infinity和NaN的运算规则，就会发现这两种方式的作用是一模一样的。那为什么这样反而不好呢？一个次要原因是NaN。众所周知，NaN === NaN是假，那假如我要判断一个cell是不是INCONSTANT，就必须写isNaN(cell)而不是cell === INCONSTANT，后者会返回一个不期望的结果。主要的原因是代码强耦合，单看mergeSituation看不到它的逻辑，必须结合常量具体的值来看，而一旦常量的值发生变更，mergeSituation将失效！这就与设置常量的初衷『消除耦合』相违背了。

回到代码，看基类的构造。ES6 可以用class声明类了，然而它只是语法糖，底层还是用原型实现的继承。并且它有个缺点，就是只能在类里写方法，不能写属性。所以我只好混用了原型和类。据说 ES7 将允许把属性写在类里。不要把属性共享在原型上。参见：http://codereview.stackexchange.com/questions/28344/should-i-put-default-values-of-attributes-on-the-prototype-to-save-space/28360#28360

class Nonogram {
  constructor() {
    return;
  }

  getSingleLine(direction, i) {
    let g = [];
    if (direction === 'row') {
      for (let j = 0; j < this.n; j++) {
        g[j] = this.grid[i][j];
      }
    } else if (direction === 'col') {
      for (let j = 0; j < this.m; j++) {
        g[j] = this.grid[j][i];
      }
    }
    return g;
  }
  removeZeroHints() {
    this.rowHints.forEach(removeZeroElement);
    this.colHints.forEach(removeZeroElement);

    function removeZeroElement(array, j, self) {
      self[j] = array.filter(Math.sign);
    }
  }
  getHints(direction, i) {
    return deepCopy(this[`${direction}Hints`][i]);
  }
  calculateHints(direction, i) {
    let hints = [];
    let line = this.getSingleLine(direction, i);
    line.reduce((lastIsFilled, cell) => {
      if (cell === FILLED) {
        lastIsFilled ? (hints[hints.length - 1] += 1) : hints.push(1);
      }
      return cell === FILLED;
    }, false);
    return hints;
  }
  checkCorrectness(direction, i) {
    return this.calculateHints(direction, i).toString() === this[`${direction}Hints`][i].toString();
  }

  getLocation(x, y) {
    // 获取点击所在区域
  }

  print() {
    if (this.canvas) {
      this.printGrid();
      this.printHints();
      this.printController();
    }
  }
  printGrid() {
    // 展示相关
  }
  printCell(status) {
    // 展示相关
  }
  printMesh() {
    // 展示相关
  }
  printHints() {
    // 展示相关
  }
  printController() {
    // 展示相关
  }
}
Object.assign(Nonogram.prototype, {
  backgroundColor: '#fff',
  filledColor: '#999',
  unsetColor: '#ccc',
  correctColor: '#0cf',
  wrongColor: '#f69',
  meshColor: '#999',
  isMeshed: false,
  isBoldMeshOnly: false,
  boldMeshGap: 5,
});

三个子类的构造大同小异，以NonogramSolve为例。其中canvas参数既可以是<canvas>元素本身，也可以是它的id属性。构造函数中的config参数是一个对象，用来自定义实例属性。

函数的参数不应该多于三个，剩余的应当被封装为对象。

——《Clean Code》

class NonogramSolve extends Nonogram {
  constructor(rowHints, colHints, canvas, config) {
    super();
    Object.assign(this, config);
    // 用配置参数赋值
    this.rowHints = deepCopy(rowHints);
    this.colHints = deepCopy(colHints);
    this.removeNonPositiveHints();
    this.m = rowHints.length;
    this.n = colHints.length;
    this.grid = new Array(this.m);
    for (let i = 0; i < this.m; i++) {
      this.grid[i] = new Array(this.n);
    }
    this.rowHints.forEach((row) => {
      row.isCorrect = false;
      row.unchangedSinceLastScanned = false;
    });
    this.colHints.forEach((col) => {
      col.isCorrect = false;
      col.unchangedSinceLastScanned = false;
    });

    this.canvas = canvas instanceof HTMLCanvasElement ? canvas : document.getElementById(canvas);
    if (!this.canvas || this.canvas.hasAttribute('occupied')) {
      return;
    }

    this.canvas.width = this.width || this.canvas.clientWidth;
    this.canvas.height = (this.canvas.width * (this.m + 1)) / (this.n + 1);
    this.canvas.nonogram = this;
    this.canvas.addEventListener('click', this.click);
    this.print();
  }

  get success() {
    return new Event('success');
  }
  get error() {
    return new Event('error');
  }
  get cellValueMap() {
    const t = new Map();
    t.set(TEMPORARILY_FILLED, FILLED);
    t.set(TEMPORARILY_EMPTY, EMPTY);
    t.set(INCONSTANT, UNSET);
    return t;
  }
  // 其他方法
}

下面来看看最难的一部分，getAllSituations的实现。前面说了，它的作用是对于给定的行的长度和提示数字，求出所有可能的填充状态。那么这些状态应该怎么描述呢？还是用前面的例子，提示数字为 2 和 3，长度为 7：

  1. |█|█|X|█|█|█|X| ---- blanks: [0, 1]
  2. |█|█|X|X|█|█|█| ---- blanks: [0, 2]
  3. |X|█|█|X|█|█|█| ---- blanks: [1, 1]

我们仔细观察可以发现，每个提示数字对应的方格组左边的空格组的长度组成的数组，与每种情况一一对应。两个数组的长度应相等。假如我们把空格组叫做blanks，提示数字叫做hints，那么每行的组成从左到右就是：blanks[0]个空格，hints[0]个填充，blanks[1]个空格，hints[1]个填充……直到数组结束，若长度未满，仍以空格填充。所以这个问题转化为：求一个整数数组blanks，长度等于hints的长度，首位不小于 0，其余位不小于 1，且元素之和加上提示数字之和不大于行的长度。用名词来概括，就是深度优先搜索。方法调用与构造如下：

this.getAllSituations(this.line.length - sum(this.hints) + 1);

class NonogramSolve {
  // ...

  getAllSituations(max, array = [], index = 0) {
    if (index === this.hints.length) {
      this.blanks = array.slice(0, this.hints.length);
      this.blanks[0] -= 1;
      return this.mergeSituation();
    }

    for (let i = 1; i <= max; i++) {
      array[index] = i;
      this.getAllSituations(max - array[index], array, index + 1);
    }
  }
}

剩余部分的实现并不深奥，就不详谈了，感兴趣的读者可以戳GitHub继续看源代码。似乎还没说这个项目到底怎么玩？GitHub 里也有介绍；如果觉得赞，请在 GitHub 上喂一颗星星！