Inception-Like Programming

When the moving Inception came out in 2010, everyone thought that it would become the next Matrix sensation. It did not. However, the plot was interesting. In essence, folks in a dream (level 1) have a dream (level 2) where they have a dream (level 3) where they have a dream (level 4) where some action happens. 4-levels of dreaming. Now a dream by itself is already a very abstract entity, hard to grasp the concept most of the time. Never mind 4 levels of dreaming.
It just so happens that a programming problem that I stumbled upon requires kind of the same paradigm of abstraction in order to solve it. Here is the problem gave to me by a friend at Microsoft:

In the game 24, you get four numbers and try to use +,-,x,÷ and () to make an equation using all four that equals 24. For example, if I gave you 4, 4, 6, 9, you might write:

(4 + 4) x (9 - 6) = 24.

One nifty thing about 24 is that it is actually the product of the run of the first four positive integers: 1 x 2 x 3 x 4 = 24. Is it possible to make 24 for all the other "runs":
2, 3, 4, 5;
3, 4, 5, 6;
4, 5, 6, 7;
5, 6, 7, 8;
6, 7, 8, 9?

Generalizing it: given 4 digits [1,9], can you arrange them, add operators, brackets, in such a way that they evaluate to 24?

The Inception-Like comes to this problem if you think of "Recursion" as being the same as a "Dream". We'll need 4 levels of recursion to solve this problem:

• Level 1: use recursion to permute all the digits. For each permutation...
• Level 2: use recursion to add the arithmetic operators. And then...
• Level 3: use recursion to add brackets. And finally...
• Level 4: use recursion to evaluate the expression!!!

Each recursion is slightly different than the others. When you run the code for an input such as "1 2 8 5", either there is going to be a solution and the solution is printed out, or no solution. For this particular case one solution is:

(-1*2+5)*8 = 24

