西西河

主题:【原创】用计算机求解一个儿时的游戏 -- Highway

共:💬39 🌺28
分页树展主题 · 全看首页 上页
/ 3
下页 末页
  • 家园 【原创】用计算机求解一个儿时的游戏

    昨天在河里瞎逛的时候,看看面壁网友的一个回帖

    哈,我也问个算法。。。,是在问一个算法的问题,问题是“前些天算两个7两个4(+-*/),怎么让它等于24,便想写个code: 任意给4个数,输出是否等于24,如果等于,给出怎么得到的结果。”

    看了这个问题,使我马上联想起小时候常玩的一个游戏。大概在二三年级的时候(注意不是大二大三大时候),常和小朋友们在一起用扑克牌玩一种心算游戏。一般是4个人玩(2个人也成),一开始每个人分一摞扑克牌。然后每轮一人出一张牌放在中间。这时候大家开始心算。谁第一个找到算法,这四张扑克牌就归谁。到最后谁手里的扑克牌最多,谁就是赢家。

    点看全图

    外链图片需谨慎,可能会被源头改

    那时候我们只会四则运算。所以规则很简单,就是四张扑克牌都要用到,但是每张牌只能用一次。不管是加减乘除怎么组合,能得到24就算赢。

    这个游戏是谁发明的我不知道,为什么选择24也从来没有问起。事实上这个游戏设计有问题,很多情况下大家想不出答案,只能把自己出的扑克牌收回,重新再来。

    那时候我们玩得时候,有大一些的孩子在旁边看我们玩(比如说谁的哥哥姐姐什么的)。有时候我们小孩子们想不出来,大孩子们可能会用一些“高级”的算法来解决问题,比如说用乘方,或是开根号什么的。

    问题是当我们大家都想不出来答案的时候,可能我们是对的,这4张扑克牌无解。也可能我们是错的,我们还没有穷尽所有的组合。现在计算机这么牛,能帮着解决一下这个问题嘛?我想这可能就是面壁朋友要问得那个问题。

    Highway不才,是吃计算机饭的。看到这个帖子后有些技痒。于是乎坐在那里开始发呆(所谓的思考)。想了好一阵子,基本路线大概有个眉目了以后,开始动手。手边正好有Java的IDE,于是决定用Java来写写看。

    写了一阵子,又测试了几个case,一个小游戏算是基本成形了。当然这个游戏只是Proof of concept类的演示,连个图形界面也没有(寒碜啊)。

    游戏是这样玩的:你在Dos Console上给出4个数字(1到13,代表A到K),然后一敲回车,计算机就开始寻

    找答案。找到的话,就在屏幕上给出答案(很多时候有多种解),找不到的话,就实话实说“Sorry, I can’t find one!”.

    点看全图

    外链图片需谨慎,可能会被源头改

    我现在的这个小游戏很粗糙,很多地方都不是很合理,比如说计算机给出的多种答案其实是一回事。因为有些括号是多余的,A+B-C+D和B+A+D-C也只是交换了一些顺序而已。我现在的算法不具备甄别这些的能力。

    我的游戏算法大概是这样的:

    1) 任意给四个1-13之间的数字

    2) 求出所有的排列来。4个数字的组合上限是24,如果数字有重复,排列自然就会减少,这样可以减少一些计算。

    3) 把加减乘除运算符加进去,列出所有可能的计算表达式(优先级也要考虑)

    4) 对每个表达式进行求解,如果是24,那么这个表达式就是一个答案。

    从计算机程序的角度来讲,我现在这个程序不太合格,有几个地方是hard-coded(优先级算法上有些投机取巧)。对加减法和乘法的交换率视而不见(及A+B = B+A, A*B=B*A),造成很多重复的计算。如果有人出钱让我把这小游戏写成一个产品的话,那么正儿八经程序应该是这样的。

    1) 允许扑克牌张数为1-N, 求解的答案可以是24,也可以是任何整数。用户可以自己制定游戏规则。

    2) 算法可以是简单的加减乘除,也可以是更广义上的所有binary运算,比如说取余数,乘方,或者是计算机上常用的shift(<< >> >>>)等等。用户可以自由选择定制。

    3) 加上美观的界面。如果用户解除了一个有难度的题目后,一定要有养眼的MM(切切)弹出。如果一个非常简单的题目也做不出来的话,可以适当的嘲笑羞辱一下(嘿嘿

    如果把这些情况都想到了,那么穷尽法可能性能上就会有些问题,比如说是玩8张牌,允许复杂算法的大游戏,那么组合很可能就会上亿。如果是玩20张牌的超大游戏,你计算机 可能3天也算不出来)。那么这时候算法就要优化,要有些智能,及早排除那些“压根就没谱”的表达式。据说当初深蓝大战国际象棋大师的时候,就有些“投机”。当卡斯帕罗夫走出一步棋的时候,深蓝会利用“常识”首先排除一些荒唐的走法,同时利用卡斯帕罗夫历史上胜负的记录优先选择一些方案。当然即使是这抄近道儿,要估算出十几步以后的情况,出现的组合数量还是触目惊心的,计算机之大非深蓝这种超级计算机才可能完成。

    好了,就说到这里吧!

    关键词(Tags): #Java#Game#Poke
    • 家园 我来提个简单的问题,4张牌算不出的第一个正整数是几

      先算出来的砸花

      • 家园 根据我暴力破解

        4张牌算不了的最小整数是1114

        • 家园 比较相信这个数,位于1101到1127之间

          送花

        • 家园 自己删了一贴
        • 家园 【原创】我的想法,并请版主转科学探索版

          这个问题我的想法如下:

          首先我门可以排除"-"和"/"的运算。为什么可以排除?因为显然可以排除。:D。因为凡是通过"*","+"运算得不到的结果"-"和"/"一定得不到,具体的原因我暂时整理不出头绪来。

          先考虑两个数的情况。A(+*)B,(A,B 是1到13区间的正整数,以下CDEF类同)能得到2到26的连续区间和27到169的离散整数。最小的两个数不能生成的数是29。

          考虑三个数的情况。A(+*)B(+*)C。因为多了C,所以上述两个数不可以生成的27到169的区间类的离散整数全被填满。(因为容易证明A*B-C*D<13)三个数可以生成2到182(169+13)的连续区间和183到2197的离散整数。

          其中182等于13*13+13,是型如A*B+C的最大数。328=13*(13+13)是型如A*(B+C)的最大数。并且显然在小于328+13=341的离散整数区间里,间隔不小于13。意既小于341的数总可以写成A*(B+C)+D。

          大于等于342的数字必然只能写成A*B*C的形式。

          问题归结为找到342到2197区间离散整数间隔大于13的最早出现的区间。

          好了要找到这个区间,就要找数学专业人士了。不过相信暴力破解的正确性。1114=11*10*10+14,花一个。

          具体1114如何来的,请版主转科学探索版,看看大洋芋的解答吧

      • 家园 题意理解错了,删...
    • 家园 是不是算法有疏漏?

      从你的黑颜色截图来看,用7,7,4,4无法算出24。但其实用四则运算是可以用它们算出来的,算法如下:

      7*(4-4/7)=24

    • 家园 我还以为这事只有我做过...

      我当初计算出了优先级,记得好像是用了一个排序然后比较

      不过只停留在了四张牌的上面,汗水

    • 家园 can you...

      can you give me your code in java here?

      • 家园 Here yo go...

        这是我的第一个Version(quick and dirty version)。这个版本想法很简单,是直接针对这个游戏的,算法不优化,也不够generic,虽然可以很容易的增减运算符,改变24预定值为其他数字,但是不能够增加或是减少扑克牌的数量(比如说玩5张牌,或是6张牌)。另外这个算法是先给出String表达式,然后再进行数值计算,涉及到了Math expression parse的问题。我偷懒,从网上下载了一个jar来完成这个工作。

        今天我新写了一个version,解决了上述问题。新算法不做String parse,不需要那么第三方parser。从效率上讲,性能提高了11倍左右(原先穷尽所有4张扑克组合要7分半钟,新算法只要40秒左右)。另外,玩5张,6张牌的游戏一定问题也没有,我基本比较满意。

        你先看看这个quick-and-dirty version,消化了再说下一步。

        package game;
        
        import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.HashSet;
        import java.util.Set;
        
        import org.nfunk.jep.JEP;
        
        import util.PermutationGenerator;
        
        public class CalcPokeGame 
        {
          private static final String[] OPERATOR = new String[]{"+", "-", "*", "/"};
          private static final double   SMALL  = 0.0000001d;
          private static final int    POKE_NUM = 4;
          
          private static final String[] PATTERNS = new String[]{
            "((A OP1 B) OP2 C) OP3 D", 
            "(A OP1 (B OP2 C)) OP3 D",
            "(A OP1 B) OP2 (C OP3 D)",
              "A OP1 ((B OP2 C) OP3 D)",
            "A OP1 (B OP2 (C OP3 D))",
            "(C OP3 D) OP2 (A OP1 B)" };
            
          public CalcPokeGame()
          {    
          }
          
          /**
           * Given 4 numbers and find out the solution/solutions
           * @param nums
           */
          public Set<String> playGame(int[] nums)
          {
            Set<String> solution = new HashSet<String>();
            if(nums.length != POKE_NUM)
            {
              System.err.println("Invalid input. Only allows" +  POKE_NUM + " numbers array");
              return solution;
            }
            for(int i=0; i<nums.length; i++)
            {
              if(nums[i]<1 || nums[i]>13)
              {
                System.out.println("Invalid number: " + nums[i] + ". It must be between 1 and 13.");
                return solution;
              }
            }
            PermutationGenerator x = new PermutationGenerator(nums.length);
            Set<int[]> permutations = x.getAllPermutations(nums);
            permutations = x.removeDuplication(permutations);
            
            for(int[] perm : permutations)
            {
              solution.addAll(this.checkOneSet(perm));
            }
            return solution;
          }
          
          /**
           * For a given int array, try out all the calcuation combinations
           * @param nums
           * @return
           */
          private Set<String> checkOneSet(int[] nums)
          {
            Set<String> totalCombo = new HashSet<String>();
            for(String str : PATTERNS)
            {
              totalCombo.addAll(this.getAllCombos(nums, str));
            }
            Set<String> rightCombos = this.getCorrectCombo(totalCombo);
            return rightCombos;
          }
          
          /**
           * Create all possible expressions here. 
           * Three layer of loop is tailored for game rule.
           * @param nums
           * @param GivenPattern
           * @return
           */
          private Set<String> getAllCombos(int[] nums, String GivenPattern)
          {
            String pattern = GivenPattern;
            pattern = pattern.replace("A", Integer.toString(nums[0]));
            pattern = pattern.replace("B", Integer.toString(nums[1]));
            pattern = pattern.replace("C", Integer.toString(nums[2]));
            pattern = pattern.replace("D", Integer.toString(nums[3]));
            
            Set<String> allCombos = new HashSet<String>();
                
            for(int i=0; i<OPERATOR.length; i++)
            {
              String step1 = pattern.replace("OP1", OPERATOR[i]);
              for(int j=0; j<OPERATOR.length; j++)
              {
                String step2 = step1.replace("OP2", OPERATOR[j]);
                for(int k=0; k<OPERATOR.length; k++)
                {
                  String step3 = step2.replace("OP3", OPERATOR[k]);
                  allCombos.add(step3);
                }
              }
            }
            return allCombos;
          }
          
          /**
           * Get expressions which yields expected result
           * @param allCombos
           * @return
           */
          private Set<String> getCorrectCombo(Set<String> allCombos)
          {
            Set<String> result = new HashSet<String>();
            for(String exp: allCombos)
            {
              double d = this.calcExpression(exp);
              if(Math.abs(d-24.0)<SMALL)
              {
                result.add(exp);
              }
            }
            return result;
          }
          
          /**
           * Do the real math calculation here
           * @param exp
           * @return
           */
          private double calcExpression(String exp) 
          {
            JEP calc = new JEP();
            calc.parseExpression(exp);
            return calc.getValue();
          }
          
          /**
           * Main entry of the program
           * @param args
           * @throws IOException
           */
          public static void main(String[] args) throws IOException
          {
            CalcPokeGame game = new CalcPokeGame();
            String line = null;
            while(true)
            {
              System.out.println("\nPlease input 4 numbers here, like \"7, 8, 11, 9\"");
              BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
              line = in.readLine();
              if(line.equalsIgnoreCase("Quit"))
              {
                System.out.println("Quit the game.");
                break;
              }else
              {
                String[] numStrs = line.split(",");
                int[] nums = new int[numStrs.length];
                for(int i=0; i<nums.length; i++)
                {
                  nums[i] = Integer.parseInt(numStrs[i].trim());
                }
                Set<String> solutions = game.playGame(nums);
                if (solutions != null && solutions.size() > 0)
                {
                  for (String str : solutions)
                  {
                    System.out.println("Solution is: " + str);
                  }
                }else
                {
                  System.out.println("Can't find a solution for this one!");
                }
              }      
            }
          }
        }
        
        
        • 家园 这些好东东可得慢慢品。。。

          首先流涕地感谢泰让前辈和highway前辈的回复,记得好像60年代有位网友发过一贴:林彪教我当师长。今儿个俺也想发一帖:泰让highway教我学编程。怎奈还要考上1个月的试,哎!而我面壁是出了名的慢,这不,前些日子泰让兄让俺去学逆波兰表达式(俺可真得从头学起),刚刚窥了个门径,现在highway兄又把java代码(java俺的问题可更多)发了上来,这些好东东可得慢慢品。最后要说的是,俺面壁编程纯粹是出于由衷的兴趣才烦请解答,两位兄台千万不要误了正事才好。

          我想写这个程序的起因和老兄的完全一样。当时天真滴认为玩上3个for语句就结束(或许这就是专业和业余的区别?),然后接着干别的。可是。。。

          2个晚上过去了,还是不能很好地解决任意给出4个数的情况。没办法,从C++-STL里偷了个排列函数,算是对付过去了。可是输出时不能解决这种情况: 2+3输一遍,3+2又输一遍,还是不满意。后来就没时间玩了。

          highway兄是否再详细的写写(当然你有时间的话)这个程序的算法,我想这样更又助于我理解这个程序。譬如我看到你的这个东东:

          private static final String[] PATTERNS = new String[]{

          "((A OP1 B) OP2 C) OP3 D",

          "(A OP1 (B OP2 C)) OP3 D",

          "(A OP1 B) OP2 (C OP3 D)",

          "A OP1 ((B OP2 C) OP3 D)",

          "A OP1 (B OP2 (C OP3 D))",

          "(C OP3 D) OP2 (A OP1 B)" };

          觉得很有帮助,不过要用逆波兰式,可能就不涉及了吧?(java的这些类、函数看的有些吃力

          先请教这么多。再次感谢。

分页树展主题 · 全看首页 上页
/ 3
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河