西西河

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

共:💬39 🌺28
全看树展主题 · 分页首页 上页
/ 3
下页 末页
家园 can you...

can you give me your code in java here?

家园 Sure, but it will cost you a bit

say, a million bucks. Deal?

刚刚做了一个循环,把所有可能的情况算了一把,结论如下(还没有验证过)

如果只允许四则运算,那么

In theory, total combination number is: 28561 (13*13*13*13)

Remove duplication, effective combination becomes: 1820 (say 7,7,4,2 = 2,4,7,7 = 2,7,4,4=...)

Total no-solution combination number is: 458

如果加入取余数,那么

Total no-solution combination number is: 218

等回家我把code整理一下,我下午下载了一套扑克牌gif图案,在加个简单的GUI,这个游戏不就齐活儿了吗!你要是愿意的话,给我个email地址,我给你一道发过去,怎么样?

家园 很久以前的事情了

代码手上已经没有了,您给点时间我再重新写一下。

家园 太牛了。能不能索性做成一个游戏供人在网上玩?
家园 一个循环需时多久?

有没有可能在一个范围内(如1-100)验证一下,哪个数字的无解率最低?

也算是验证一下这个问题:

毕竟只能是四则运算,那种小数,开方什么的高级货不算的。24是个偶数而且可以被3整除,同样的数字有12,36等,我猜3张牌算12,5张牌算36不错。就4张牌而言,算出24也许是4张牌的排列组合中最多的。一点愚见。

家园 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!");
        }
      }      
    }
  }
}

家园 对于四张牌,全循环一次40秒左右,

在我的core 2 duo E6300的机器上。如果使用多线程,时间降到了28秒左右。

三张牌算12成功率不高,5张牌计算量太大,随便给5个数字,方案都一大堆。比如说7,13,6,2,5,结果为

Solution is: 5-13=-8-->6-7=-1-->-1-2=-3-->-3*-8=24
Solution is: 7-13=-6-->5*2=10-->-6+10=4-->6*4=24
Solution is: 13-7=6-->5-2=3-->6*3=18-->18+6=24
Solution is: 7-6=1-->13-5=8-->1+2=3-->3*8=24
Solution is: 2*5=10-->7-13=-6-->-6+10=4-->6*4=24
Solution is: 2*5=10-->6-7=-1-->13--1=14-->10+14=24
Solution is: 5*2=10-->6-13=-7-->7--7=14-->14+10=24
Solution is: 5*2=10-->10+7=17-->13+17=30-->30-6=24
Solution is: 5*2=10-->6-10=-4-->13--4=17-->17+7=24
Solution is: 2*5=10-->7-6=1-->1+10=11-->13+11=24
Solution is: 5*2=10-->7+13=20-->10+20=30-->30-6=24
Solution is: 13+7=20-->2*5=10-->10-6=4-->20+4=24
Solution is: 5*2=10-->7-6=1-->1+13=14-->10+14=24
Solution is: 2+7=9-->13-5=8-->9-6=3-->3*8=24
Solution is: 6-7=-1-->-1-2=-3-->5-13=-8-->-3*-8=24
...
Solution is: 5-2=3-->3*6=18-->18-7=11-->13+11=24
Solution is: 7-13=-6-->5-2=3-->6*3=18-->18--6=24
Solution is: 7*2=14-->13+5=18-->18-14=4-->6*4=24
Solution is: 13-6=7-->2*5=10-->7+10=17-->7+17=24
Solution is: 6-13=-7-->7--7=14-->5*2=10-->10+14=24
Solution is: 5*2=10-->13-6=7-->7+7=14-->10+14=24
Solution is: 2*5=10-->13-6=7-->7+7=14-->10+14=24
Solution is: 13*5=65-->7+65=72-->72/6=12-->2*12=24
Solution is: 5*2=10-->10+7=17-->17+13=30-->30-6=24
Solution is: 2-6=-4-->7+-4=3-->13-5=8-->8*3=24
Solution is: 7-6=1-->2+1=3-->13-5=8-->3*8=24
Solution is: 13-6=7-->2*5=10-->10+7=17-->17+7=24
Solution is: 13-5=8-->2+7=9-->9-6=3-->8*3=24
Solution is: 6-2=4-->7-4=3-->13-5=8-->3*8=24
Solution is: 5*13=65-->7+65=72-->2*72=144-->144/6=24
Solution is: 13+7=20-->20-6=14-->2*5=10-->14+10=24
Solution is: 13-5=8-->2+7=9-->9-6=3-->3*8=24
Solution is: 5*2=10-->10-13=-3-->7+-3=4-->6*4=24
Solution is: 5*2=10-->13+10=23-->23+7=30-->30-6=24
Solution is: 2*5=10-->10+7=17-->17-6=11-->13+11=24
Solution is: 2*5=10-->13-10=3-->7-3=4-->6*4=24
Solution is: 5+7=12-->6/12=0.5-->13/0.5=26-->26-2=24
家园 真牛掰!
家园 1的乘方!!!

赖皮花

家园 呵呵,详细地说说你原来的算法俺就知足了。。。

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

另外解的同构性判断是个很复杂的问题,在组合搜索中,这种判断往往比寻找解的算法还要难。

什么叫解的同构性判断?譬如。。。

呵呵,详细地说说你原来的算法俺就知足了,不必重新写代码啦。

再次感谢。

家园 这些好东东可得慢慢品。。。

首先流涕地感谢泰让前辈和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的这些类、函数看的有些吃力

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

家园 这个可不敢当

我可不敢称高手,大家有问题互相讨论,相互学习的说,欢迎面壁以后有心得也同大家交流。

有代码可能说的更清楚些,周末争取写好调通

家园 牛掰! !
家园 我还以为这事只有我做过...

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

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

家园 是不是算法有疏漏?

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

7*(4-4/7)=24

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


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

Copyright © cchere 西西河