A function to find all possible Expressions which results in a specific number let's say 42?

Question

There is a Game in which they give us some Slots. Some of them are filled with numbers and some are empty. We have to fill the empty Slot with correct Mathematical Operator like +, -, * and /so that when the expression as a whole is evaluated It is always equal to 10. For example:

9 _ 1 = 10
5 _ 2 = 10
3 _ 2 _ 2 = 10

Note that "_" indicates the empty slot. We have to fill these slots with any mathematical operator to make it equal to 10.

My question is, How can I find all the expressions which results in 42 so I can dynamically generate the expressions through Code rather than writing hundreds of expressions myself before hand?

Like I call a function GenerateExpressions(operatorsCount, result) and it gives me back a list of all the possible expressions which evaluates to result.

For Example if I pass 3 as operatorsCount and 42 as result, the function will give me a list of expressions that looks like this: N o N o N o N where "o" is any mathematical operator i.e., +, -, * or / and N is any number between 1 to 9 and the Expression will evaluate to 42. Or if I pass it 4 as operatorsCount and 10 as result, the function will give me a list of expressions that looks like this: N o N o N o N o N where "o" is any mathematical operator i.e., +, -, * or / and N is any number between 1 to 9 and the Expression will evaluate to 10.

I've tried to generate all possible equations using nested loops and then checking each of them whether or not it equals to my result e.g. 42 or not. But It caused out of memory exceptions on every test and also this is not a good solution to brute force all possible combinations.

Edit: Okay, I've changed my approach from Nested loops to Recursive functions and now it's not giving that exception. But still, this is very inefficient solution. I'm using DataTable.Compute method to evaluate and check the expressions.

public static List<string> GenerateExpressions(int count)
    {
        List<string> expressions = new List<string>();
        List<string> numbers = new List<string> { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
        List<string> operators = new List<string> { "+", "-", "*", "/" };

        for (int i = 0; i < numbers.Count; i++)
        {
            GenerateExpressionsHelper(expressions, numbers, operators, count, numbers[i]);
        }
        return expressions;
    }

    static void GenerateExpressionsHelper(List<string> expressions, List<string> numbers, List<string> operators, int count, string currentExpression)
    {
        if (count == 0)
        {
            // If we have used all operators, add the expression to the list
            expressions.Add(currentExpression);
            return;
        }

        for (int i = 0; i < operators.Count; i++)
        {
            for (int j = 0; j < numbers.Count; j++)
            {
                // Recursively call the function with one operator and one number less
                GenerateExpressionsHelper(expressions, numbers, operators, count - 1, currentExpression + operators[i] + numbers[j]);
            }
        }
    }

Answer 1

You can think about this problem in a recursive fashion:

func GenerateExpressions(opCount, result, path):
    if opCount == 0:
        path += [result]
        add path to ans
        return

    for i in range [1,9]:
        for op in [+,-,*,/]:
            # assuming the form (i op y) = result, calculate() function gives the value of y
            y = calculate(result, i, op)

            GenerateExpressions(opCount - 1, y, path + [i, op])
            

You should note here that GenerateExpressions(opCount, result) has recursive subcalls, which can be memoized using a 2D table. This should allow you to build the solution using a bottom-up approach.

Answer 2

Just some tweaks to your code, to store only the expressions that result in the target value

void Main()
{
    GenerateExpressions(4, 42).Dump();
    // NB 'Dump()' is a LINQPad extension method to print the results
}

// a DataTable to call Compute() on - just need one instance
static DataTable dataTable = new();

public static List<string> GenerateExpressions(int count, int target)
{
    List<string> expressions = new List<string>();
    List<string> numbers = new List<string> { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
    List<string> operators = new List<string> { "+", "-", "*", "/" };

    for (int i = 0; i < numbers.Count; i++)
    {
        GenerateExpressionsHelper(expressions, numbers, operators, count, numbers[i], target);
    }
    return expressions;
}

static void GenerateExpressionsHelper(List<string> expressions, List<string> numbers, List<string> operators, int count, string currentExpression, int target)
{
    if (count == 0)
    {
        // If we have used all operators, add the expression to the list, ONLY WHEN it results in the target value
        // EDIT use Convert.ToDecimal to better match the result of Compute
        if (Convert.ToDecimal(dataTable.Compute(currentExpression, null)) == target)
        {
            expressions.Add(currentExpression);
        }
        return;
    }

    for (int i = 0; i < operators.Count; i++)
    {
        for (int j = 0; j < numbers.Count; j++)
        {
            // Recursively call the function with one operator and one number less
            GenerateExpressionsHelper(expressions, numbers, operators, count - 1, currentExpression + operators[i] + numbers[j], target);
        }
    }
}

This took my machine 24 seconds to deliver 35_696 results, like

1+1+1*5*8
1+1+1*8*5
1+1+2*4*5
1+1+2*5*4
1+1+4+4*9
1+1+4+6*6
1+1+4+9*4
// etc

Do note that the value you add to expressions is also visible to previous iterations when you return there.