# Optimization expression evaluation challenge

I'm trying to calculate a total value with an array of six numbers and all the basic operators (+-*/).

Suppose you have: 1, 2, 3, 4, 5, 6 and you want to have a total of 10.

Here is my function call a part of my result:

10 = 4 - ((2 - (5 + 6)) + (3 * 1)) 10 = (((6 - 4) - 1) - (2 - 3)) * 5 10 = (2 * 3) - ((1 + (5 - 4)) - 6)
:
:
:
10 = 3 - (5 - (6 * 2)) 10 = (3 - 2) * ((1 * 5) * (6 - 4))
10 = (4 + (6 + 3)) - ((5 + 1) / 2)

Number of solutions = 252676

3/28/2013 12:28:25 PM 3/28/2013 12:28:44 PM 00:00:19.7425257

It took 19 secs for my old quad CPU Q8200 2.33Ghz to process the 105164223 possible expression. I put all the possible expression in a Hashtable. And at the end, I print all the valid expressions. There should be a way to speed up this process.

I have tried to put all the results in a file like: (C - B) * ((A * E) * (F - D))

After that, I process the file and change the letter for the right number. But this file has a size of about 2GB, and it takes 35 secs just to read the file without any progress.

I'd like to have your comments about the code. Can I speed up this code? How can we speed up the process, may be :( parallel, task, async/wait, etc.. ) I'm not used of all this things.

Do you have an other idea for the calculation like put all the equation in a table (like: (C - B) * ((A * E) * (F - D))) and process the table.

Sky drive

using System;
using System.Collections;

/// <summary>
///  Class to Find all the possible value to reach a number
///from an number array with the basic operators
/// </summary>
class PossibleExpression
{
public DateTime mStartDateTime;
public DateTime mEndDateTime;
public TimeSpan mTimeSpan;

// all the solutions are stored in an Hachtable
public Hashtable mSolutionHashtable = new Hashtable();

// NbEvaluate
public int mNbEvaluate = 0;

// calculate the AbsValue, if we are not able to reach the total, we kept the nearest total
public int mAbsValue = int.MaxValue;

public PossibleExpression()
{

}

/// <summary>
/// Evaluate all the possibility to reach the total with this numbers
/// </summary>
/// <param name="Numbers"></param>
/// <param name="total"></param>
private void Evaluate(Number[] Numbers, int total)
{
mNbEvaluate++;

if (Numbers.Length == 1)
{
int absValue = Math.Abs(Numbers.Value - total);

// if the abolute value is less then the one before
if (absValue < mAbsValue)
{
mAbsValue = absValue;
}

// if it was the right absolute value store the ValueString and the Value in the SolutionHashtable
if (mAbsValue == absValue)
{
string valueString = Numbers.ValueString.ToString();
if (mSolutionHashtable.ContainsKey(valueString) == false)
{
}
}
}
else
{
{
// we prepare to call back the function with a smaller array size
Number[] NextNumbers = new Number[Numbers.Length - 1];

{
// allocate Number for this new array
int i = 0;
while (i < NextNumbers.Length)
{
NextNumbers[i] = new Number();
i++;
}
}

// get the right Mix Array
int[][] Mix = AllMix[Numbers.Length];

// for all the possible Mix
int indexMixOperand = 0;
while (indexMixOperand < Mix.Length)
{
// copy all the numbers that was not in the Mix index
if ((Numbers.Length - 1 > 1))
{
int indexNextNumbers = 1;     // we kept the index 0 for the Mix result
int i = 0;
while (i < Numbers.Length)
{
if ((i != Mix[indexMixOperand])
&& (i != Mix[indexMixOperand]))
{
NextNumbers[indexNextNumbers++] = Numbers[i];
}
i++;
}
}

// for all the operators
for (int indexOperator = 0; indexOperator < 4; indexOperator++)
{
// set the number 0  to the total of the expression composed of this two number and operator
if (NextNumbers.Set(Numbers[Mix[indexMixOperand]], Numbers[Mix[indexMixOperand]], indexOperator) == true)
{
// call to evaluate
Evaluate(NextNumbers, total);
}
//next operator
}

// next MixPermutation
indexMixOperand++;
}
}
}
}

public bool Find(int[] numbers, int total)
{
if( numbers.Length == 6)
{
mStartDateTime = DateTime.Now;

mSolutionHashtable = new Hashtable();
mNbEvaluate = 0;
mAbsValue = int.MaxValue;

Number[] Numbers = new Number;
Numbers = new Number();
Numbers = new Number();
Numbers = new Number();
Numbers = new Number();
Numbers = new Number();
Numbers = new Number();

Numbers.Set(numbers);
Numbers.Set(numbers);
Numbers.Set(numbers);
Numbers.Set(numbers);
Numbers.Set(numbers);
Numbers.Set(numbers);

foreach (int[] index in m_Index)
{
Number[] CurrentNumbers = new Number[index.Length];

for (int i = 0; i < index.Length; i++)
{
CurrentNumbers[i] = Numbers[index[i]];
}
Evaluate(CurrentNumbers, total);
}

mEndDateTime = DateTime.Now;
mTimeSpan = mEndDateTime - mStartDateTime;
}

return (numbers.Length == 6);
}

// possible index for indirection table
static private int[][] m_Index = new int[][]
{
// with one number
new int[] {0},
new int[] {1},
new int[] {2},
new int[] {3},
new int[] {4},
new int[] {5},

// with two numbers
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {0,5},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {1,5},
new int[] {2,3},
new int[] {2,4},
new int[] {2,5},
new int[] {3,4},
new int[] {3,5},
new int[] {4,5},

// with three numbers
new int[] {0,1,2},
new int[] {0,1,3},
new int[] {0,1,4},
new int[] {0,1,5},
new int[] {0,2,3},
new int[] {0,2,4},
new int[] {0,2,5},
new int[] {0,3,4},
new int[] {0,3,5},
new int[] {0,4,5},
new int[] {1,2,3},
new int[] {1,2,4},
new int[] {1,2,5},
new int[] {1,3,4},
new int[] {1,3,5},
new int[] {1,4,5},
new int[] {2,3,4},
new int[] {2,3,5},
new int[] {2,4,5},
new int[] {3,4,5},

// with four numbers
new int[] {0,1,2,3},
new int[] {0,1,2,4},
new int[] {0,1,2,5},
new int[] {0,1,3,4},
new int[] {0,1,3,5},
new int[] {0,1,4,5},
new int[] {0,2,3,4},
new int[] {0,2,3,5},
new int[] {0,2,4,5},
new int[] {0,3,4,5},
new int[] {1,2,3,4},
new int[] {1,2,3,5},
new int[] {1,2,4,5},
new int[] {1,3,4,5},
new int[] {2,3,4,5},

// with five numbers
new int[] {0,1,2,3,4},
new int[] {0,1,2,3,5},
new int[] {0,1,2,4,5},
new int[] {0,1,3,4,5},
new int[] {0,2,3,4,5},
new int[] {1,2,3,4,5},

// with six numbers
new int[] {0,1,2,3,4,5},
};

static private int[][] Mix0 = new int[][]
{
};

static private int[][] Mix1 = new int[][]
{
};

static private int[][] Mix2 = new int[][]
{
new int[] {0,1},
new int[] {1,0}
};

static private int[][] Mix3 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {1,0},
new int[] {1,2},
new int[] {2,0},
new int[] {2,1}
};

