转载

Node.js 自动猜单词程序的实现

本文同步自我的 GitHub

过去，在文曲星等各种电子词典中，经常会有一个叫做猜单词的游戏。给定一个单词，告诉你这个单词有几个字母，然后你去猜。输入一个字母，如果单词中包含这个字母，则将单词中所有的这个字母都显示出来，如果猜错，则扣生命值，在生命值扣光之前全部猜对则为胜利。

过去我很喜欢玩这个游戏，因为它能让背单词显得不那么枯燥乏味，也能提高自己对单词构词规律的认识。但是这篇文章要说的，不是怎么去玩好这个游戏，而是怎么借助程序的力量去自动破解猜单词的难题。

背景

假设现在存在这样的一个接口 http://hangman.com/game/on ，它可以接受 post 请求，合法的请求共有四种。第一种是开始游戏，发送这样的数据可以重新开始一次新的游戏：

javascript{     "playerId": "classicemi",     "action": "startGame" }

服务器会返回如下信息：

javascript{  "message": "THE GAME IS ON",  "sessionId": "xxxx",  "data": {   "numberOfWordsToGuess": 80,   "numberOfGuessAllowedForEachWord": 10  } }

它告诉用户游戏已经开始，共有 80 个单词要猜，每个单词有十次猜错的机会。

用户还可以发送下一个单词的请求：

