美文网首页
Shut the box

Shut the box

作者: 尚无花名 | 来源:发表于2019-03-23 12:46 被阅读0次

    这是一道网传某民宿公司的面试题。
    面试出这种题我也是醉了,有意思吗?我把它帖在这里,只是希望你们尽量ban掉这道题
    当然题目本身还是挺有意思的。
    这题是有概率的游戏问题。
    可以网上搜一下shut the box怎么玩
    这里假设是一个人玩,每次掷两个骰子, 要把数字1-9消掉。消掉算你赢,消不掉算你输。
    假设掷了一个 7, 7可以用1,6 , 也可以用3,4,也可以直接用7。具体用哪种要算一下取了哪种之后胜率最高
    这里dp[state][i], 表示当我还剩state里包含的数字时我掷出了 “i” 这个数时的胜率。
    枚举各种情况, 取使下一步胜率最大的那一支。
    具体实现的时候由于很多状态变不是合法的根本没必要算。
    所以没使用DP来做,使用了从大到小的recursion with memorization。 这样不必要的状态就不用算一遍了
    初始化的时候先算好所以情况下应该怎么办存下来,具体游戏玩到哪一步的时候就直接查表就可以了。
    一个文献如下 http://www.durangobill.com/ShutTheBox.html
    经测试下面这个程序的1千万次的胜率7.147%,和文献中的期望值完美match上

    这里面容易出现的bug。
    我们的数字是从1到9的,可是计算机里的数字是从 0开始的。这面有一个 1 的offset。这样,如果state是 0 或者state是 1,都是成功的状态 , 因为第0位的状态没有意义。
    这题真的很容易写错。 我第二次写的时候也debug了好久。

    代码见下。

    import java.util.*;
    public class ShutTheBox {
        int STATE; // using bit to represent which bits are available
        Double[][] probability; // memorization
        double[] numberProb; // from 2 to 12, the probability of each number
        List[][] combinations;
        // recursion with memorization
        public ShutTheBox(){
            STATE = 0;
            for (int i = 1; i <= 9; i++) {
                STATE += (1 << i);
            }
    
            probability = new Double[STATE + 1][13]; // only 2 to 12 is meaningful
            combinations = new List[STATE + 1][13];
            numberProb = calNumberProb();
            for (int c = 2; c <= 12; c++ ) dfs(STATE, c, probability);
        }
    
        private double dfs(int curState, int c, Double[][] probablity) {
            // recursion with memorization
            if (probablity[curState][c] != null) return probablity[curState][c];
            //base case;
            if (curState == 0) {
                probablity[curState][c] = 1.0;
                return 1.0;
            }
    
            // find combinations that can construct c from state
            // c is the number from rolling the dice
            List<List<Integer>> combs = findComb(curState, c);
            if (combs.size() == 0) {
                probablity[curState][c] = 0.0;
                return 0.0;
            }
            double bestProb = 0.0;
            for (List<Integer> comb : combs) {
                int nextState = getNextState(curState, comb);
                double localProb = 0.0;
                for (int nc = 2; nc <= 12; nc++) {
                    localProb += numberProb[nc] * dfs(nextState, nc, probablity);
                }
                if (localProb > bestProb) {
                    bestProb = localProb;
                    combinations[curState][c] = comb;
                }
            }
            probablity[curState][c] = bestProb;
            return bestProb;
        }
    
        private List<List<Integer>> findComb(int curState, int c) {
            List<Integer> choices = new ArrayList<>();
            for (int i = 1; i <= 9; i++) {
                if ((curState & (1 << i)) > 0) {
                    choices.add(i);
                }
            }
            List<List<Integer>> combinations = new ArrayList<>();
            findCombDfs(choices, c, 0, combinations, 0, new ArrayList<>());
            return combinations;
        }
    
        private void findCombDfs(List<Integer> choices, int c, 
                        int index, List<List<Integer>> combinations, 
                        int sum, List<Integer> list) {
            if (sum > c || c < 2) return;
            if (sum == c) {
                combinations.add(new ArrayList<>(list));
                return;
            }
            for (int i = index; i < choices.size(); i++) {
                if (sum + choices.get(i) <= c) {
                    list.add(choices.get(i));
                    findCombDfs(choices, c, i + 1, 
                                  combinations, sum + choices.get(i), list);
                    list.remove(list.size() - 1);
                }
            }
        }
    
        private int getNextState(int curState, List<Integer> comb) {
            for (int n : comb)  curState -= (1 << n);
            return curState;
        }
    
        public double[] calNumberProb() {
            double[] ans = new double[13];
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= 6; j++) {
                    ans[i + j] += 1.0 / 6.0 /6.0;
                }
            }
            return ans;
        }
    
        public List<Integer> pick(int curState, int c) {
            return combinations[curState][c];
        }
    
        /////// Test code
    
        public static Random random;
        public static int rollDice() {
            return random.nextInt(6) + random.nextInt(6) + 2;
        }
        public static void main(String[] args) {
            ShutTheBox stb = new ShutTheBox();
            random = new Random();
            int trialNumber = 10000;
            int cnt = 0;
            for (int i = 0; i < trialNumber; i++) {
                if (runOnce(stb)) cnt++;
            }
            System.out.println(cnt * 1.0 / trialNumber);
        }
    
        public static boolean runOnce(ShutTheBox stb) {
            int curState = stb.STATE;
            while (true) {
                int c = rollDice();
                List<Integer> comb = stb.pick(curState, c);
                if (comb == null || comb.size() == 0) {
                    return false;
                } else {
                    curState = stb.getNextState(curState, comb);
                    if (curState == 0) {
                        return true;
                    }
                }
            }
        }
    }
    
    

    我第二遍时代码,略有不同

    package oaPrepare.airbnb;
    
    import java.util.*;
    
    public class ShutTheBox {
        int[][] nextStates;
        Double[][] chanceToWin;
        double[] sumChance;
        public ShutTheBox() {
            // constructor
            //precompute and calculate the next step
            int nOfState = (1 << 10 ); // 1 -> 2, 2 -> 4
            nextStates = new int[nOfState][13]; // 1 to 13
            chanceToWin = new Double[nOfState][13];
            for (int r = 0; r < nOfState; r++) {
                for (int c = 0; c < 13; c++) {
                    nextStates[r][c] = -1; // -1 means never computed before
                    // -2 means computed and no good state
                }
            }
            sumChance = new double[13];
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= 6; j++) sumChance[i + j] += 1.0/36;
            }
    
            for (int diceSum = 2; diceSum <= 12; diceSum ++) {
                getBestChoice(nOfState - 1, diceSum);
            }
        }
        public List<Integer> pickCombination(int state, int diceSum) {
            if (nextStates[state][diceSum] == -2) return null;
            // if null: lost;
            return getDiff(state, nextStates[state][diceSum]);
        }
        private double getBestChoice(int state, int diceSum) {
            if (nextStates[state][diceSum] != -1) return chanceToWin[state][diceSum];
            // base case;
            if (state == 0 || state == 1) {
                chanceToWin[state][diceSum] = 1.0;
                nextStates[state][diceSum] = 0;
                return 1.0;
            }
            List<List<Integer>> choicesOfCombination = getChoicesOfCombination(state, diceSum);
    
            //among the choices, pick the best one
            // the one which have best expectation;
            double bestExpectation = 0.0;
            int  bestNextState = -2;
            for (List<Integer> comb : choicesOfCombination) {
                int nextState = getNextState(state, comb);
                double expectation = 0.0;
                for (int c = 2; c <= 12; c++) {
                     // recursive call
                    expectation += sumChance[c] * getBestChoice(nextState, c);
                }
                if (expectation >= bestExpectation) {
                    bestExpectation = expectation;
                    bestNextState = nextState;
                }
            }
            chanceToWin[state][diceSum] = bestExpectation;
            nextStates[state][diceSum] = bestNextState;
            return bestExpectation;
        }
    
        private List<List<Integer>> getChoicesOfCombination(int state, int diceSum) {
            List<Integer> nums = new ArrayList<>();
            for (int i = 1; i <= 9; i++) {
                if ((state & (1 << i)) != 0) nums.add(i);
            }
            List<List<Integer>> ans = new ArrayList<>();
            dfs(nums, ans, 0, diceSum, 0, new ArrayList<>());
            return ans;
        }
        private void dfs(List<Integer> nums, List<List<Integer>> ans, int index, int target, int curSum, List<Integer> path) {
            if (curSum > target) return;
            if (curSum == target) {
                ans.add(new ArrayList<>(path));
                return;
            }
            for (int j = index; j < nums.size(); j++) {
                path.add(nums.get(j));
                dfs(nums, ans, j + 1, target, curSum + nums.get(j), path);
                path.remove(path.size() - 1);
            }
        }
    
        private int getNextState(int state, List<Integer> comb) {
            for (int b : comb)  state -= (1 << b);
            return state;
        }
        private List<Integer> getDiff(int state, int nextState) {
            List<Integer> ans = new ArrayList<>();
            if (nextState == -2) return null;
            for (int i = 1; i <= 9; i++) {
                int mask = 1 << i;
                if ((mask & state) > 0 &&( (mask & nextState) == 0)) {
                    ans.add(i);
                }
            }
            return ans;
        }
    
        //Test
    
        public static Random random;
        public static int rollDice() {
            return random.nextInt(6) + random.nextInt(6) + 2;
        }
        public static void main(String[] args) {
            ShutTheBox stb = new ShutTheBox();
            random = new Random();
            int trialNumber = 10000000;
            int cnt = 0;
            for (int i = 0; i < trialNumber; i++) {
                if (runOnce(stb)) cnt++;
            }
            System.out.println(cnt * 1.0 / trialNumber);
        }
        public static void printState(int state) {
            List<Integer> ans = new ArrayList<>();
            for (int i = 1; i <= 9; i++) if ((state & (1 << i)) > 0) ans.add(i);
            System.out.println(ans);
        }
        public static boolean runOnce(ShutTheBox stb) {
            int curState = (1 << 10) - 1;
            //printState((1<< 10) - 1);
            while (true) {
                //System.out.println(curState);
                //printState(curState);
                int c = rollDice();
                List<Integer> comb = stb.pickCombination(curState, c);
                //System.out.println(c);
                //System.out.println(comb);
                if (comb == null || comb.size() == 0) {
                    return false;
                } else {
                    curState = stb.getNextState(curState, comb);
                    if (curState <= 1) {
                        return true;
                    }
                }
            }
        }
    }
    
    

    相关文章

      网友评论

          本文标题:Shut the box

          本文链接:https://www.haomeiwen.com/subject/ojxsvqtx.html