/*
 * @(#)Solution.java Version 1.0 98/03/12
 * 
 * Copyright (c) 1998 by Huahai Yang
 * 
 * Use at your own risk. I do not guarantee the fitness of this 
 * software for any purpose, and I do not accept responsibility for 
 * any damage you do to yourself or others by using this software.
 * This file may be distributed freely, provided its contents 
 * are not tampered with in any way.
 *
 */

import java.util.Vector;

/**
 * Given 4 integers, trying to form an expression using +, -, *, /,  
 * ( and ) so that the value of this expression equals 24
 */
public class Solution 
{
   // vector to store 4 integers
   static Vector numbers; 
  
   // flag to indicate whether there is solution
   boolean hasSolution;
   
   // final expression
   Vector theSolution = null;
   
   // the value of final expression
   double theResult;
   
   /* in order to avoid combination explosion, construct a list of 
    * valid positions for both numbers and operators as following:
    *    0  1  2  3  4  5  6  7  8  9 10 11 12
    *    (  n  o  (  n  )  o  (  n  )  o  n  )
    * 
    *    n - number, o - operator
    */ 
    
   static final int TOTAL_POSITION = 13;
   
   // valid number locations
   static final int [] NUM_POSITION = { 1, 4, 8, 11 }; 
   
   // valid number combinations
   static Integer [][] numCombin;
   
   // valid operator locations
   static final int [] OP_POSITION = { 2, 6, 10 };
   
   // valid operator combinations
   static int [][] opCombin;
   
   // valid parenthesis locations
   static final int [] PAREN_POSITION = { 0, 3, 5, 7, 9, 12 };
   
   // valid parenthesis combination, 0-no, 1-open, 2-close
   static final int [][] PAREN_COMBIN = 
   { 
      { 0, 0, 0, 0, 0, 0 },
      { 1, 0, 2, 0, 0, 0 },
      { 1, 0, 0, 0, 2, 0 },
      { 0, 1, 0, 0, 2, 0 },
      { 0, 1, 0, 0, 0, 2 },
      { 0, 0, 0, 1, 0, 2 },
      { 1, 0, 2, 1, 0, 2 },
   };  // PAREN_COMBIN
   
   /**
    * Constructs a solution, given 4 integers
    * @param num0 the first number
    * @param num1 the second number
    * @param num2 the third number
    * @param num3 the fouth number
    */
   public Solution(int num0, int num1, int num2, int num3)
   {
      numbers = new Vector(4);
            
      numbers.addElement(new Integer(num0));
      numbers.addElement(new Integer(num1));
      numbers.addElement(new Integer(num2));
      numbers.addElement(new Integer(num3));
      
      searchSolution();
               
   } // 4 param constructor  
   
   /**
    * Gets solution expression
    * @return one solution expressio as a vector
    */
   public Vector getSolution()
   {
      return theSolution;
   } //getSolution  
   
   /**
    * Judges if there is solution for this 4 number
    * @return  <code>true</code> if has solution
    *          <code>false</code> if no solution
    */          
   public boolean hasSolution()
   {
      return hasSolution;
   } // hasSolution  

   /**
    * Constructs a 4 number permutation matrix
    */
   static private void numberCombination()
   {
      Vector tmpNumbers = new Vector(4);
      numCombin = new Integer [24][4];
      int count = 0;
      
      for(int i = 0; i < 4; i++)
      {  
         for(int j = 0; j < 3; j++)
         {
            for(int k = 0; k < 2; k++)
            {
               tmpNumbers = (Vector)numbers.clone();
               
               numCombin[count][0] = (Integer)tmpNumbers.elementAt(i);
               tmpNumbers.removeElementAt(i);   
               
               numCombin[count][1] = (Integer)tmpNumbers.elementAt(j);
               tmpNumbers.removeElementAt(j);
               
               numCombin[count][2] = (Integer)tmpNumbers.elementAt(k);
               tmpNumbers.removeElementAt(k);
               
               numCombin[count][3] = (Integer)tmpNumbers.elementAt(0);
               tmpNumbers.removeElementAt(0);
               
               count++;
               
            } // for k
         } // for j
      } // for i   
   } // numberCombination
   
   /**
    * Constructs an operator combination matrix
    */
   static private void operatorCombination()
   {   
      opCombin = new int [64][3];
      int count = 0;
      
      for(int i = 0; i < 4; i++)
      {
         for(int j = 0; j < 4; j++)
         {
            for(int k = 0; k < 4; k++)
            {         
               opCombin[count][0] = i;
               opCombin[count][1] = j;
               opCombin[count][2] = k;
               
               count++;
               
            } // for k
         } // for j
      } // for i   
   } // operatorCombination
   
   /**
    * Uses enumeration to find a valid solution
    */
   private void searchSolution()
   {
      Character whiteSpace = new Character(' '),
                openParen = new Character('('),
                closeParen = new Character(')'),
                addition = new Character('+'),
                subtract = new Character('-'),
                multiply = new Character('*'),
                division = new Character('/');
      
      Vector tmpExpression = new Vector(TOTAL_POSITION); 
      
      int i, j, k;  // three simple loop variables
      int count = 0;
      
      numberCombination();   
      operatorCombination();
            
      // fill with whitespaces
      for(i = 0; i < TOTAL_POSITION; i++)
      {
         tmpExpression.addElement(whiteSpace);
      } // for   

      // search all the possible combination:
      // number * parenthesis * operator
      for(int num = 0; num < 24; num++)
      {
         for(int paren = 0; paren < 7; paren++)
         {
            for(int op = 0; op < 64; op++)
            {
               // fill in numbers
               for(i = 0; i < 4; i++)
               {
                  tmpExpression.setElementAt( numCombin[num][i], 
                        NUM_POSITION[i]);
               } // for numbers
               
               // fill in parenthesis
               for(i = 0; i < 6; i++)
               {
                  switch ( PAREN_COMBIN[paren][i] )
                  {
                     case 1:
                        tmpExpression.setElementAt(
                           openParen, PAREN_POSITION[i]);
                        break;
                     case 2:
                        tmpExpression.setElementAt(
                           closeParen, PAREN_POSITION[i]);
                        break;
                     case 0:
                        tmpExpression.setElementAt(
                           whiteSpace, PAREN_POSITION[i]);
                        break;
                  } // switch
               } // for parenthesis
               
               // fill in operators
               for(i = 0; i < 3; i++)
               {
                  switch ( opCombin[op][i] )
                  {
                     case 0:
                        tmpExpression.setElementAt(
                           addition, OP_POSITION[i]);
                        break;
                     case 1:
                        tmpExpression.setElementAt(
                           subtract, OP_POSITION[i]);
                        break;
                     case 2:
                        tmpExpression.setElementAt(
                           multiply, OP_POSITION[i]);
                        break;
                     case 3:
                        tmpExpression.setElementAt(
                           division, OP_POSITION[i]);
                        break;   
                  } // switch
               } // for operator
               
               // evaluate the generated expression               
               try
               {
                  theResult = new Expression(tmpExpression).getValue();
               } // try
               catch (IllegalExpressionException e)
	            {
	               // expression format error, keep trying
	               continue;
	            } // catch
	            
	            if( theResult == 24.0 )
	            {
	               // we found the solution
	               hasSolution = true;
	               theSolution = tmpExpression;
	               return;
	            } // if hasSolution
	         } // for op
	      } // for paren
	   } // for num   
	   
	   // searched all the combination, no solution
	   hasSolution = false;
	   theSolution = null;
	   
	} // searchSolution   
	                  
} // Solution