How can I create a programmatic solution to a formation of numbers problem?

Question

There is a common formation-of-numbers puzzle in which the solver is supposed to take predetermined collection of numbers, permitted operators, and a desired result; then perform mathematical operations using the permitted operators in such a way that an equality is established between the collection of numbers and the desired result. For example:

Using the numbers 1, 2, 3, and 4, create a mathematical expression that when evaluated would equate to zero. Your permitted operators are +, -, and parenthesis.

A valid example of a solution to this problem is:

(1 + 2 - 3)4

I'm trying to solve this problem programmatically (in C or C++ if possible) but I haven't had any luck sorting it out. In my case, the requirements are as follows:

• Numbers: 1, 2, 3, and 4, in that order (e.g. they cannot be rearranged).
• Operators: +, -, *, /, decimal point, brackets, absolute value, floor, ceiling, and factorial.
  • All operators don't have to be used.
  • I can add any number of brackets.

What is the most efficient way of tackling such a puzzle in a programmatic way?

Answer 1

You can try to generate all possible valid expressions and evaluate them. If the result matches your target value, print it.

How can you generate all expressions? Let's start with a simplified variant of your example:

• The numbers 1, 2, 3, and 4 must all be used in the given order.
• The only allowed operators are the binary operators +, −, × and /.
• A division that leaves a remainder is invalid.
• Numbers cannot be concatenated. No decimal points.

In that case, we get five patterns:

  ((1 ◦ 2) ◦ 3) ◦ 4
  (1 ◦ (2 ◦ 3)) ◦ 4
  (1 ◦ 2) ◦ (3 ◦ 4)
  1 ◦ ((2 ◦ 3) ◦ 4)
  1 ◦ (2 ◦ (3 ◦ 4))

The small circle ◦ represents any of the four valid operators. In your case, you could use these expressions verbatim and cycle through the possible operators. For a more general approach that will make it easier to introduce unary operators later, you could represent the equations in postfix notation.

That notation keeps a stack of operands and operators. The equation in your question becomes:

  (1 + 2 − 3) × 4   →   1 2 add 3 sub 4 mul

