猜数字游戏

guess.js

/*
有一个猜数字游戏，庄家预先写下一个四位数字（每位数字各不相同），玩家每次随机猜一个数字，庄家告知玩家猜对了几A几B（A代表数字和位置都相同，B代表包含该数字但位置不同，比如如果庄家写的是3514，玩家猜的是3165，庄家会回答1A2B），玩家继续猜，直到猜中为止。如果超过5轮没猜中，则玩家输，否则玩家赢。
请为玩家设计一个猜数字的算法，确保玩家能够大概率胜。
*/


// 返回数字和位置都相同的个数
const calcStrictIdentical = (target, input) => {
    let count = 0;

    for (let i = 0; i <= target.length - 1; ++i) {
        if (target[i] === input[i]) {
            count++;
        }
    }

    return count;
}

// 返回包含该数字但位置不同的个数
const calcLooseIdentical = (target, input) => {
    let count = 0;

    for (let i = 0; i <= target.length - 1; ++i) {
        if (input.includes(target[i]) && input[i] !== target[i]) {
            count++;
        }
    }

    return count;
}

// 返回两组数字之间的差异
const calcDiff = (target, input) => {
    const a = calcStrictIdentical(target, input);
    const b = calcLooseIdentical(target, input);

    return `${a}A${b}B`;
}

// 用0补全字符串的以保证长度
const padding = (value, count) => {
    const countNeedFilled = count - value.length;
    const array = new Array(countNeedFilled);

    array.fill('0');

    return array.join('') + value;
}

// 检查字符串里的字符没有重复
const checkUnique = (string) => {
    return string.length === [...new Set([...string])].length;
}

// 生成包含4个数字（数字各不相同）的字符串所组成的合集
const generateRecords = () => {
    const records = new Set();

    let index = 9999;

    while(index) {
        let record = index.toString();

        record = padding(record, 4);

        if (checkUnique(record)) {
            records.add(record);
        }

        // 剪枝
        if (index < 100) {
            break;
        }

        index--;
    }

    return records;
}

// 根据反馈，比对差异值，过滤合集中不可能为正确答案的记录
const filterRecords = (records, diff, guessedValue) => {
    records.delete(guessedValue);

    records.forEach(function(record) {
        const recordDiffResult = calcDiff(record, guessedValue);

        if (recordDiffResult !== diff) {
            records.delete(record);
        }
    });
};


// 在合集里随机挑选一条记录
const pickRecord = (records) => {
    const size = records.size;
    const array = [...records];

    const index = Math.floor(Math.random() * size);

    return array[index];
}



/**
 * 返回猜测的值
 * @param {string} input 输入值
 */
const guess = (input) => {
    const records = generateRecords();
    let roundCount = 1;
    let success;
    let guessedValue;

    do {
        guessedValue = pickRecord(records);
        success = guessedValue === input;
        console.log('Round', roundCount);

        roundCount++;

        if (!success) {
            const diff = calcDiff(input, guessedValue);
            filterRecords(records, diff, guessedValue);
        }
    } while(!success)

    return guessedValue;
}


const main = () => {
    let input = '1934';

    if (process.argv.length === 3) {
        input = process.argv.slice(-1)[0];
    }

    if (input.length !== 4 || !checkUnique(input)) {
        console.error('Ileagal input')
        return;
    }

    console.log('The input is', input);
    const guessedValue = guess(input);
    console.log('The answer is', guessedValue);
}

main();