// 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
{
    /// <summary>
    /// Solves the Four Fours puzzle, namely: express each integer between 1 and 100 
    /// using standard operations and exactly four fours
    /// </summary>

    class FourFoursSolver
    {
        private enum Operation
        {
            Add = 0,
            Subtract,
            Multiply,
            Divide,
            Power
        }

        static Dictionary<Operation, char> OperatorSymbol = new Dictionary<Operation, char>{
            { 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();
        }
    }
}