static private int[][] Mix4 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2}
};

static private int[][] Mix5 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {2,4},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2},
new int[] {3,4},
new int[] {4,0},
new int[] {4,1},
new int[] {4,2},
new int[] {4,3}
};

static private int[][] Mix6 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {0,5},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {1,5},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {2,4},
new int[] {2,5},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2},
new int[] {3,4},
new int[] {3,5},
new int[] {4,0},
new int[] {4,1},
new int[] {4,2},
new int[] {4,3},
new int[] {4,5},
new int[] {5,0},
new int[] {5,1},
new int[] {5,2},
new int[] {5,3},
new int[] {5,4}
};

static private int[][][] AllMix = { Mix0, Mix1, Mix2, Mix3, Mix4, Mix5, Mix6 };

using System.Text;

/// <summary>
/// allways have the value and the Value in String format
/// </summary>
public class Number
{

// the int value
public int Value = 0;

// the string value
public StringBuilder ValueString = new StringBuilder(40);

// the operator
public int m_Operator = -1;

/// <summary>
/// Set the value
/// </summary>
/// <param name="value"></param>
public void Set(int value)
{
Value = value;
ValueString.Clear();
ValueString.Append(value);
}

/// <summary>
/// Build the Value String depending on the operand and the operator
/// </summary>
/// <param name="Operande1"></param>
/// <param name="Operande2"></param>
/// <param name="Operator"></param>
private void BuildValueString(Number Operande1, Number Operande2, int Operator)
{
ValueString.Clear();

//        int Operande1OperatorFamily = Operande1.m_Operator / 2;
//        int Operande2OperatorFamily = Operande2.m_Operator / 2;
//        int OperatorFamily = Operator / 2;

if ((Operande1.m_Operator != -1)
//                && (    (Operande1OperatorFamily != OperatorFamily)
//                   || (Operator == 1)
//                 || (Operator == 2)
//               || (Operator == 3)
//             )
)
{
ValueString.Append("(");
}

ValueString.Append(Operande1.ValueString);

if ((Operande1.m_Operator != -1)
//                && ((Operande1OperatorFamily != OperatorFamily)
//                     || (Operator == 1)
//                    || (Operator == 2)
//                   || (Operator == 3)
//            )
)
{
ValueString.Append(")");
}

switch (Operator)
{
case 0:
ValueString.Append(" + ");
break;
case 1:
ValueString.Append(" - ");
break;
case 2:
ValueString.Append(" * ");
break;
case 3:
ValueString.Append(" / ");
break;
}

if ((Operande2.m_Operator != -1)
//              && (  (Operande2OperatorFamily != OperatorFamily)
//                 || (Operator == 1)
//               || (Operator == 2)
//             || (Operator == 3)
//          )
)
{
ValueString.Append("(");
}

ValueString.Append(Operande2.ValueString);

if ((Operande2.m_Operator != -1)
//                && ((Operande2OperatorFamily != OperatorFamily)
//                   || (Operator == 1)
//                 || (Operator == 2)
//               || (Operator == 3)
//            )
)
{
ValueString.Append(")");
}
}

/// <summary>
/// Set the number for these operands and operator
/// </summary>
/// <param name="Operande1"></param>
/// <param name="Operande2"></param>
/// <param name="Operator"></param>
/// <returns></returns>
public bool Set(Number Operande1, Number Operande2, int Operator)
{
bool returnValue = true;
m_Operator = Operator;

Value = Operande1.Value;

switch (Operator)
{
case 0:
Value += Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 1:
Value -= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 2:
Value *= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 3:
if ((Operande2.Value != 0)
&& (Value % Operande2.Value) == 0)
{
Value /= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
}
else
{
returnValue = false;
}
break;
}

return returnValue;
}
}
}

