Node.js 自動猜單詞程序的實現(xiàn)

aaron 發(fā)布于2019-08-21 10:30 / 2739人閱讀

摘要：本文同步自我的過去，在文曲星等各種電子詞典中，經(jīng)常會有一個叫做猜單詞的游戲。算法與自動化流程相關(guān)的函數(shù)都已經(jīng)準備好了，接下來需要實現(xiàn)的就是算法了。最后附上完整的源碼實現(xiàn)源碼

本文同步自我的 GitHub

過去，在文曲星等各種電子詞典中，經(jīng)常會有一個叫做猜單詞的游戲。給定一個單詞，告訴你這個單詞有幾個字母，然后你去猜。輸入一個字母，如果單詞中包含這個字母，則將單詞中所有的這個字母都顯示出來，如果猜錯，則扣生命值，在生命值扣光之前全部猜對則為勝利。

過去我很喜歡玩這個游戲，因為它能讓背單詞顯得不那么枯燥乏味，也能提高自己對單詞構(gòu)詞規(guī)律的認識。但是這篇文章要說的，不是怎么去玩好這個游戲，而是怎么借助程序的力量去自動破解猜單詞的難題。

背景

假設(shè)現(xiàn)在存在這樣的一個接口http://hangman.com/game/on，它可以接受 post 請求，合法的請求共有四種。第一種是開始游戲，發(fā)送這樣的數(shù)據(jù)可以重新開始一次新的游戲：

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

服務(wù)器會返回如下信息：

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

它告訴用戶游戲已經(jīng)開始，共有 80 個單詞要猜，每個單詞有十次猜錯的機會。

用戶還可以發(fā)送下一個單詞的請求：

javascript{
    "sessionId": "xxxx", //這是開始游戲時服務(wù)器返回的sessionId，用于識別用戶
    "action": "nextWord"
}

服務(wù)器的返回信息如下：

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

從這樣的信息中可以知道，要猜的單詞由 5 個字母組成，以及現(xiàn)在猜錯了幾次（當然現(xiàn)在是 0 次）。

要進行猜測的話，則發(fā)送如下請求：

javascript{
    "sessionId": "xxxx",
    "action": "guessWord",
    "guess": "t" //舉個栗子
}

如果猜測正確，服務(wù)器會返回如下數(shù)據(jù):

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

如果猜錯了，則返回如下數(shù)據(jù)：

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

如果猜錯超過十次還繼續(xù)猜，則會返回如下信息：

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

這時，只能選擇跳轉(zhuǎn)至下一個單詞了，即再次發(fā)送nextWord請求。當用戶猜完了 80 個詞（當然也可以是任何時候），用戶可以選擇提交成績結(jié)束游戲，只要發(fā)送如下請求：

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

服務(wù)器返回最終完成的信息：

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"
    }
}

同時，在游戲過程中，用戶可以隨時查看當前已有的成績，發(fā)送請求如下：

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

返回信息如下：

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

OK，關(guān)于接口已經(jīng)介紹完了，下面就來玩這個游戲吧。
思考
首先，由于我們要實現(xiàn)一個全自動的程序，不能借助人的力量，也就是說，用戶的單詞量的多少根本派不上用場。如果這個單詞只是一個隨機字符串的話，問題倒也簡單了，隨機猜字母即可。但是現(xiàn)在已經(jīng)明確是英語單詞，雖然比起隨機字符串，范圍大大縮小，但是要準確去猜英語單詞，隨機猜字母肯定是行不通了。

既不能借助用戶的單詞量，又不能使用隨機字母，那么我們就需要一個樣本總量足夠大的單詞表作為我們的數(shù)據(jù)庫。在 UNIX 系統(tǒng)中，/usr/share/dict目錄中，有一個words文件，用 vim 打開看一下，發(fā)現(xiàn)里面有 20 多萬個單詞，這就是一個現(xiàn)成的單詞數(shù)據(jù)庫。不過根據(jù)后來的測試結(jié)果來看，20多萬的單詞量玩這個游戲還是有點不夠，所以，還是去找開源的單詞列表數(shù)據(jù)吧，最后我找到一個 65w 單詞量的文件，正確率就比較高了。
流程
有了大量的單詞數(shù)據(jù)，只是打好了基礎(chǔ)，就像張無忌練了九陽神功，內(nèi)力充沛，但是沒有招式還是不行，充其量只是打不死，在這里我們需要的招式則是一個科學的算法。

不過在實現(xiàn)算法之前，先來把自動化程序的骨架搭起來，使流程控制能夠跑通。我使用的是 Node.js 來執(zhí)行程序，依賴的模塊有兩個，分別是inquirer和request。前者用來構(gòu)建交互式的命令行程序，便于必要時接受用戶的指令；后者用來方便地發(fā)送 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 | +--------------+ +--------+

