0%

猜数字游戏算法

发表于

题目

有猜数字游戏如下

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

例如：庄家写下9876，玩家第一次猜0123，庄家回复0A0B；玩家继续猜4567，庄家恢复0A2B；依次下去，知道玩家猜中9876为止。

一道很有意思的题目，网上搜索下，发现有很多解法，主流两种

  1. 筛选法
  2. 信息熵法

筛选法

筛选法原理很简单，首先我们需要知道庄家所有可能结果的集合

1
10*9*8*7 === 5040  // 总共有5040个可能结果

然后，玩家猜一个数字，和庄家数字对比后得到一个反馈结果某A某B

这时候，我们把所有5040个可能的结果和玩家数字对比，再从中过滤出和某A某B一样反馈的结果集，那么这个结果集中一定包含了庄家数字，这就是一次过滤，排除很多无关的数据。

然后在第一次过滤出来的结果集中随机取一个数字，用这个数字和庄家对比进行第二次猜测，用上面的方法在上一次的过滤结果中再次过滤，得到第二次过滤结果。

循环过滤，最后只剩一个结果。

算法代码

首先是得到所有可能数字的集合，本质上是0-9999之间每位不重复的数字集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let data = [] // 集合数据

for (let i = 0; i < 9999; i++) {
    let str
    if (i <= 999) {
        str = '0' + i // 例子： 0987 这种特殊情况
    } else {
        str = '' + i
    }
    const arr = str.split('')
    if (new Set(arr).size !== 4) continue // 判断size === 4，表示没有重复数字
    data.push(arr)
}

console.log(data) // [...]

两串数字对比并得到反馈的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function analyse(basicArr, compareArr) {
    let count = 0
    basicArr.forEach((value, index) => {
        if (value == compareArr[index]) {
            count++
        }
    })
    const A = count
    const B = (compareArr.length + basicArr.length) - new Set([...basicArr, ...compareArr]).size - A
    return `A${A}B${B}`
}

console.log(
    analyse([1,2,3,4], [0,2,4,7])  // A1B1
)

过滤函数那部分就简单了，略。

整体代码如下，大概率在第五次过滤就只有一个结果存在了，少部分在5次前就出来了，部分需要更多次过滤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 这个函数用于分析两个数组之间的反馈
function analyse(basicArr, compareArr) {
    let count = 0
    basicArr.forEach((value, index) => {
        if (value == compareArr[index]) {
            count++
        }
    })
    const A = count
    const B = (compareArr.length + basicArr.length) - new Set([...basicArr, ...compareArr]).size - A
    return `A${A}B${B}`
}

// 默认以结果集第一个数据为猜测值, 最后根据猜测反馈的值过滤出所有符合反馈的数据
function filter(preResult) {
    const guess = preResult[0]
    const re = analyse(store, guess)
    const filterResult = preResult.filter(arr => {
        if (analyse(guess, arr) == re) {
            return true
        }
    })
    return filterResult
}

// 开始
let data = []

// 以下for循环用来将符合猜规则的数据存放到data变量
for (let i = 0; i < 9999; i++) {
    let str
    if (i <= 999) {
        str = '0' + i
    } else {
        str = '' + i
    }
    const arr = str.split('')
    if (new Set(arr).size !== 4) continue
    data.push(arr)
}

// 随机生成庄家数组
const store = data[Math.ceil(Math.random() * data.length) - 1]

console.log('庄家数据: ', store)

// 以下每一次filter包含一次猜测,返回可能的结果集,在结果集中重复过滤,大概率会在第五次猜测后得到唯一的数据, 第六次概率更高
const filterResult1 = filter(data)
const filterResult2 = filter(filterResult1)
const filterResult3 = filter(filterResult2)
const filterResult4 = filter(filterResult3)
const filterResult5 = filter(filterResult4)

console.log(filterResult5)

信息熵法

待以后有空补充