• I believe you wrote too much code. Are you using en.wikipedia.org/wiki/Reverse_Polish_notation to compute the values or are you doing something more complex? It is hard to tell by reading all that code. You could also create a dictionary that maps a char operand such as '*' to a lambda that computes the result. I coded something similar in Python ages ago and the hardest part was setting up reverse postfix and some combinatorial tricks. – Leonid Mar 28 '13 at 20:29
• What does 6 * (1 / 3) equal? Does 1/3 evaluate to 0 thus making the whole thing 0 or is it operating on floats? If all arithmetic is integer, then you could cull non-integer fractions to speed things up. I would simplify the algorithm before polishing the C# look and feel, as your code could look quite different when you are done. – Leonid Mar 28 '13 at 20:34
• Looks like you are doing some memoization with a Hashtable, which is a good idea, I am just not sure yet what it is that you are memoizing. You should using a generic Dictionary<TKey, TValue> instead of Hashtable. – Leonid Mar 28 '13 at 20:42
• 1/3 is not a valid sub expression, all arithmetic are integers – UnBinBonGars Mar 28 '13 at 20:45
• There should be at most (4^5) * 6! = 737280 permutations: n1 op n2 op n3 op n4 op n5 op n6 - you have 6! ways to rearrange the numbers and 4*4*4*4*4 = 1024 ways to pick 5 different operators. With reverse postfix notation the sequence will not necessarily be num op num op ... but it is true that you need one less operator than you have numbers. – Leonid Mar 28 '13 at 20:52

I'll comment on the C#ness of the code, then we can worry about the logic.

Overall, not bad. I like the casing and white space.

I see a few things to improve though:

1. In C#, the general standard for class level members is to prefix with a _. i.e. _solutionHasTable, or if you prefer m_solutionHasTable. There is discussions all over as to which is better, I'll let you decide.
2. No need to include an empty default constructor. C# will add it if it is not declared.
3. Use var when declaring obvious variables. var is strongly typed, using it just removes unneeded clutter from the code. i.e. var absValue = Math.Abs(Numbers.Value - total);
4. Overall, I think your methods are too long, and trying to do too much. Optimally, the whole method should fit onto one screen. If it doesn't, refactor it into smaller functions. This will also help with #5
5. I think the code is over commented. comments like // for all the operators or // call to evaluate are just reiterating what I can read in the code. Comments should be saved to describe why you did something, or to enhance the code, not explain what it is doing. Good code explains what its doing
6. Too many magic numbers. use private const int MeaningOfNumber = 1 instead.
7. foreach is a much easier loop structure than for (var i=0;i<4;i++) to use. You should look into it
8. m_Index is not correct naming convention for C#. I think a better name can be found.
9. On the same note, the operations in m_Index could be done with loops, and constant (or a value in the app.confg file). This way if in the future the number changes, you change it in one place, and the program continues running.
10. Use enums when you can. Your operators should be an enum, that will make the switch statement much easier to read:

switch (Operator)
{
Value += Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Subtract:
Value -= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Multiple:
Value *= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Divide:
if ((Operande2.Value != 0)
&& (Value % Operande2.Value) == 0)
{
Value /= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
}
else
{
returnValue = false;
}
break;
}

• I believe there is actually no standard for fields. Some use the m_ prefix, others no prefix. – svick Mar 28 '13 at 20:58
• true, but generally there is something there. – Jeff Vanzella Mar 28 '13 at 21:00
• If you count StyleCop as standard, then it would prescrive using this. instead of m_. – Leonid Mar 28 '13 at 21:01
• Reshaper likes _ Tomato Tomato I guess... – Jeff Vanzella Mar 28 '13 at 21:02
• var is strongly typed. There aren't any speed enhancements, most people find that it cleans up the code nicely as declarations are all lined up, and it removes unneeded clutter from the code. – Jeff Vanzella Apr 6 '13 at 15:28