// Small program for solving the Four Fours puzzle. // // Revision history: // ------------------------------------------------------------------------ // 06-Feb-05 Carl Johansen v0.9 Created // 20-Feb-05 v0.91 Added stats // 06-Nov-09 v1.0 Can disable controversial terms. // Avoids answers with negative subexpressions. // Brought coding style into the 21st century. using System; using System.Diagnostics; using System.Collections.Generic; [assembly: CLSCompliant(true)] namespace CarlJohansen { /// /// Solves the Four Fours puzzle, namely: express each integer between 1 and 100 /// using standard operations and exactly four fours /// class FourFoursSolver { private enum Operation { Add = 0, Subtract, Multiply, Divide, Power } static Dictionary OperatorSymbol = new Dictionary{ { Operation.Add, '+' }, { Operation.Subtract, '-' }, { Operation.Multiply, '*' }, { Operation.Divide, '/' }, { Operation.Power, '^' } }; static private bool TryOperate(float lhs, float rhs, Operation operation, out float result) { result = 0; switch (operation) { case Operation.Add: result= lhs + rhs; return true; case Operation.Subtract: result= lhs - rhs; return true; case Operation.Multiply: try { result= lhs * rhs; return true; } catch (OverflowException) { return false; }; case Operation.Divide: if (rhs < 0.001 && Math.Abs(rhs) < 0.001) { return false; } else { result= lhs / rhs; return true; } case Operation.Power: try { result= (float)Math.Pow(lhs, rhs); return true; } catch (OverflowException) { return false; }; default: throw new InvalidOperationException("Unknown operation"); } } static private string ExpressionForDisplay(string[] displayTerms, int[] termIndex, Operation[] 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] + displayTerms[termIndex[0]].ToString() + separators[1] + OperatorSymbol[operations[0]] + separators[2] + displayTerms[termIndex[1]].ToString() + separators[3] + OperatorSymbol[operations[1]] + separators[4] + displayTerms[termIndex[2]].ToString() + separators[5] + OperatorSymbol[operations[2]] + separators[6] + displayTerms[termIndex[3]].ToString() + separators[7]; } [STAThread] static void Main(string[] args) { //You can set the maximum goal value as high as you like. The program will record all the results // that it finds that are <= this value. const int MAX_GOAL_VALUE = 102; //If you have a philosophical objection to the use of a term, disable it in the useTerm array. //But be prepared for a <100% solution. //The terms are: // 1: 4 // 2: sqrt(4) = 2 // 3: 4! = 1x2x3x4 = 24 // 4: .4 (0.4) // 5: .4bar ( = 4/9 = 0.4444....) // 6: sqrt(.4bar) = 2/3 bool[] useTerm = { true, true, true, true, true, true }; float[] candidateTerms = { 4, 2, 24, (4 / 10F), (4 / 9F), (2 / 3F) }; string[] candidateDisplayTerms = { "4", "sqrt(4)", "4!", ".4", ".4bar", "sqrt(.4bar)" }; int[] candidateTermBeauty = { 50, 40, 30, 10, 5, 1 }; // used to give preference to "simpler" answers string[] displayTerms = new string[candidateTerms.Length]; int[] termBeauty = new int[candidateTermBeauty.Length]; int numTerms = 0; for (int i = 0; i < useTerm.Length; i++) { numTerms += (useTerm[i] ? 1 : 0); } float[] terms = new float[numTerms + 2]; for (int i = 0, j = 0; i < useTerm.Length; i++) { if (useTerm[i]) { terms[j] = candidateTerms[i]; displayTerms[j] = candidateDisplayTerms[i]; termBeauty[j++] = candidateTermBeauty[i]; } } // 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 ) ) int[] termIndex = { 0, 0, 0, 0, numTerms, (byte)(numTerms + 1) }; string[] arrAnswer = new string[MAX_GOAL_VALUE + 1]; int[] arrBestAnswerScore = new int[MAX_GOAL_VALUE + 1]; bool[] seenResult = new bool[MAX_GOAL_VALUE + 1]; for (int i = 0; i < arrAnswer.Length; i++) { arrAnswer[i] = "** No solution found **"; } int numIterations = 0; int numSolved = 0; //Get the last member of the Operation enum (assuming members are contiguously numbered from zero). Operation lastOperationEnumMember = (Operation)(Enum.GetValues(typeof(Operation)).Length - 1); Operation[] operations = new Operation[3]; //Initialization is done - timing starts now. Stopwatch timer = Stopwatch.StartNew(); //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] < numTerms; termIndex[0]++) for (termIndex[1] = 0; termIndex[1] < numTerms; termIndex[1]++) for (termIndex[2] = 0; termIndex[2] < numTerms; termIndex[2]++) for (termIndex[3] = 0; termIndex[3] < numTerms; termIndex[3]++) for (operations[0] = 0; operations[0] <= lastOperationEnumMember; operations[0]++) for (operations[1] = 0; operations[1] <= lastOperationEnumMember; operations[1]++) { float currResultAsFloat = 0; for (operations[2] = 0; operations[2] <= lastOperationEnumMember; operations[2]++) { numIterations++; byte evaluationStep; bool evaluationSucceeded; for (evaluationStep = 0, evaluationSucceeded = true; evaluationStep <= 2 && evaluationSucceeded; evaluationStep++) { float tempResult; evaluationSucceeded = TryOperate(terms[termIndex[expression[association, evaluationStep, 0]]], terms[termIndex[expression[association, evaluationStep, 2]]], operations[expression[association, evaluationStep, 1]], out tempResult); if (evaluationSucceeded) switch (evaluationStep) { case 0: terms[numTerms] = tempResult; break; case 1: terms[numTerms + 1] = tempResult; break; case 2: currResultAsFloat = tempResult; break; } } int currResult = 0; if (evaluationSucceeded && 1 <= currResultAsFloat && currResultAsFloat <= MAX_GOAL_VALUE && Math.Abs((currResult = (int)(currResultAsFloat)) - (float)currResultAsFloat) < 0.0000001) { int currResultBeauty = 0; //Add up the individual "beauty scores" to get an overall score. currResultBeauty = termBeauty[termIndex[0]] + termBeauty[termIndex[1]] + termBeauty[termIndex[2]] + termBeauty[termIndex[3]]; //Deduct beauty points if either of the intermediate terms is negative (eg deduct points for +(4 - 4!)). // At some point we will encounter the mirror image (ie -(4! - 4)) and we should get the same // result, but using the more "beautiful" positive subexpressions. if (terms[numTerms] < 0) { currResultBeauty -= 10; } if (terms[numTerms + 1] < 0) { currResultBeauty -= 10; } if (currResultBeauty > arrBestAnswerScore[currResult]) { //This looks like the most attractive answer we have seen so far for the current result. arrBestAnswerScore[currResult] = currResultBeauty; switch (association) { case 0: arrAnswer[currResult] = ExpressionForDisplay(displayTerms, termIndex, operations, new string[] { "(", " ", " ", ") ", " (", " ", " ", ")" }); break; case 1: arrAnswer[currResult] = ExpressionForDisplay(displayTerms, termIndex, operations, new string[] { "( (", " ", " ", ") ", " ", ") ", " ", "" }); break; case 2: arrAnswer[currResult] = ExpressionForDisplay(displayTerms, termIndex, operations, new string[] { "(", " ", " (", " ", " ", ")) ", " ", "" }); break; case 3: arrAnswer[currResult] = ExpressionForDisplay(displayTerms, termIndex, operations, new string[] { "", "", " (", "", " (", "", "", ") )" }); break; } } if (!seenResult[currResult]) { seenResult[currResult] = true; numSolved++; } } } } timer.Stop(); for (int i = 1; i <= MAX_GOAL_VALUE; i++) { Console.WriteLine("{0} {1} {2}", i, seenResult[i] ? "=" : "", arrAnswer[i]); } Console.WriteLine(); Console.WriteLine("Done. ({0} loop iterations)", numIterations); Console.WriteLine("Num solved: {0}", numSolved); Console.WriteLine("Elapsed time: {0:00} milliseconds", timer.ElapsedMilliseconds); Console.ReadLine(); } } }