初探 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的基类,用来存放展示方法。抛开展示部分不谈,NonogramPlayNonogramEdit两个类几乎不剩下什么了。

我们先来看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 + EMPTYTEMPORARILY_EMPTY + FILLED ,则跳出;
  • UNSET + TEMPORARILY_* = TEMPORARILY_*
  • TEMPORARILY_FILLED + TEMPORARILY_FILLED = TEMPORARILY_FILLED
  • TEMPORARILY_EMPTY + TEMPORARILY_EMPTY = TEMPORARILY_EMPTY
  • TEMPORARILY_FILLED + TEMPORARILY_EMPTY = INCONSTANT
  • 网格中的FILLEDEMPTYINCONSTANT都是最终情况,不再变化。

当所有中可能情况都被处理完,执行setBackToGrid方法,三种临时状态要被转换为一般状态。TEMPORARILY_FILLED对应FILLEDTEMPORARILY_EMPTY对应EMPTYINCONSTANT对应UNSET

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

宽以待人。

——中国先贤

在执行getAllSituations之前,设置某个表示错误的变量为真。执行mergeSituation时,如果未出现TEMPORARILY_FILLED + EMPTYTEMPORARILY_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-InfinityNaN的运算规则,就会发现这两种方式的作用是一模一样的。那为什么这样反而不好呢?一个次要原因是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 上喂一颗星星!