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

这是我的第一个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俺的问题可更多）发了上来，这些好东东可得慢慢品。最后要说的是，俺面壁编程纯粹是出于由衷的兴趣才烦请解答，两位兄台千万不要误了正事才好。