javascript{     "sessionId": "xxxx", //这是开始游戏时服务器返回的sessionId，用于识别用户     "action": "nextWord" }

服务器的返回信息如下：

javascript{  "sessionId": "xxxx",  "data": {   "word": "*****",   "totalWordCount": 1,   "wrongGuessCountOfCurrentWord": 0  } }

从这样的信息中可以知道，要猜的单词由 5 个字母组成，以及现在猜错了几次（当然现在是 0 次）。

要进行猜测的话，则发送如下请求：

javascript{     "sessionId": "xxxx",     "action": "guessWord",     "guess": "t" //举个栗子 }

如果猜测正确，服务器会返回如下数据:

javascript{  "sessionId": "xxxx",  "data": {   "word": "***S*",   "totalWordCount": 1,   "wrongGuessCountOfCurrentWord": 0  } }

如果猜错了，则返回如下数据：

javascript{  "sessionId": "xxxx",  "data": {   "word": "*****",   "totalWordCount": 1,   "wrongGuessCountOfCurrentWord": 1  } }

如果猜错超过十次还继续猜，则会返回如下信息：

javascript{     "message": "No more guess left." }

这时，只能选择跳转至下一个单词了，即再次发送 nextWord 请求。当用户猜完了 80 个词（当然也可以是任何时候），用户可以选择提交成绩结束游戏，只要发送如下请求：

javascript{     "sessionId": "xxxx",     "action" : "submitResult" }

服务器返回最终完成的信息：

javascript{     "message": "GAME OVER",     "sessionId": "xxxx",     "data": {         "playerId": "classicemi",          "sessionId": "xxxx",         "totalWordCount": 80,         "correctWordCount": 77,         "totalWrongGuessCount": 233,         "score": 1307,         "datetime": "2014-10-28 11:45:58"     } }

同时，在游戏过程中，用户可以随时查看当前已有的成绩，发送请求如下：

javascript{     "sessionId": "xxxx",     "action" : "getResult" }

返回信息如下：

javascript{  "sessionId": "xxxx",  "data": {   "totalWordCount": 40,   "correctWordCount": 20,   "totalWrongGuessCount": 100,   "score": 300  } }

OK，关于接口已经介绍完了，下面就来玩这个游戏吧。

思考

首先，由于我们要实现一个全自动的程序，不能借助人的力量，也就是说，用户的单词量的多少根本派不上用场。如果这个单词只是一个随机字符串的话，问题倒也简单了，随机猜字母即可。但是现在已经明确是英语单词，虽然比起随机字符串，范围大大缩小，但是要准确去猜英语单词，随机猜字母肯定是行不通了。

既不能借助用户的单词量，又不能使用随机字母，那么我们就需要一个样本总量足够大的单词表作为我们的数据库。在 UNIX 系统中， /usr/share/dict 目录中，有一个 words 文件，用 vim 打开看一下，发现里面有 20 多万个单词，这就是一个现成的单词数据库。不过根据后来的测试结果来看，20多万的单词量玩这个游戏还是有点不够，所以，还是去找开源的单词列表数据吧，最后我找到一个 65w 单词量的文件，正确率就比较高了。

流程

有了大量的单词数据，只是打好了基础，就像张无忌练了九阳神功，内力充沛，但是没有招式还是不行，充其量只是打不死，在这里我们需要的招式则是一个科学的算法。

不过在实现算法之前，先来把自动化程序的骨架搭起来，使流程控制能够跑通。我使用的是 Node.js 来执行程序，依赖的模块有两个，分别是 inquirer 和 request 。前者用来构建交互式的命令行程序，便于必要时接受用户的指令；后者用来方便地发送 post 请求。

程序的流程图如下：

      +-------+                | start |                +---+---+                 |                  v              +---------+-----------+      +-----------+     +--->+ flow control center | <-------------+ next word |     | +---------+-----------+      +-------+---+     |     |           ^      |  is the|guess finished?     |no       |     |     is the game finished?|  get the|result  +--------+yes+----------------------+      |     |no         yes|      |     v           v      |    +------+-------+       +----+---+     +-------+ make a guess |       | submit |       +--------------+       +--------+

根据流程图可以知道，我们需要几个函数来实现这个流程，图中的一个方块就对应一个函数，首先是流程的入口，程序最开始也是调用这个方法：

javascriptfunction startGame() {  inquirer.prompt(   [{    type: "input",    name: "startGame",    message: "please enter 'y' to automatically play the game, or enter session id to continue: "   }], function(answers) {    if (answers.startGame.toLowerCase() != 'y') {     sessionId = answers.startGame;     nextWord();     return;    }    setTimeout(function() {     auto('start');    }, 0);   }  ); }

这里面有一个 if 语句用来接受用户直接输入 sessionId 的情况，这是为了处理一旦网络中断或是程序异常的情况，便于用户直接输入 sessionId 来接着上次的进度继续执行。可以看到其中调用了 auto 方法，这个 auto 方法则是流程图中的 flow control center ，它会根据传入的参数来决定下一步去调用哪个方法(函数中的一些变量的作用后面会作解释)：

javascriptfunction auto(data, letterToGuess) {  if (data == 'start') {   options.body = {    "playerId": playerId,    "action": "startGame"   };   request(options, function(err, res, data) {    if (!err && res.statusCode == 200) {     console.log(data)     console.log('game restarted，your sessionId is: ', data.sessionId);     sessionId = data.sessionId;     setTimeout(function() {      auto(data);     }, 0);    } else {     console.log(err);    }   });   return;  }  // game start  if (data.message && data.message == 'THE GAME IS ON') {   sessionId = data.sessionId;   setTimeout(nextWord, 0);   return;  }  if (data.message && data.message == 'No more word to guess.') {   setTimeout(getResult, 0);   return;  }  // unfinished situation  if (data.data.word.indexOf('*') > -1    && data.data.wrongGuessCountOfCurrentWord < 10    && data.data.totalWordCount <= 80) {   setTimeout(function() {    guess(data.data.word, data.data.wrongGuessCountOfCurrentWord, letterToGuess);   }, 0);  } else if (data.data.word.indexOf('*') == -1    || data.data.wrongGuessCountOfCurrentWord >= 10) { // guess finished   // 猜词完毕后，复原辅助变量   wordsMatchLength = [];   letterFrequency = {};   wrongNum = 0;   lettersGuessed = '';   setTimeout(nextWord, 0);  } else if (data.data.totalWordCount >= 80 && data.data.wrongGuessCountOfCurrentWord >= 10) {   setTimeout(getResult, 0);  } }

接下来是实现 nextWord 功能和 guessWord 功能的函数：

javascriptfunction nextWord() {  options.body = {   "sessionId": sessionId,   "action": "nextWord"  };  request(options, function(err, res, data) {   if (err) {    console.log(err);   } else if(data.message) {    console.log(data.message);   } else {    console.log('current word: ', data.data.word);    console.log('current word count: ', data.data.totalWordCount);    console.log('wrong guess: ', data.data.wrongGuessCountOfCurrentWord + ' times');    index = 0;   }   auto(data);  }); } function guess(word, wrongNum, letter) {  var letterToGuess = filter(word, wrongNum, letter);  options.body = {   "sessionId": sessionId,   "action": "guessWord",   "guess": letterToGuess.toUpperCase()  };  request(options, function(err, res, data) {   if (err) {    console.log(err);   } else if(data.message) {    console.log(message);   } else {    console.log('your guess: ', letterToGuess.toUpperCase());    console.log('current word: ', data.data.word);    console.log('current word count: ', data.data.totalWordCount);    console.log('wrong guess: ', data.data.wrongGuessCountOfCurrentWord + ' times');   }   setTimeout(function() {    auto(data, letterToGuess);   }, 0);  }); }

最后是获取成绩和提交成绩的方法：

javascriptfunction getResult() {  options.body = {   "sessionId": sessionId,   "action": "getResult"  };  function submitDicide() {   inquirer.prompt(    [{     type: "input",     name: "submitDicision",     message: "enter 'y' to submit your score or enter 'n' to restart: "    }], function(answers) {     if (answers.submitDicision.toLowerCase() != 'y' && answers.submitDicision.toLowerCase() != 'n') {      console.log('illegal command, please reenter: ');      submitDicide();      return;     }     switch (answers.submitDicision.toLowerCase()) {      case 'y':       submit();       break;      case 'n':       startGame();       break;      default:       break;     }    }   );  }  request(options, function(err, res, data) {   if (err) {    console.log(err);   } else if(data.message) {    console.log(message);   } else {    console.log(data);    console.log('current word: ', data.data.word);    console.log('current word count: ', data.data.totalWordCount);    console.log('wrong guess: ', data.data.wrongGuessCountOfCurrentWord + ' times');    console.log('current score: ', data.data.score);    submitDicide();   }  }); } function submit() {  options.body = {   "sessionId": sessionId,   "action": "submitResult"  };  request(options, function(err, res, data) {   if (err) {    console.log(err);   } else {    console.log('player: ', data.data.playerId);    console.log('session id: ', data.data.sessionId);    console.log('total word count: ', data.data.totalWordCount);    console.log('correct word count: ', data.data.correctWordCount);    console.log('total wrong guess count: ', data.data.totalWrongGuessCount);    console.log('total score: ', data.data.score);    console.log('submit time: ', data.data.datetime);   }  }); }

由于整个程序的方法之间会一直相互调用，为了防止调用栈过深，所有的调用都用 setTimeout 改成了异步的方式。

算法

与自动化流程相关的函数都已经准备好了，接下来需要实现的就是算法了。说是算法，其实就是充分利用已有的信息对词典进行筛选的过程，首先要对现有的词典文件进行一些预处理的工作，这些工作在执行程序的一开始就会完成：

javascript// 同步方式读取字典文件 var dict = fs.readFileSync('words.txt', 'utf-8'); // 获得保存所有单词的数组 var wordArr = dict.split('/r/n');

接下来就是核心函数 filter ，它位于 guess 方法中，用来分析数据，返回接下来应该猜哪个字母，它的工作流程如下：

第一次调用时，根据要猜单词的长度遍历数组 wordArr ，筛选出长度符合条件的单词并 push 到 wordsMatchLength 数组中：

javascriptif (!wordsMatchLength.length) {     for (var i = 0, len = wordArr.length; i < len; i++) {         if (wordArr[i].length === word.length) {             wordsMatchLength.push(wordArr[i]);         }     } }

对 wordsMatchLength 数组进行双循环遍历，借助一个空对象 letterFrequency ，选出这些单词中出现频率最高的字母，并返回。

javascriptfor (var i = 0, len = wordsMatchLength.length; i < len; i++) {  for (var j = 0, innerLen = wordsMatchLength[i].length; j < innerLen; j++) {   letterFrequency[wordsMatchLength[i][j].toLowerCase()] == undefined     ? letterFrequency[wordsMatchLength[i][j].toLowerCase()] = 1     : letterFrequency[wordsMatchLength[i][j].toLowerCase()]++;  } } for (var key in letterFrequency) {  if (letterFrequency[key] > frequency && lettersGuessed.indexOf(key) < 0) {   frequency = letterFrequency[key];   l = key;  } }

这是猜第一个字母的方法，后续的筛选将要依赖之前猜词的结果来进行， filter 方法在递归中会被重复调用，之前猜词的结果会作为参数传入。

如果上一次猜对，那么返回的信息大概会长这样：

javascriptword: **t**u*

这显然是一种模式，可以将它转化为正则去筛选候选数组，我又实现了一个将此类字符串转化为正则的方法：

javascriptfunction generatePattern(word) {  var patternStr = '';  var starNum = 0;  for (var i = 0, len = word.length; i < len; i++) {   if (word[i] == '*') {    starNum = starNum + 1;   } else {    patternStr = patternStr + (starNum ? '//w{' + starNum + '}' : '') + word[i];    starNum = 0;   }  }  // 修正结尾的星号  patternStr = patternStr + (starNum ? '//w{' + starNum + '}' : '');  return new RegExp(patternStr, 'i'); }

得到正则后，用这个正则去过滤一下 wordsMatchLength 数组，删掉不匹配的单词：

javascriptfor (var i = 0, len = wordsMatchLength.length; i < len; i++) {  if (wordsMatchLength[i] && !generatePattern(word).test(wordsMatchLength[i])) {   wordsMatchLength.splice(i, 1);   i--;   len--;  } }

如果上一次猜错了呢，那么上一次猜了哪个字母，就说明正确的单词中不应该包含它，那么遍历一下 wordsMatchLength 数组，凡是包含这个字母的单词通通干掉：

javascriptfor (var i = 0, len = wordsMatchLength.length; i < len; i++) {     if (wordsMatchLength[i] &&      (wordsMatchLength[i].indexOf(letter.toLowerCase()) > -1 || wordsMatchLength[i].indexOf(letter.toUpperCase()) > -1)) {  wordsMatchLength.splice(i, 1);  i--;  len--;     } }

过滤工作完成后，要做的就是再统计一次字母频率，选择最常出现的那个即可。

另外，还需要做一些修正工作，来应对所猜单词过于偏门，没有出现在单词库中的情况，准备一个备用数组，里面的单词顺序按照一般情况下字母的出现频率排列，一旦单词库被过滤完，就去遍历这个数组，选出频率最高，而之前还没有猜过的字母并返回。这时候就看运气了。

同时也要记住在没猜完一个单词后要把候选数组清空，纪录猜错次数和已猜过字母的变量也要复原，不要影响后面的计算。