根據(jù)流程圖可以知道，我們需要幾個函數(shù)來實現(xiàn)這個流程，圖中的一個方塊就對應(yīng)一個函數(shù)，首先是流程的入口，程序最開始也是調(diào)用這個方法：

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的情況，這是為了處理一旦網(wǎng)絡(luò)中斷或是程序異常的情況，便于用戶直接輸入sessionId來接著上次的進度繼續(xù)執(zhí)行。可以看到其中調(diào)用了auto方法，這個auto方法則是流程圖中的 flow control center，它會根據(jù)傳入的參數(shù)來決定下一步去調(diào)用哪個方法(函數(shù)中的一些變量的作用后面會作解釋)：

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
        // 猜詞完畢后，復(fù)原輔助變量
        wordsMatchLength = [];
        letterFrequency = {};
        wrongNum = 0;
        lettersGuessed = "";
        setTimeout(nextWord, 0);
    } else if (data.data.totalWordCount >= 80 && data.data.wrongGuessCountOfCurrentWord >= 10) {
        setTimeout(getResult, 0);
    }
}

接下來是實現(xiàn)nextWord功能和guessWord功能的函數(shù)：

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);
        }
    });
}

由于整個程序的方法之間會一直相互調(diào)用，為了防止調(diào)用棧過深，所有的調(diào)用都用setTimeout改成了異步的方式。
算法
與自動化流程相關(guān)的函數(shù)都已經(jīng)準備好了，接下來需要實現(xiàn)的就是算法了。說是算法，其實就是充分利用已有的信息對詞典進行篩選的過程，首先要對現(xiàn)有的詞典文件進行一些預(yù)處理的工作，這些工作在執(zhí)行程序的一開始就會完成：

javascript// 同步方式讀取字典文件
var dict = fs.readFileSync("words.txt", "utf-8");
// 獲得保存所有單詞的數(shù)組
var wordArr = dict.split("
");

接下來就是核心函數(shù)filter，它位于guess方法中，用來分析數(shù)據(jù)，返回接下來應(yīng)該猜哪個字母，它的工作流程如下：

第一次調(diào)用時，根據(jù)要猜單詞的長度遍歷數(shù)組wordArr，篩選出長度符合條件的單詞并push到wordsMatchLength數(shù)組中：

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

對wordsMatchLength數(shù)組進行雙循環(huán)遍歷，借助一個空對象letterFrequency，選出這些單詞中出現(xiàn)頻率最高的字母，并返回。

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;
    }
}

這是猜第一個字母的方法，后續(xù)的篩選將要依賴之前猜詞的結(jié)果來進行，filter方法在遞歸中會被重復(fù)調(diào)用，之前猜詞的結(jié)果會作為參數(shù)傳入。

如果上一次猜對，那么返回的信息大概會長這樣：

javascriptword: **t**u*

這顯然是一種模式，可以將它轉(zhuǎn)化為正則去篩選候選數(shù)組，我又實現(xiàn)了一個將此類字符串轉(zhuǎn)化為正則的方法：

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;
        }
    }
    // 修正結(jié)尾的星號
    patternStr = patternStr + (starNum ? "w{" + starNum + "}" : "");
    return new RegExp(patternStr, "i");
}

得到正則后，用這個正則去過濾一下wordsMatchLength數(shù)組，刪掉不匹配的單詞：

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

如果上一次猜錯了呢，那么上一次猜了哪個字母，就說明正確的單詞中不應(yīng)該包含它，那么遍歷一下wordsMatchLength數(shù)組，凡是包含這個字母的單詞通通干掉：

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--;
    }
}

過濾工作完成后，要做的就是再統(tǒng)計一次字母頻率，選擇最常出現(xiàn)的那個即可。

另外，還需要做一些修正工作，來應(yīng)對所猜單詞過于偏門，沒有出現(xiàn)在單詞庫中的情況，準備一個備用數(shù)組，里面的單詞順序按照一般情況下字母的出現(xiàn)頻率排列，一旦單詞庫被過濾完，就去遍歷這個數(shù)組，選出頻率最高，而之前還沒有猜過的字母并返回。這時候就看運氣了。

同時也要記住在沒猜完一個單詞后要把候選數(shù)組清空，紀錄猜錯次數(shù)和已猜過字母的變量也要復(fù)原，不要影響后面的計算。
優(yōu)化
以上方法還有一些優(yōu)化的空間：

統(tǒng)計字母出現(xiàn)頻率的時候，同一個單詞中的同一個字母，不論出現(xiàn)幾次都只算一次，比如 e 或 s 這樣的字母，在一個單詞中可能出現(xiàn)很多次，但是沒有必要重復(fù)計數(shù)。

當候選數(shù)組被過濾完時，可以不用備用數(shù)組，切換為用戶手動輸入，這樣可以利用用戶英語構(gòu)詞法的知識進行有目的的猜測，但這種方法偏離了全自動程序的初衷。

最后就要借助對構(gòu)詞法的科學計算進行優(yōu)化了，這種計算需要專業(yè)知識的支撐，普通開發(fā)者無法勝任。

最后附上完整的源碼實現(xiàn)：
源碼

