不过在实现算法之前,先来把自动化程序的骨架搭起来,使流程控制能够跑通。我使用的是 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 |
+--------------+ +--------+
function 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,它会根据传入的参数来决定下一步去调用哪个方法(函数中的一些变量的作用后面会作解释):
function 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);
}
}
if (!wordsMatchLength.length) {
for (var i = 0, len = wordArr.length; i < len; i++) {
if (wordArr[i].length === word.length) {
wordsMatchLength.push(wordArr[i]);
}
}
}
function 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数组,删掉不匹配的单词:
for (var i = 0, len = wordsMatchLength.length; i < len; i++) {
if (wordsMatchLength[i] && !generatePattern(word).test(wordsMatchLength[i])) {
wordsMatchLength.splice(i, 1);
i--;
len--;
}
}
过去,在文曲星等各种电子词典中,经常会有一个叫做猜单词的游戏。给定一个单词,告诉你这个单词有几个字母,然后你去猜。输入一个字母,如果单词中包含这个字母,则将单词中所有的这个字母都显示出来,如果猜错,则扣生命值,在生命值扣光之前全部猜对则为胜利。
过去我很喜欢玩这个游戏,因为它能让背单词显得不那么枯燥乏味,也能提高自己对单词构词规律的认识。但是这篇文章要说的,不是怎么去玩好这个游戏,而是怎么借助程序的力量去自动破解猜单词的难题。
背景
假设现在存在这样的一个接口
http://hangman.com/game/on
,它可以接受 post 请求,合法的请求共有四种。第一种是开始游戏,发送这样的数据可以重新开始一次新的游戏:服务器会返回如下信息:
它告诉用户游戏已经开始,共有 80 个单词要猜,每个单词有十次猜错的机会。
用户还可以发送下一个单词的请求:
服务器的返回信息如下:
从这样的信息中可以知道,要猜的单词由 5 个字母组成,以及现在猜错了几次(当然现在是 0 次)。
要进行猜测的话,则发送如下请求:
如果猜测正确,服务器会返回如下数据:
如果猜错了,则返回如下数据:
如果猜错超过十次还继续猜,则会返回如下信息:
这时,只能选择跳转至下一个单词了,即再次发送
nextWord
请求。当用户猜完了 80 个词(当然也可以是任何时候),用户可以选择提交成绩结束游戏,只要发送如下请求:服务器返回最终完成的信息:
同时,在游戏过程中,用户可以随时查看当前已有的成绩,发送请求如下:
返回信息如下:
OK,关于接口已经介绍完了,下面就来玩这个游戏吧。
思考
首先,由于我们要实现一个全自动的程序,不能借助人的力量,也就是说,用户的单词量的多少根本派不上用场。如果这个单词只是一个随机字符串的话,问题倒也简单了,随机猜字母即可。但是现在已经明确是英语单词,虽然比起随机字符串,范围大大缩小,但是要准确去猜英语单词,随机猜字母肯定是行不通了。
既不能借助用户的单词量,又不能使用随机字母,那么我们就需要一个样本总量足够大的单词表作为我们的数据库。在 UNIX 系统中,
/usr/share/dict
目录中,有一个words
文件,用 vim 打开看一下,发现里面有 20 多万个单词,这就是一个现成的单词数据库。不过根据后来的测试结果来看,20多万的单词量玩这个游戏还是有点不够,所以,还是去找开源的单词列表数据吧,最后我找到一个 65w 单词量的文件,正确率就比较高了。流程
有了大量的单词数据,只是打好了基础,就像张无忌练了九阳神功,内力充沛,但是没有招式还是不行,充其量只是打不死,在这里我们需要的招式则是一个科学的算法。
不过在实现算法之前,先来把自动化程序的骨架搭起来,使流程控制能够跑通。我使用的是 Node.js 来执行程序,依赖的模块有两个,分别是
inquirer
和request
。前者用来构建交互式的命令行程序,便于必要时接受用户的指令;后者用来方便地发送 post 请求。程序的流程图如下:
根据流程图可以知道,我们需要几个函数来实现这个流程,图中的一个方块就对应一个函数,首先是流程的入口,程序最开始也是调用这个方法:
这里面有一个 if 语句用来接受用户直接输入
sessionId
的情况,这是为了处理一旦网络中断或是程序异常的情况,便于用户直接输入sessionId
来接着上次的进度继续执行。可以看到其中调用了auto
方法,这个auto
方法则是流程图中的 flow control center,它会根据传入的参数来决定下一步去调用哪个方法(函数中的一些变量的作用后面会作解释):接下来是实现
nextWord
功能和guessWord
功能的函数:最后是获取成绩和提交成绩的方法:
由于整个程序的方法之间会一直相互调用,为了防止调用栈过深,所有的调用都用
setTimeout
改成了异步的方式。算法
与自动化流程相关的函数都已经准备好了,接下来需要实现的就是算法了。说是算法,其实就是充分利用已有的信息对词典进行筛选的过程,首先要对现有的词典文件进行一些预处理的工作,这些工作在执行程序的一开始就会完成:
接下来就是核心函数
filter
,它位于guess
方法中,用来分析数据,返回接下来应该猜哪个字母,它的工作流程如下:第一次调用时,根据要猜单词的长度遍历数组
wordArr
,筛选出长度符合条件的单词并push
到wordsMatchLength
数组中:对
wordsMatchLength
数组进行双循环遍历,借助一个空对象letterFrequency
,选出这些单词中出现频率最高的字母,并返回。这是猜第一个字母的方法,后续的筛选将要依赖之前猜词的结果来进行,
filter
方法在递归中会被重复调用,之前猜词的结果会作为参数传入。如果上一次猜对,那么返回的信息大概会长这样:
这显然是一种模式,可以将它转化为正则去筛选候选数组,我又实现了一个将此类字符串转化为正则的方法:
得到正则后,用这个正则去过滤一下
wordsMatchLength
数组,删掉不匹配的单词:如果上一次猜错了呢,那么上一次猜了哪个字母,就说明正确的单词中不应该包含它,那么遍历一下
wordsMatchLength
数组,凡是包含这个字母的单词通通干掉:过滤工作完成后,要做的就是再统计一次字母频率,选择最常出现的那个即可。
另外,还需要做一些修正工作,来应对所猜单词过于偏门,没有出现在单词库中的情况,准备一个备用数组,里面的单词顺序按照一般情况下字母的出现频率排列,一旦单词库被过滤完,就去遍历这个数组,选出频率最高,而之前还没有猜过的字母并返回。这时候就看运气了。
同时也要记住在没猜完一个单词后要把候选数组清空,纪录猜错次数和已猜过字母的变量也要复原,不要影响后面的计算。
优化
以上方法还有一些优化的空间:
最后附上完整的源码实现: 源码