// Simple program for solving the Four Fours puzzle.
// 
// Revision history:
// ------------------------------------------------------------------------
// 06-Feb-05	Carl Johansen	v0.9	Created
// 20-Feb-05					v0.91	Added stats

using System;
[assembly:CLSCompliant(true)]

namespace CarlJohansen
{
	/// <summary>
	/// This class solves the Four Fours puzzle, namely: express each integer between 1 and 100 
	/// using standard operations and exactly four fours
	/// </summary>
	
	class FourFoursSolver
	{
		static private float Operate(float lhs, float rhs, int operation, out bool blnAbort) 
		{	
			blnAbort = false;
			switch(operation) 
			{
				case 0: return lhs + rhs; 
				case 1: return lhs - rhs; 
				case 2: try { return lhs * rhs; } 
						catch(OverflowException) { blnAbort = true; return 0; }; 
				case 3: if(rhs < 0.001) { blnAbort = true; return 0; } else return lhs / rhs; 
				case 4: try { return  (float) Math.Pow(lhs, rhs); } 
						catch(OverflowException) { blnAbort = true; return 0; }; 
				default: return -9999;
			}
		}

		static private string OperatorSymbol(int operation)
		{
			switch(operation) 
			{
				case 0: return "+"; 
				case 1: return "-"; 
				case 2: return "*"; 
				case 3: return "/"; 
				case 4: return "^";
				default: return "unknown operator!";
			}
		}

		static private string ExpressionForDisplay(string[] arrTermsDisp, byte[] termIndex, 
													int[] operations, string[] separators)
		{	//combines the expression's operators and operands using the specified separator characters
			// (white spaces and round brackets) to create a string for display
			return	separators[0] + 
					arrTermsDisp[termIndex[0]].ToString() + separators[1] + 
					OperatorSymbol(operations[0]) + separators[2] + 
					arrTermsDisp[termIndex[1]].ToString() + 
					separators[3] + OperatorSymbol(operations[1]) + 
					separators[4] + arrTermsDisp[termIndex[2]].ToString() + 
					separators[5] + OperatorSymbol(operations[2]) + 
					separators[6] + arrTermsDisp[termIndex[3]].ToString() + separators[7];
		}

		[STAThread]
		static void Main(string[] args)
		{	
			const int NUM_OPERATORS = 5, NUM_TERMS = 6;		
			int intCurrResult, intCurrResultScore, intIterations = 0;
			DateTime datStartTime = DateTime.Now;
			float decCurrResult = 0, decTempResult = 0;
			byte step;
			bool blnAbort;
			int[] operations = new int[3];
			float[] arrTerms =     { 4,   2,          24, 4.0F/10.0F, 4.0F/9.0F,  2.0F/3.0F,         0, 0 };
			string[] arrTermsDisp = { "4", "sqrt(4)", "4!", ".4",   ".4bar",  "sqrt(.4bar)" };
			int[] arrTermScore =    { 50,  40,         30,  20,       10,        1 }; // used to give preference to "simpler" answers

			// There are four possible groupings. 
			// { 0, 0, 1 } means apply operator #0 to operand #0 and operand #1 and call the result "operand #4"
			// { 2, 2, 3 } means apply operator #2 to operand #2 and operand #3 and call the result "operand #5"
			// { 4, 1, 5 } means apply operator #1 to operand #4 and operand #5.  This is the overall result
			byte[,,] expression = { { { 0, 0, 1 }, { 2, 2, 3 }, { 4, 1, 5 } },   // ( A x B ) x ( C x D )
									{ { 0, 0, 1 }, { 4, 1, 2 }, { 5, 2, 3 } },   // ( ( A x B ) x C ) x D
									{ { 1, 1, 2 }, { 0, 0, 4 }, { 5, 2, 3 } },   // ( A x ( B x C ) ) x D
									{ { 2, 2, 3 }, { 1, 1, 4 }, { 0, 0, 5 } } }; // A x ( B x ( C x D ) )

			byte[] termIndex = { 0, 0, 0, 0, NUM_TERMS, NUM_TERMS + 1 };

			string[] arrAnswer = new string[101]; 
			int[] arrBestAnswerScore = new int[101];
			bool[] seenResult = new bool[101];

			// go through all possible operator/operand combinations
			for(int association = 0 ; association < 4 ; association++)  //There are four ways of applying precedence to the operators
				for(termIndex[0] = 0 ; termIndex[0] < NUM_TERMS ; termIndex[0]++)
					for(termIndex[1] = 0 ; termIndex[1] < NUM_TERMS ; termIndex[1]++)
						for(termIndex[2] = 0 ; termIndex[2] < NUM_TERMS ; termIndex[2]++)
							for(termIndex[3] = 0 ; termIndex[3] < NUM_TERMS ; termIndex[3]++)										
								for(operations[0] = 0 ; operations[0] < NUM_OPERATORS ; operations[0]++)
									for(operations[1] = 0 ; operations[1] < NUM_OPERATORS ; operations[1]++)
										for(operations[2] = 0 ; operations[2] < NUM_OPERATORS ; operations[2]++)
										{	
											intIterations++;
											
											for(step = 0, blnAbort = false; step <= 2 && !blnAbort; step++)
											{
												decTempResult = Operate(arrTerms[termIndex[expression[association,step,0]]], 
																		arrTerms[termIndex[expression[association,step,2]]],
																		operations[expression[association,step,1]],
																		out blnAbort);

												if(!blnAbort) 
													switch(step)
													{
														case 0: arrTerms[NUM_TERMS] = decTempResult; break;
														case 1: arrTerms[NUM_TERMS + 1] = decTempResult; break;
														case 2: decCurrResult = decTempResult; break;
													}
											}

											if(!blnAbort && decCurrResult >= 1 && decCurrResult <= 100 && Math.Abs((intCurrResult = (int) (decCurrResult)) - (float) decCurrResult) < 0.0000001)
											{
												intCurrResultScore = arrTermScore[termIndex[0]] + arrTermScore[termIndex[1]] + arrTermScore[termIndex[2]] + arrTermScore[termIndex[3]];
												if(intCurrResultScore > arrBestAnswerScore[intCurrResult])
												{	//This looks like the most attractive answer we have seen so far for intCurrResult
													arrBestAnswerScore[intCurrResult] = intCurrResultScore;										
													switch(association)
													{																
													    case 0:		arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, new string[] { "(", " ", " ", ") ", " (", " ", " ", ")" } );
															break;
														case 1:		arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, new string[] { "( (", " ", " ", ") ", " ", ") ", " ", "" } );
															break;															
														case 2:		arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, new string[] { "", " ", " (", " ", " ", ") ", " ", "" } );
															break;
														case 3:		arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, new string[] { "", "", " (", "", " (", "", "", ") )" } );
															break;
														default: break;
													}
												}
															
												if(!seenResult[intCurrResult]) 
													seenResult[intCurrResult] = true;
											}										
										}
			for(int i=1 ; i<= 100; i++)
				Console.WriteLine(i.ToString() + " = " + arrAnswer[i]);

			Console.WriteLine("Done. ({0} loop iterations)", intIterations);
			Console.WriteLine("Elapsed time: {0:00} milliseconds" , DateTime.Now.Subtract(datStartTime).TotalMilliseconds);
			Console.ReadLine();
		}

	}
}