GPU云服務(wù)器云服務(wù)器背單詞小程序c語言支持node.js的云服務(wù)器 js做一個猜數(shù)字的 linux常用的單詞

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/85650.html

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

下一篇：關(guān)于單位轉(zhuǎn)換問題（M, G, TB, PB)

相關(guān)文章

如何利用Python寫猜數(shù)字和字母的游戲

　　Python作為一門常見的編程語言，可以用到的地方是比較的多的，而且他還能夠去編程相關(guān)的游戲，那么，下文就會給大家教一個比較簡單的小游戲，就是寫猜數(shù)字和字母的游戲，詳細的內(nèi)容可以看下文，看完之后，可以自己去手動敲下代碼哦?！　∏把浴　W完語法和正在學習語法的時候，我們可以在空閑的時候，寫幾個簡單的小項目，今天我們就用最基礎(chǔ)的語法看兩個實戰(zhàn)語法練習　　猜數(shù)字游戲　　項目游戲說明：讓用戶輸入一個數(shù)...

89542767 2022-11-10 15:31 評論0 收藏0

[零基礎(chǔ)學python]用while來循環(huán)

摘要：我在這里將他寫的程序恭錄于此，單元李航同學不要見怪，如果李航同學認為此舉侵犯了自己的知識產(chǎn)權(quán)，可以告知我，我馬上撤下此代碼。我用的是，在輸入指令上區(qū)別于李同學程序用變量接收了輸入的內(nèi)容。 while，翻譯成中文是當...的時候，這個單詞在英語中，常常用來做為時間狀語，while ... someone do somthing，這種類型的說法是有的。在python中，它也有這個含義，不過...

Tony 2019-07-24 17:37 評論0 收藏0

Vue.js新手入門指南[轉(zhuǎn)載]

摘要：就是一個用于搭建類似于網(wǎng)頁版知乎這種表單項繁多，且內(nèi)容需要根據(jù)用戶的操作進行修改的網(wǎng)頁版應(yīng)用。單頁應(yīng)用程序顧名思義，單頁應(yīng)用一般指的就是一個頁面就是應(yīng)用，當然也可以是一個子應(yīng)用，比如說知乎的一個頁面就可以視為一個子應(yīng)用。最近在逛各大網(wǎng)站，論壇，以及像SegmentFault等編程問答社區(qū)，發(fā)現(xiàn)Vue.js異常火爆，重復(fù)性的提問和內(nèi)容也很多，樓主自己也趁著這個大前端的熱潮，著手學習了一...

MartinHan 2019-08-23 11:50 評論0 收藏0

這事要從node node.js說起

導(dǎo)讀：興許所有程序員都有命名困難癥，在考慮變量、常量、方法、類、文件等命名時，總會千方百計嘗試一些語義化的方式去實現(xiàn)。曾經(jīng)有那么一段時間，一些node初學的同學遇到了同樣的問題：Hello World 跑不動！原文首發(fā)于個人博客：這事要從node node.js說起 0. 謎之 Hello World 問題的起源非常簡單，當我們在編寫一個入門程序時，就會迅速想起那句膾炙人口的語句： conso...

Acceml 2019-08-20 18:58 評論0 收藏0

發(fā)表評論

登陸后可評論

0條評論

aaron

男|高級講師

我要關(guān)注我要私信

TA的文章
閱讀更多

#開學季#無憂云：4核/4G/80G/5Mbps不限流量/洛陽BGP/月付59元，帶5G防御

閱讀 3891·2021-09-10 11:22

Pillow 10行代碼給營業(yè)執(zhí)照模板寫數(shù)據(jù)，批量生產(chǎn)

閱讀 2365·2021-09-03 10:30

記：原樣輸出文字，不做任何處理

閱讀 3677·2019-08-30 15:55

如何在React中優(yōu)雅的處理doubleClick

閱讀 1921·2019-08-30 15:44

怎樣分析頁面加載慢

閱讀 855·2019-08-30 15:44

純css三角形及其應(yīng)用

閱讀 603·2019-08-30 14:04

vue中的適配：px2rem

閱讀 3056·2019-08-29 17:18

swiper的使用

閱讀 1278·2019-08-29 15:04

最新活動

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Node.js 自動猜單詞程序的實現(xiàn)

相關(guān)文章

如何利用Python寫猜數(shù)字和字母的游戲

[零基礎(chǔ)學python]用while來循環(huán)

Vue.js新手入門指南[轉(zhuǎn)載]

**這事要從node node.js說起**

發(fā)表評論

0條評論

aaron

男|高級講師

TA的文章

#開學季#無憂云：4核/4G/80G/5Mbps不限流量/洛陽BGP/月付59元，帶5G防御

Pillow 10行代碼給營業(yè)執(zhí)照模板寫數(shù)據(jù)，批量生產(chǎn)

記：原樣輸出文字，不做任何處理

如何在React中優(yōu)雅的處理doubleClick

怎樣分析頁面加載慢

純css三角形及其應(yīng)用

vue中的適配：px2rem

swiper的使用

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Node.js 自動猜單詞程序的實現(xiàn)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！