(技术分析)没有重复数字4位数的个数思路分析

(技术分析)没有重复数字4位数的个数思路分析

前言

上篇文章的内容是猜数字(Bulls and Cows)游戏的提示如何生成,这篇文章考虑另一个问题:如何设计猜数字游戏策略,使得对任意目标数字,都可以用较少的次数猜到。

这篇文章考虑的情形比上篇文章简单,目标数字一定是没有重复数字的 4 位数。

猜数字游戏规则

猜数字(Bulls and Cows)游戏由两个人玩,一方出数字,一方猜数字。

出数字的人想一个没有重复数字的 4 位数(最高位可以是 0),称为目标数字,猜数字的人每次猜一个 4 位数,猜的数同样不能有重复数字。每次猜数字之后,出数字的人需要给出形式为 "xAyB" 的提示,其中 x 和 y 分别表示「公牛」和「奶牛」的数量,「公牛」表示数字和位置都正确,「奶牛」表示数字正确但位置错误。如果猜数字的人得到的提示是 "4A0B",则猜到目标数字。

猜题游戏 猜智商_疯狂猜歌六字英文数字_猜数字游戏设计

猜数字游戏通常有次数限制猜数字游戏设计,猜数字的人在规定次数内猜到目标数字为胜利,否则为失败。常用的次数限制为 10 次,得到提示 "4A0B" 的一次猜数字也计入次数。

思路分析

没有重复数字 4 位数的个数是 A(10, 4)= 5040。如果直接遍历所有可能的没有重复数字 4 位数,则最坏情况下需要猜 5040 次才能猜到目标数字,显然不是好的策略。

其实,每次猜数字之后,可以根据得到的提示知道哪些数字可能是目标数字,哪些数字不可能是目标数字,从而缩小猜数字的范围。例如,猜数字 1024 得到的提示是 "1A2B",则 2048 可能是目标数字,4096 不可能是目标数字。

猜题游戏 猜智商_猜数字游戏设计_疯狂猜歌六字英文数字

假设猜的数字是 guess,可能的目标数字是 candidate(下文称为「候选目标数字」),则一定满足以下两个条件。

猜的数字 guess 中的每个「公牛」数字对应的候选目标数字 candidate 中的相同位置的数字一定相同,猜的数字 guess 中的每个非「公牛」数字对应的候选目标数字 candidate 中的相同位置的数字一定不同,因此 guess 和 candidate 的相同位置的数字相同的个数一定等于「公牛」的数量。

猜的数字 guess 中的每个正确数字(包括「公牛」和「奶牛」)一定在候选目标数字 candidate 中出现,猜的数字 guess 中的每个错误数字(既不是「公牛」也不是「奶牛」)一定不在候选目标数字 candidate 中出现,因此 guess 和 candidate 的公共数字(不考虑位置是否相同)的个数一定等于正确数字的个数(即「公牛」和「奶牛」的数量之和)。

第 2 个条件同时包含「公牛」和「奶牛」的数量,根据第 1 个条件,可以将「公牛」的数量减去,因此第 2 个条件等价于 guess 和 candidate 的位置不同的公共数字的个数一定等于「奶牛」的数量。

猜数字游戏设计_猜题游戏 猜智商_疯狂猜歌六字英文数字

由于同时满足上述两个条件的数字的数量是有限的,因此在每次猜数字之后,都可以排除大部分数字,留下小部分候选目标数字,从而减少猜数字的次数。

根据上述分析可知,在第一次猜数字之后,不同的提示对应的可能的目标数字的数量如下:

如果得到 "4A0B" 的提示,则已经猜到目标数字。

"3A1B" 的提示不可能出现,因为此时 4 个数字都是正确的数字猜数字游戏设计3D交通工具,在 3 个数字的位置正确的情况下,剩下的 1 个数字的位置也一定正确,不可能只有 1 个数字的位置错误。

猜题游戏 猜智商_疯狂猜歌六字英文数字_猜数字游戏设计

对于任意目标数字,在第一次猜数字之后,都可以将候选目标数字的数量减少到不超过 1440 个程序开发,因此可以显著减少猜数字的次数。每次猜数字之后都可以得到一个候选目标数字的集合,下一次猜数字时在该集合中任选一个数字并继续缩小猜数字的范围,直到猜到目标数字。

根据上述策略,猜到目标数字最多需要 9 次,平均需要 5.5 次。

实现实现说明

实现包括三个类:Master、BullsAndCows 和 TestBullsAndCows。

疯狂猜歌六字英文数字_猜题游戏 猜智商_猜数字游戏设计

Master 类的功能是交互,包含一个私有的目标数字 secret 和一个公共的方法 guess,从外部无法直接访问目标数字,只能通过调用方法得到提示。

BullsAndCows 类的功能是实现猜数字策略,包含一个公共的方法 guessSecret,该方法的参数是 Master 类的一个实例,通过和该实例交互猜到目标数字。

TestBullsAndCows 类的功能是测试,根据特定的没有重复数字的 4 位数创建 Master 类的实例并创建 BullsAndCows 类的实例进行测试。为了统计猜到目标数字的次数,测试时考虑所有的没有重复数字的 4 位数。

代码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