Highly exponential algorithm due to all the multiple nested recursions, but given the limited size of the input (4), it runs relatively fast. Enjoy-njoy-joy-oy-y!!!!!

Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace _24Game
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length != 4)
            {
                Usage();
                return;
            }
            int[] numbers = new int[4];
            for (int i = 0; i < args.Length; i++)
            {
                int digit = 0;
                if (!Int32.TryParse(args[i], out digit) ||
                    digit < 0 ||
                    digit > 9)
                {
                    Usage();
                    return;
                }
                numbers[i] = digit;
            }
            Util.Process(numbers);
        }
        public static void Usage()
        {
            Console.WriteLine("Usage: 24Game.exe digit1 digit2 digit3 digit4");
            Console.WriteLine("Each digit being a number greater than 0 and less than 10");
            return;
        }
    }
}
Util.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace _24Game
{
    class Util
    {
        public static void Process(int[] numbers)
        {
            Hashtable htNumberAlreadyUsed = new Hashtable();
            Hashtable htPermutationAlreadyUsed = new Hashtable();
            Console.WriteLine();
            if (!FirstRecursion_GeneratePermutations(numbers, 0, "", htNumberAlreadyUsed, htPermutationAlreadyUsed))
            {
                Console.WriteLine("No Solution!");
            }
        }
        public static bool FirstRecursion_GeneratePermutations(int[] numbers,
                                                               int currentIndex,
                                                               string permutation,
                                                               Hashtable htNumberAlreadyUsed,
                                                               Hashtable htPermutationAlreadyUsed)
        {
            if (currentIndex >= numbers.Length)
            {
                if (htPermutationAlreadyUsed.ContainsKey(permutation))
                {
                    return false;
                }
                htPermutationAlreadyUsed.Add(permutation, true);
                string[] parts = permutation.Split(new char[] { '@' }, StringSplitOptions.RemoveEmptyEntries);
                int[] numberPermutation = new int[numbers.Length];
                for (int i = 0; i < parts.Length; i++)
                {
                    numberPermutation[i] = Convert.ToInt32(parts[i]);
                }
                return SecondRecursion_AddOperators(numberPermutation, 0, "");
            }
            for (int i = 0; i < numbers.Length; i++)
            {
                if (!htNumberAlreadyUsed.ContainsKey(i)) //Index, not the actual number
                {
                    htNumberAlreadyUsed.Add(i, true);
                    if (FirstRecursion_GeneratePermutations(numbers,
                                                           currentIndex + 1,
                                                           permutation + "@" + numbers[i],
                                                           htNumberAlreadyUsed,
                                                           htPermutationAlreadyUsed))
                    {
                        return true;
                    }
                    htNumberAlreadyUsed.Remove(i);
                }
            }
            return false;
        }
        public static bool SecondRecursion_AddOperators(int[] numbers,
                                                        int currentIndex,
                                                        string currentExpression)
        {
            if (numbers == null)
            {
                return false;
            }
            if (currentIndex >= numbers.Length)
            {
                //Try without brackets first
                double result = 0.0;
                if (FourthRecursion_MathExpressionEvaluator(currentExpression, out result))
                {
                    if (result == 24)
                    {
                        Console.WriteLine("{0} = 24", RemoveRedundantBrackets(currentExpression));
                        return true;
                    }
                }
                if (ThirsRecursion_AddBrackets(numbers,
                                               currentExpression,
                                               0,
                                               "",
                                               0))
                {
                    return true;
                }
                return false;
            }
            foreach (char op in "+-*/")
            {
                if (currentIndex == 0 && op == '-')
                {
                    if (SecondRecursion_AddOperators(numbers, currentIndex + 1, currentExpression + op.ToString() + numbers[currentIndex]))
                    {
                        return true;
                    }
                }
                else if (currentIndex == 0)
                {
                    if (SecondRecursion_AddOperators(numbers, currentIndex + 1, currentExpression + numbers[currentIndex]))
                    {
                        return true;
                    }
                }
                else if (currentIndex > 0)
                {
                    if (SecondRecursion_AddOperators(numbers, currentIndex + 1, currentExpression + op.ToString() + numbers[currentIndex]))
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        public static bool ThirsRecursion_AddBrackets(int[] numbers,
                                                      string originalExpression,
                                                      int originalExpressionIndex,
                                                      string expression,
                                                      int numberOfOpenMinusClosedBrackets)
        {
            if (String.IsNullOrEmpty(originalExpression))
            {
                return false;
            }
            if (originalExpressionIndex >= originalExpression.Length)
            {
                string localExpression = expression;
                for (int i = 0; i < numberOfOpenMinusClosedBrackets; i++)
                {
                    localExpression += ")";
                }
                double result = 0.0;
                if (Util.FourthRecursion_MathExpressionEvaluator(localExpression, out result))
                {
                    if (result == 24)
                    {
                        Console.WriteLine("{0} = 24", RemoveRedundantBrackets(localExpression));
                        return true;
                    }
                }
                return false;
            }
            //1. Try to add an open bracket
            if (numberOfOpenMinusClosedBrackets < numbers.Length - 1 &&
               (expression.Length == 0 ||
                ((expression[expression.Length - 1] < '0' || expression[expression.Length - 1] > '9') &&
                  expression[expression.Length - 1] != ')')))
            {
                if (ThirsRecursion_AddBrackets(numbers,
                                               originalExpression,
                                               originalExpressionIndex,
                                               expression + "(",
                                               numberOfOpenMinusClosedBrackets + 1))
                {
                    return true;
                }
            }
            //2. Try to add a closed bracket
            if (numberOfOpenMinusClosedBrackets > 0 &&
                ((expression[expression.Length - 1] >= '0' && expression[expression.Length - 1] <= '9') ||
                 expression[expression.Length - 1] == ')'))
            {
                if (ThirsRecursion_AddBrackets(numbers,
                                               originalExpression,
                                               originalExpressionIndex,
                                               expression + ")",
                                               numberOfOpenMinusClosedBrackets - 1))
                {
                    return true;
                }
            }
            //3. Add the char in the original string
            return ThirsRecursion_AddBrackets(numbers,
                                              originalExpression,
                                              originalExpressionIndex + 1,
                                              expression + originalExpression[originalExpressionIndex],
                                              numberOfOpenMinusClosedBrackets);
        }
        public static bool FourthRecursion_MathExpressionEvaluator(string expression,
                                                                   out double result)
        {
            result = 0;
            if (expression == null)
            {
                return false;
            }
            if (expression.Trim().Length == 0)
            {
                return true;
            }
            if (expression.Length > 2 &&
                expression.StartsWith("(") &&
                expression.EndsWith(")") &&
                IsWellFormedBrackets(expression.Substring(1, expression.Length - 2)))
            {
                return FourthRecursion_MathExpressionEvaluator(expression.Substring(1, expression.Length - 2), out result);
            }
            if (Double.TryParse(expression, out result))
            {
                return true;
            }
            char[] operators = new char[] { '+', '-', '*', '/' };
            foreach (char op in operators)
            {
                int bracketsCount = 0;
                for (int i = expression.Length - 1; i >= 0; i--)
                {
                    if (expression[i] == '(')
                    {
                        bracketsCount++;
                    }
                    else if (expression[i] == ')')
                    {
                        bracketsCount--;
                    }
                    if (expression[i] == op &&
                        bracketsCount == 0)
                    {
                        double value1 = 0;
                        double value2 = 0;
                        string part1 = "";
                        string part2 = "";
                        if (i > 0)
                        {
                            part1 = expression.Substring(0, i);
                        }
                        if (i + 1 < expression.Length)
                        {
                            part2 = expression.Substring(i + 1);
                        }
                        if (!FourthRecursion_MathExpressionEvaluator(part1, out value1))
                        {
                            return false;
                        }
                        if (!FourthRecursion_MathExpressionEvaluator(part2, out value2))
                        {
                            return false;
                        }
                        switch (op)
                        {
                            case '+':
                                result = value1 + value2;
                                break;
                            case '-':
                                result = value1 - value2;
                                break;
                            case '*':
                                result = value1 * value2;
                                break;
                            case '/':
                                if (value2 == 0)
                                {
                                    return false;
                                }
                                result = value1 / value2;
                                break;
                        }
                        return true;
                    }
                }
            }
            return false;
        }
        public static string RemoveRedundantBrackets(string expressionInput)
        {
            //First mark off
            //Then remove
            StringBuilder expression = new StringBuilder(expressionInput);
            for (int i = 0; i < expression.Length; i++)
            {
                int begin = -1;
                int end = -1;
                if (expression[i] >= '0' &&
                    expression[i] <= '9')
                {
                    if (i - 1 >= 0 &&
                        expression[i - 1] == '-')
                    {
                        begin = i - 2;
                    }
                    else
                    {
                        begin = i - 1;
                    }
                    end = i + 1;
                    while (begin >= 0 &&
                           end < expression.Length &&
                           expression[begin] == '(' &&
                           expression[end] == ')')
                    {
                        expression[begin] = '#';
                        expression[end] = '#';
                        begin--;
                        end++;
                    }
                }
            }
            string finalExpression = "";
            for (int i = 0; i < expression.Length; i++)
            {
                if (expression[i] != '#')
                {
                    finalExpression += expression[i].ToString();
                }
            }
            return finalExpression;
        }
        public static bool IsWellFormedBrackets(string expression)
        {
            if (expression == null ||
                expression.Trim().Length == 0)
            {
                return true;
            }
            int bracketsCount = 0;
            for (int i = 0; i < expression.Length; i++)
            {
                if (expression[i] == '(')
                {
                    bracketsCount++;
                }
                else if (expression[i] == ')')
                {
                    bracketsCount--;
                }
                if (bracketsCount < 0)
                {
                    return false;
                }
            }
            return bracketsCount == 0;
        }
    }
}