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

aaron 发布于2019-08-21 10:30 / 2695人阅读

摘要：本文同步自我的过去，在文曲星等各种电子词典中，经常会有一个叫做猜单词的游戏。算法与自动化流程相关的函数都已经准备好了，接下来需要实现的就是算法了。最后附上完整的源码实现源码

本文同步自我的 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("
");

接下来就是核心函数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--;
    }
}

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

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

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

统计字母出现频率的时候，同一个单词中的同一个字母，不论出现几次都只算一次，比如 e 或 s 这样的字母，在一个单词中可能出现很多次，但是没有必要重复计数。

当候选数组被过滤完时，可以不用备用数组，切换为用户手动输入，这样可以利用用户英语构词法的知识进行有目的的猜测，但这种方法偏离了全自动程序的初衷。

最后就要借助对构词法的科学计算进行优化了，这种计算需要专业知识的支撑，普通开发者无法胜任。

最后附上完整的源码实现：
源码

云服务器 GPU云服务器背单词小程序c语言支持node.js的云服务器 js做一个猜数字的 linux常用的单词

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85650.html

上一篇：【译】Impress.js制作酷炫Presentation PPT

下一篇：关于单位转换问题（M, G, TB, PB)

相关文章

如何利用Python写猜数字和字母的游戏

　　Python作为一门常见的编程语言，可以用到的地方是比较的多的，而且他还能够去编程相关的游戏，那么，下文就会给大家教一个比较简单的小游戏，就是写猜数字和字母的游戏，详细的内容可以看下文，看完之后，可以自己去手动敲下代码哦。　　前言　　学完语法和正在学习语法的时候，我们可以在空闲的时候，写几个简单的小项目，今天我们就用最基础的语法看两个实战语法练习　　猜数字游戏　　项目游戏说明：让用户输入一个数...

89542767 2022-11-10 15:31 评论0 收藏0

[零基础学python]用while来循环

摘要：我在这里将他写的程序恭录于此，单元李航同学不要见怪，如果李航同学认为此举侵犯了自己的知识产权，可以告知我，我马上撤下此代码。我用的是，在输入指令上区别于李同学程序用变量接收了输入的内容。 while，翻译成中文是当...的时候，这个单词在英语中，常常用来做为时间状语，while ... someone do somthing，这种类型的说法是有的。在python中，它也有这个含义，不过...

Tony 2019-07-24 17:37 评论0 收藏0

Vue.js新手入门指南[转载]

摘要：就是一个用于搭建类似于网页版知乎这种表单项繁多，且内容需要根据用户的操作进行修改的网页版应用。单页应用程序顾名思义，单页应用一般指的就是一个页面就是应用，当然也可以是一个子应用，比如说知乎的一个页面就可以视为一个子应用。最近在逛各大网站，论坛，以及像SegmentFault等编程问答社区，发现Vue.js异常火爆，重复性的提问和内容也很多，楼主自己也趁着这个大前端的热潮，着手学习了一...

MartinHan 2019-08-23 11:50 评论0 收藏0

这事要从node node.js说起

导读：兴许所有程序员都有命名困难症，在考虑变量、常量、方法、类、文件等命名时，总会千方百计尝试一些语义化的方式去实现。曾经有那么一段时间，一些node初学的同学遇到了同样的问题：Hello World 跑不动！原文首发于个人博客：这事要从node node.js说起 0. 谜之 Hello World 问题的起源非常简单，当我们在编写一个入门程序时，就会迅速想起那句脍炙人口的语句： conso...

Acceml 2019-08-20 18:58 评论0 收藏0

发表评论

登陆后可评论

0条评论

aaron

男|高级讲师

我要关注我要私信

TA的文章
阅读更多

#开学季#无忧云：4核/4G/80G/5Mbps不限流量/洛阳BGP/月付59元，带5G防御

阅读 3838·2021-09-10 11:22

Pillow 10行代码给营业执照模板写数据，批量生产

阅读 2304·2021-09-03 10:30

记：原样输出文字，不做任何处理

阅读 3611·2019-08-30 15:55

如何在React中优雅的处理doubleClick

阅读 1819·2019-08-30 15:44

怎样分析页面加载慢

阅读 824·2019-08-30 15:44

纯css三角形及其应用

阅读 533·2019-08-30 14:04

vue中的适配：px2rem

阅读 3026·2019-08-29 17:18

swiper的使用

阅读 1247·2019-08-29 15:04

最新活动

资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

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

相关文章

如何利用Python写猜数字和字母的游戏

[零基础学python]用while来循环

Vue.js新手入门指南[转载]

**这事要从node node.js说起**

发表评论

0条评论

aaron

男|高级讲师

TA的文章

#开学季#无忧云：4核/4G/80G/5Mbps不限流量/洛阳BGP/月付59元，带5G防御

Pillow 10行代码给营业执照模板写数据，批量生产

记：原样输出文字，不做任何处理

如何在React中优雅的处理doubleClick

怎样分析页面加载慢

纯css三角形及其应用

vue中的适配：px2rem

swiper的使用

最新活动