/**
 * Solve a problem I found on Hacker News using trees and recursion.
 */  
import java.util.*;

public class ZachProblem{

	public int count = 0;
	public ArrayList AllTrees = new ArrayList();
	public HashMap results = new HashMap();
	
	//Classes for our tree representation of this problem.
	public abstract class ProblemNode {
		public ProblemNode Left = null;
		public ProblemNode Right = null;
		public ArrayList Operators = null;
				
		public abstract float performOperation();
		public abstract ProblemNode copy(ArrayList Operators);
		public abstract float calculate();
		
		public void slot(ArrayList SlotThese, ProblemNode Head) {
			if (SlotThese.size() == 2) {
				float value1 = (float)(Float)SlotThese.get(0);
				float value2 = (float)(Float)SlotThese.get(1);

				IntegerNode TempLeft = new IntegerNode();
				TempLeft.value = value1;
				this.Left = TempLeft;				
	
				IntegerNode TempRight = new IntegerNode();
				TempRight.value = value2;
				this.Right = TempRight;
				
				if(value2 == 9.0f) {
					ProblemNode NewTree = Head.copy(null);
					AllTrees.add(NewTree);
					count++;
				}
			} else {
				int i = (int)(Math.random() * (SlotThese.size() - 1));
				
					
				ArrayList A = new ArrayList();
				for(int ii = 0; ii <= i; ii++) {
					A.add(new Float((float)(Float)(SlotThese.get(ii))));
				}
				
				ArrayList B = new ArrayList();
				for(int iii = i+1; iii < SlotThese.size(); iii++) {
					B.add(new Float((float)(Float)(SlotThese.get(iii))));
				}
				
				if (A.size() == 1) {
					IntegerNode Temp = new IntegerNode();
					Temp.value = (float)(Float)A.get(0);
					this.Left = Temp;
				} else {
					this.Left = new OperationNode();
					this.Left.slot(A, Head);
				}
				
				if (B.size() == 1) {
					IntegerNode Temp = new IntegerNode();
					Temp.value = (float)(Float)B.get(0);
					this.Right = Temp;
					
					if (Temp.value == 9.0f) {
						ProblemNode NewTree = Head.copy(null);
						AllTrees.add(NewTree);
						count ++;
					}
					
				} else {
					this.Right = new OperationNode();
					this.Right.slot(B, Head);
				}
					
			}
		}
	}
	
	public class  OperationNode extends ProblemNode {
		public int operation = 0;
		public int MULTIPLY = 0;
		public int ADD = 1;
		public int SUBTRACT = 2;
		public int DIVIDE = 3;

		public String operationStrings[] = new String[]{"*", "+", "-", "/"};
	
		public float performOperation() {
			return Left.performOperation() * Right.performOperation();
		}
		
		public String toString() {
			String returnMe = "";
			if (Left instanceof IntegerNode) {
				returnMe += Left;
			} else {
				returnMe += "(" + Left + ")";
			}
			
			returnMe += operationStrings[operation];
			
			if (Right instanceof IntegerNode) {
				returnMe += Right;
			} else {
				returnMe += "(" + Right + ")";
			}
			
			return returnMe;
		}
		
		public ProblemNode copy(ArrayList Operators) {
		
			OperationNode copy = new OperationNode();
			
			if (Operators == null) {
				copy.Operators = new ArrayList();
				copy.Operators.add(copy);
				Operators = copy.Operators;
			} else {
				Operators.add(copy);
			}
			
			copy.Right = this.Right.copy(Operators);
			copy.Left = this.Left.copy(Operators);
			return copy;
		}
		
		public float calculate() {
			if (operation == MULTIPLY) {
				return Left.calculate() * Right.calculate();
			} else if(operation == DIVIDE) {
				return Left.calculate() / Right.calculate();
			} else if(operation == ADD) {
				return Left.calculate() + Right.calculate();
			} else {
				return Left.calculate() - Right.calculate();
			}
		}
	}
	
	public class IntegerNode extends ProblemNode {
		public float value;
	
		public float performOperation() {
			return value;
		}
		
		public String toString() {
			return "" + value;
		}
		
		public ProblemNode copy(ArrayList Operators) {
			IntegerNode copy = new IntegerNode();
			copy.value = this.value;
			return copy;
		}
		
		public float calculate() {
			return value;
		}
	}
		
	/**
	Construct the algorithm and execute it.
	*/
	public ZachProblem() {
		ArrayList SlotThese = new ArrayList();
		SlotThese.add(new Float(1.0));
		SlotThese.add(new Float(2.0));
		SlotThese.add(new Float(3.0));
		SlotThese.add(new Float(4.0));
		SlotThese.add(new Float(5.0));
		SlotThese.add(new Float(6.0));
		SlotThese.add(new Float(7.0));
		SlotThese.add(new Float(8.0));
		SlotThese.add(new Float(9.0));
		
		//Create the intial head node, this will be used to create all the trees.
		ProblemNode HeadNode = new OperationNode();
		
		while(AllTrees.size() < 1024) {
			HeadNode.slot(SlotThese, HeadNode);
		}
		
		System.out.println("Terminal condition hit " + count + " times.");
		
		bruteForce();
	}
	
	/**
	Perform the brute force search for solutions in the problem space.
	*/
	public void bruteForce() {
		int iteration = 0;
		
		for (int index = 0; index < AllTrees.size(); index++) {
			ProblemNode ProblemTree = (ProblemNode)AllTrees.get(index);
			
			Object Operators[] = (Object[])ProblemTree.Operators.toArray();
													
			for(int i=0;i<4;i++) {
			for(int ii=0;ii<4;ii++) {
			for(int iii=0;iii<4;iii++) {
			for(int iv=0;iv<4;iv++) {
			for(int v=0;v<4;v++) {
			for(int vi=0;vi<4;vi++) {
			for(int vii=0;vii<4;vii++) {
			for(int viii=0;viii<4;viii++) {

				((OperationNode)Operators[0]).operation = i;
				((OperationNode)Operators[1]).operation = ii;
				((OperationNode)Operators[2]).operation = iii;
				((OperationNode)Operators[3]).operation = iv;
				((OperationNode)Operators[4]).operation = v;
				((OperationNode)Operators[5]).operation = vi;
				((OperationNode)Operators[6]).operation = vii;
				((OperationNode)Operators[7]).operation = viii;

				float calculation = ProblemTree.calculate();
				if (calculation >= 1900 && calculation <= 2100) {
					int calculationInteger = (int)calculation;
					if (calculation - calculationInteger == 0) {
						results.put(new Integer(calculationInteger), "" + ProblemTree);
					}
				}
				
				iteration ++;
			}
			}
			}
			}
			}
			}
			}
			}
			
			if(results.size() == 201)
				break;
		}

		//Output the results for confirmation.
		Object[] key = results.keySet().toArray();
		Arrays.sort(key); 
		
		ArrayList FinalResults = new ArrayList();
		for (int i = 0; i < key.length; i++) {
			FinalResults.add(new Object[]{key<i>, results.get(key<i>)});
		}
		
		for (int i = 0; i< FinalResults.size(); i++) {
			Object O[] = (Object[])FinalResults.get(i);
			System.out.println(O[1] + " = " + O[0]);
		}
		

		Object[] data = results.values().toArray();
		System.out.println("Result Size = " + data.length);
	}
	
	//Testing main.
	public static void main(String args[]) {
		ZachProblem MyProblem = new ZachProblem();
	}
}