Operands are pushed on the stack. Operators (which I'll write as bold words here to distinguish them from the mathematical symbols used in infix notation) pull a number of operands off the stack and calculate a result. That result is pushed onto the stack. In our simplified example, all operators are binary: They pull two operands and push back one operand. If the expression is well formed, there will be a single operand on the stack, the result.

That notation gets rid of parentheses. Instead, the order of evaluation is determined by the position of the operators. Our five cases are now:

  ((1 ◦ 2) ◦ 3) ◦ 4   →   1 2 op 3 op 4 op
  (1 ◦ (2 ◦ 3)) ◦ 4   →   1 2 3 op op 4 op
  (1 ◦ 2) ◦ (3 ◦ 4)   →   1 2 op 3 4 op op
  1 ◦ ((2 ◦ 3) ◦ 4)   →   1 2 3 op 4 op op
  1 ◦ (2 ◦ (3 ◦ 4))   →   1 2 3 4 op op op

Now you can create all expressions recursively: Push openands on the stack in the given order. When there are enough operands to perform a binary operation, try all four operators, too. When there are four operands and three operators on the stack, evaluate the created expression.

Here's one way to code that in C:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <ctype.h>
#include <assert.h>

enum {
    N = 4,              // number of digits in pool
    Error = INT_MIN     // value that signals misevaluation
};

typedef struct Expression Expression;

struct Expression {
    int nums[N];
    int stack[2 * N];
    unsigned nstack;
    unsigned binop;
    unsigned operands;
};

/*
 *      Print expression in Postfix notation
 */
void postfix(const Expression *ex)
{
    for (unsigned i = 0; i < ex->nstack; i++) {
        int c = ex->stack[i];
        
        if (i) putchar(' ');
    
        switch (c) {
        case '+':   printf("add"); break;                    
        case '-':   printf("sub"); break;
        case '*':   printf("mul"); break;
        case '/':   printf("div"); break;

        default:    printf("%d", ex->nums[c - '0']);
                    break;
        }
    }
    
    puts(""); 
}

/*
 *      Evaluate the expression
 */
int evaluate(const Expression *ex)
{
    int res[N];
    unsigned nres = 0;
    
    int a, b;
    unsigned i;
    
    for (i = 0; i < ex->nstack; i++) {
        unsigned char c = ex->stack[i];
    
        switch (c) {
        case '+':   if (nres < 2) return Error;
                    b = res[--nres];
                    a = res[--nres];

                    res[nres++] = a + b;
                    break;
                    
        case '-':   if (nres < 2) return Error;
                    b = res[--nres];
                    a = res[--nres];

                    res[nres++] = a - b;
                    break;

        case '*':   if (nres < 2) return Error;
                    b = res[--nres];
                    a = res[--nres];
                    
                    res[nres++] = a * b;
                    break;

        case '/':   if (nres < 2) return Error;
                    b = res[--nres];
                    a = res[--nres];
                    
                    if (b == 0 || a % b) return Error;
                    res[nres++] = a / b;
                    break;

        default:    if (isdigit(c) == 0) return Error;

                    res[nres++] = ex->nums[c - '0'];
                    break;
        }
    }
    
    return (nres == 1) ? res[0] : Error;
}

/*
 *      Recursively create and evaluate all expressions
 */
unsigned solve(Expression *ex, int target)
{
    unsigned res = 0;

    if (ex->operands == N && ex->binop == N - 1) {
        int res = evaluate(ex);
        
        if (res == target) {
            postfix(ex);
            infix(ex);
            return 1;
        }
        
        return 0;
    }
    
    if (ex->operands > ex->binop + 1) {
        unsigned i = ex->nstack;
        
        ex->nstack++;
        ex->binop++;
        
        ex->stack[i] = '+'; res += solve(ex, target);
        ex->stack[i] = '-'; res += solve(ex, target);
        ex->stack[i] = '*'; res += solve(ex, target);
        ex->stack[i] = '/'; res += solve(ex, target);
        
        ex->binop--;
        ex->nstack--;
    }
    
    if (ex->operands < N) {
        ex->stack[ex->nstack++] = '0' + ex->operands++;

        res += solve(ex, target);
        
        ex->nstack--;
        ex->operands--;
    }
    
    return res;
}

/*
 *      Example code
 */
int main(void)
{
    Expression ex = {{1, 2, 3, 4}};    
    unsigned n = solve(&ex, 0);
    
    printf("%u solutions.\n", n);

    return 0;
}

If we run that code, it prints:

1 2 add 3 sub 4 mul
1 2 add 3 sub 4 div
1 2 sub 3 sub 4 add
1 2 sub 3 4 sub sub
1 2 3 add sub 4 add
1 2 3 add 4 sub sub
1 2 3 sub add 4 mul
1 2 3 sub add 4 div
1 2 3 4 sub add sub
9 solutions.

But we want the output to be in the more common infix notation. This is usually done by representing the expression as a tree and then traversing the tree in order, e.g.:

    1 2 add 3 sub 4 mul            1 2 sub 3 4 sub sub

              *                           -
            /   \                       /   \
          -      4                    +       -
        /   \                        / \     / \
       +     3                      1   2   3   4
     /   \
    1     2

   (1 + 2 - 3) * 4                  1 + 2 - (3 - 4)

The postfix expression is on top. In the middle, there is the respective tree representation from which one can get the infix notation at the bottom.

Creating the tree works like evaluating the expression, but instead of pushing back the calculated result, push back a node that holds the operator with the operand nodes as its children. At the end, there's only one item left on the stack, the root node.

You could print parentheses around every level of the tree, but such expressions would not look natural. If you know the precendecce of each operator – how tightly it binds its operands – you can omit them where they aren't needed: (1) + ((2)·(3)) is written more naturally as just 1 + 2·3. Operands (numbers) have a high precedence, so they don't get parentheses around them.

Add this to the program above for infix notation:

typedef struct Node Node;

struct Node {
    const int *ref;
    Node *left;
    Node *right;
};

/*
 *      Operator precedence of node; higher binds tighter
 */
int precedence(const Node *node)
{
    if (node) {
        switch (*node->ref) {
        case '+':       return 2;
        case '-':       return 2;
        case '*':       return 4;
        case '/':       return 4;
        default:        return 6;
        }
    }
    
    return 0;
}

/*
 *      Recursive infix printing back-end
 */
void infix_rec(const Expression *ex, const Node *node, int pprec)
{
    if (node) {
        unsigned char c = *node->ref;
        int leaf = isdigit(c);
        int prec = precedence(node);
        int asymm = (c == '-' || c == '/');
    
        if (prec < pprec) putchar('(');
        infix_rec(ex, node->left, prec);
        
        if (leaf) {
            printf("%d", ex->nums[c - '0']);
        } else {
            printf(" %c ", c);
        }
        
        infix_rec(ex, node->right, prec + asymm);
        if (prec < pprec) putchar(')');
    }
}

/*
 *      Print expression in infix notation
 */
void infix(const Expression *ex)
{
    Node node[2*N];
    Node *stack[2*N];
    unsigned nstack = 0;
    unsigned i;
    
    for (i = 0; i < ex->nstack; i++) {
        node[i].ref = ex->stack + i;
        node[i].left = NULL;
        node[i].right = NULL;
    }
    
    for (i = 0; i < ex->nstack; i++) {
        unsigned char c = ex->stack[i];
        Node *n = node + i;
        
        if (isdigit(c) == 0) {
            n->right = stack[--nstack];
            n->left = stack[--nstack];
        }

        stack[nstack++] = n;
    }
    
    assert(nstack == 1);
    
    infix_rec(ex, stack[0], 0);
    puts(""); 
}

That should give you a base for further additions. Things to ponder:

• You have to decide how to treat division. Do you use floating-point numbers with their known issues or do you implement rational numbers?

• You can treat concatenation as binary operator: 1 2 cat → 12, but you must make sure that you concatenate only original numbers, not the result of previous calculations.

• The same goes for the decimal point, but it can come only between original numbers or results from concatenation: 1 2 cat 3 period → 12.3.

• You can add unary operators or functions like −x; |x|, x!, sqrt(x) and so on when there is at least one operand on the stack. Be careful, though: Because unary operatore leave the number of operands on the stack unchanged – they exchange their single operand with the result – you can use infinitely many of them. You will need some restriction.

• The implementation above is wasteful: It creates all expressions and then evaluates each, starting from the beginning. It doesn't hurt with the small example, but if you use more numbers and operators, you will run into performance problems. In addition to the full stack, which you need for printing the expression, you could keep a value stack.

  Being able to see the intermediate results of your calculations, you can also omit some operators: Don't push div if the tast operand is a zero; don't push abs if it's not negative; don't push floor or ceil if it doesn't have a fractional part and so on. This should cut many dead paths short.

• You must also decide how you will handle errors. Most importantly, don't overflow the stack. (The C code above uses a fixed-size stack. You can save yourself a lot of pain by using C++ standard containers instead.)

With a bit of luck, you have your formation-of-number too ready by New Year's Eve, when there traditionally is a slew of puzzles asking you to make 2022 from this bag of digits and this bag of operators. Happy coding!

Answer 2

Unfortunately, brute force is the way to go.

---

Solving the problem with brute force will require two steps:

• Generate all possible expressions.
• Test all possible expressions.

This may sound redundant to mention, but I do so for a very specific reason. You can focus your code on brute forcing the first step and then writing the generated expressions to a file in a way that can be interpreted by a programming language of your choosing. For example, if I limit myself to the following:

• Numbers: 1 and 2
• Operators: $+$ and $-$

The collection of possible expressions is:

1 + 2
1 - 2
2 + 1
2 - 1

Instead of simply outputting the expression, it can be written as a conditional execution; for example:

if (expression == desiredResult)
    cout << "expression";

Here, you'd replace expression with one of the possible expressions and desiredResult with the desired result, respectively. As such, the output file would be:

if (1 + 2 == 3)
    cout << "1 + 2";
if (1 - 2 == 3)
    cout << "1 - 2";
if (2 + 1 == 3)
    cout << "2 + 1";
if (2 - 1 == 3)
    cout << "2 - 1";

This will at least simplify the second step tremendously for you. Unfortunately, to perform the second step in the same process as the first, you'll have to create a miniature interpreted language, which is likely much more work than you're bargaining for when it comes to solving such a simple puzzle.

If you're interested in learning about creating your own interpreter to pursue step 2 in the same process, then here is a good article on the topic, though it uses C#.