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

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

不好意思。已经改过来了。

这是我的第一个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!");
        }
      }      
    }
  }
}