class Master {
    public static final int LENGTH = 4;
    private String secret;

    public Master(String secret) {
        this.secret = secret;
    }

    public String guess(String number) {
        int bulls = 0, cows = 0;
        int[] digits = new int[10];
        for (int i = 0; i < LENGTH; i++) {
            int secretDigit = secret.charAt(i) - '0';
            int guessDigit = number.charAt(i) - '0';
            if (secretDigit == guessDigit) {
                bulls++;
            } else {
                if (digits[secretDigit] < 0) {
                    cows++;
                }
                if (digits[guessDigit] > 0) {
                    cows++;
                }
                digits[secretDigit]++;
                digits[guessDigit]--;
            }
        }
        return String.format("%dA%dB", bulls, cows);
    }
}

class BullsAndCows {
    private static Set secretSet;
    private int turns;

    public BullsAndCows() {
        if (secretSet == null) {
            secretSet = new HashSet();
            for (int i = 0; i < 10000; i++) {
                String secret = String.format("d", i);
                if (allDifferent(secret)) {
                    secretSet.add(secret);
                }
            }
        }
        turns = 0;
    }

    public String guessSecret(Master master) throws Exception {
        Set possibleSet = new HashSet(secretSet);
        int bulls = 0, cows = 0;
        while (bulls < Master.LENGTH) {
            Iterator iterator = possibleSet.iterator();
            String number = iterator.next();
            String hint = master.guess(number);
            turns++;
            bulls = hint.charAt(0) - '0';
            cows = hint.charAt(2) - '0';
            if (bulls == Master.LENGTH) {
                return number;
            }
            iterator.remove();
            while (iterator.hasNext()) {
                String candidate = iterator.next();
                if (!isPossible(number, candidate, bulls, cows)) {
                    iterator.remove();
                }
            }
        }
        throw new Exception("Secret not found!");
    }

    public int getTurns() {
        return turns;
    }

    private static boolean allDifferent(String secret) {
        boolean[] exists = new boolean[10];
        for (int i = 0; i < Master.LENGTH; i++) {
            int digit = secret.charAt(i) - '0';
            if (exists[digit]) {
                return false;
            }
            exists[digit] = true;
        }
        return true;
    }

    private static boolean isPossible(String guess, String candidate, int bulls, int cows) {
        int actualBulls = 0;
        int actualCows = 0;
        boolean[] exists = new boolean[10];
        for (int i = 0; i < Master.LENGTH; i++) {
            int digit = guess.charAt(i) - '0';
            exists[digit] = true;
        }
        for (int i = 0; i < Master.LENGTH; i++) {
            if (candidate.charAt(i) == guess.charAt(i)) {
                actualBulls++;
            } else {
                int digit = candidate.charAt(i) - '0';
                if (exists[digit]) {
                    actualCows++;
                }
            }
        }
        if (bulls != actualBulls || cows != actualCows) {
            return false;
        }
        return true;
    }
}

public class TestBullsAndCows {
    private static int maxTurns = 0;
    private static int minTurns = Integer.MAX_VALUE;
    private static int sumTurns = 0;

    public static void main(String[] args) {
        List secretList = new ArrayList();
        for (int i = 0; i < 10000; i++) {
            String secret = String.format("d", i);
            if (allDifferent(secret)) {
                secretList.add(secret);
            }
        }
        int size = secretList.size();
        for (int i = 0; i < size; i++) {
            testGuess(secretList, i);
        }
        System.out.println("Maximum turns: " + maxTurns);
        System.out.println("Minimum turns: " + minTurns);
        double meanTurns = 1.0 * sumTurns / size;
        System.out.println("Mean turns: " + meanTurns);
    }

    private static boolean allDifferent(String secret) {
        boolean[] exists = new boolean[10];
        for (int i = 0; i < Master.LENGTH; i++) {
            int digit = secret.charAt(i) - '0';
            if (exists[digit]) {
                return false;
            }
            exists[digit] = true;
        }
        return true;
    }

    private static void testGuess(List secretList, int index) {
        Master master = new Master(secretList.get(index));
        BullsAndCows obj = new BullsAndCows();
        try {
            String secret = obj.guessSecret(master);
            System.out.println("Expected secret: " + secretList.get(index));
            System.out.println("Guessed secret: " + secret);
            System.out.println("Used turns: " + obj.getTurns());
            maxTurns = Math.max(maxTurns, obj.getTurns());
            minTurns = Math.min(minTurns, obj.getTurns());
            sumTurns += obj.getTurns();
        } catch (Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
}

结语

这篇文章使用的策略是简单策略,猜到目标数字最多需要 9 次,平均需要 5.5 次。除了简单策略以外,还有启发式策略和最优策略,在最多次数和平均次数方面都优于简单策略,感兴趣的读者可以自行尝试。

文章来源:http://mp.weixin.qq.com/s?src=11×tamp=1682100845&ver=4482&signature=mcpy2aEU8zwi8QqGeH3HvU1cmXmJJOi0Vz1QunS323u2oMRFzs9LTNX83CTeCp7ad1kvcClVlP6VLDFRAWx0omdS2MYiUrXSuCqCFfKCZaSc26ubUjz1BwZXxQoBOrwd&new=1