How to find the exact set of operations for a specific number?

Question

I am trying to implement a program that answers this problem :

if you are given a specific number (for example : 268)
and another 6 numbers (for example : 2,4,5,25,75,100)

How can I find the operation that gives me the exact answer or the closest one to it?

You can answer the previous example by using this operation : 75*4-25-5-2 = 268

---

Rules :

1. you can use these arithmetic operations : +, -, *, / , ().
2. when you use division the reminder must be equal to 0 (6/3 is ok but 6/4 is not ok!).
3. you can not use the same number more than once. Also, you can avoid using a number (for example : 100 in our previous example).

Is there is any better solution than writing the whole possibilities and taking the closest one? Because this answer would force me to write too many lines of code, thanks!

Decigram

The brute-force solution isn't that many lines of code, probably less than a faster solution. – Willman

If the task is to find the best answer, then you have to go through all the possibilities, just enhance you code with as many if statements as possible to avoid some useless computations. – Cytosine

Do you always get 6 numbers to produce the first one? Also, merely out of curiosity, in what context does this problem arise? – Edenedens

@G.Bach you always get 6 numbers and one result. I found this problem in a mathematical bot that gives you such a question and ask you to find the operation. I found it interesting to solve this problem by a program. – Decigram

if your answer demands you to write too many lines of code, than you`re on the wrong path – Rothermere

Answer 1

In fact, the brute force solution really isn't so much code

(EDIT: Changed the code slightly, because some of the rules had not been properly taken into account)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NumberPuzzle
{
    public static void main(String[] args)
    {
        List<Integer> numbers = Arrays.asList(2,4,5,25,75,100); 
        Integer result = 268;
        solve(numbers, result);
    }

    private static void solve(List<Integer> numbers, Integer result)
    {
        List<Node> nodes = new ArrayList<Node>();
        for (int i=0; i<numbers.size(); i++)
        {
            Integer number = numbers.get(i);
            nodes.add(new Node(number));
        }
        System.out.println(nodes);


        List<Node> all = create(nodes);
        System.out.println("Found "+all.size()+" combinations");

        List<Node> best = new ArrayList<Node>();
        Integer minDifference = Integer.MAX_VALUE;
        for (Node n : all)
        {
            //System.out.println(n);
            Integer e = n.evaluate();
            Integer difference = Math.abs(e - result); 
            if (difference < minDifference)
            {
                best.clear();
                minDifference = difference;
                best.add(n);
            }
            else if (difference.equals(minDifference))
            {
                best.add(n);
            }
        }

        for (Node n : best)
        {
            System.out.println(n+" = "+n.evaluate());
        }
    }

    private static List<Node> create(List<Node> nodes)
    {
        if (nodes.size() == 1)
        {
            return nodes;
        }
        List<Node> result = new ArrayList<Node>(nodes);
        for (int i=0; i<nodes.size(); i++)
        {
            List<Node> copy = new ArrayList<Node>(nodes);
            Node node = copy.remove(i);
            List<Node> others = create(copy);
            for (int j=0; j<others.size(); j++)
            {
                Node other = others.get(j);
                result.add(new Node(node, '+', other));
                result.add(new Node(node, '*', other));
                result.add(new Node(node, '-', other));
                result.add(new Node(other, '-', node));

                Integer vNode = node.evaluate();
                Integer vOther = other.evaluate();
                if (vOther != 0 && vNode % vOther == 0)
                {
                    result.add(new Node(node, '/', other));
                }
                if (vNode != 0 && vOther % vNode == 0)
                {
                    result.add(new Node(other, '/', node));
                }
            }
        }
        return result;
    }

    static class Node
    {
        Integer value;
        Node left;
        Character op;
        Node right;

        Node(Node left, Character op, Node right)
        {
            this.left = left;
            this.op = op;
            this.right = right;
        }
        Node(Integer value)
        {
            this.value = value;
        }

        Integer evaluate()
        {
            if (op != null)
            {
                Integer lv = left.evaluate();
                Integer rv = right.evaluate();
                switch (op)
                {
                    case '+': return lv + rv;
                    case '-': return lv - rv;
                    case '*': return lv * rv;
                    case '/': return rv.equals(0) ? Integer.MAX_VALUE : lv / rv;
                }
            }
            return value;
        }

        @Override
        public String toString()
        {
            if (op == null)
            {
                return String.valueOf(value);
            }
            return "("+left.toString()+op+right.toString()+")";
        }
    }
}

It finds quite some solutions....

(EDIT: Updated according to the changed code)

(2*(4+(5+(25+100)))) = 268
(2*(4+(5+(100+25)))) = 268
(2*(4+(25+(5+100)))) = 268
(2*(4+(25+(100+5)))) = 268
(2*(4+(100+(5+25)))) = 268
(2*(4+(100+(25+5)))) = 268
((5*(4-(25-75)))-2) = 268
((5*(4+(75-25)))-2) = 268
(2*(5+(4+(25+100)))) = 268
((5*(4+(25-(75-100))))-2) = 268
((5*(4-((75-100)-25)))-2) = 268
((5*(4+(25+(100-75))))-2) = 268
((5*(4+(25+(100-75))))-2) = 268
((5*(4+(25-(75-100))))-2) = 268
((5*(4-((75-100)-25)))-2) = 268
((5*(4+(75-25)))-2) = 268
((5*(4-(25-75)))-2) = 268
((5*(4-(75-(25+100))))-2) = 268
((5*(4+((25+100)-75)))-2) = 268
((5*(4-(75-(100+25))))-2) = 268
((5*(4+((100+25)-75)))-2) = 268
(2*(5+(4+(100+25)))) = 268
((5*(4+(100+(25-75))))-2) = 268
((5*(4+(100-(75-25))))-2) = 268
((5*(4-((75-25)-100)))-2) = 268
((5*(4+(100-(75-25))))-2) = 268
((5*(4-((75-25)-100)))-2) = 268
((5*(4+(100+(25-75))))-2) = 268
((5*((4+75)-25))-2) = 268
((((4*75)-25)-5)-2) = 268
(2*(5+(25+(4+100)))) = 268
((5*(25+(4-(75-100))))-2) = 268
((5*(25-((75-100)-4)))-2) = 268
((5*(25+(4+(100-75))))-2) = 268
((5*(25+(4+(100-75))))-2) = 268
((5*(25+(4-(75-100))))-2) = 268
((5*(25-((75-100)-4)))-2) = 268
((5*((75+4)-25))-2) = 268
((((75*4)-25)-5)-2) = 268
((5*(25-(75-(4+100))))-2) = 268
((5*(25+((4+100)-75)))-2) = 268
((5*(25-(75-(100+4))))-2) = 268
((5*(25+((100+4)-75)))-2) = 268
(2*(5+(25+(100+4)))) = 268
((5*(25+(100+(4-75))))-2) = 268
((5*(25+(100-(75-4))))-2) = 268
((5*(25-((75-4)-100)))-2) = 268
((5*(25+(100-(75-4))))-2) = 268
((5*(25-((75-4)-100)))-2) = 268
((5*(25+(100+(4-75))))-2) = 268
((5*(75+(4-25)))-2) = 268
((5*(75-(25-4)))-2) = 268
((5*((4+(25+100))-75))-2) = 268
((5*((4+(100+25))-75))-2) = 268
((5*(75-(25-4)))-2) = 268
((5*(75+(4-25)))-2) = 268
((5*((25+(4+100))-75))-2) = 268
((5*((25+(100+4))-75))-2) = 268
((5*((100+(4+25))-75))-2) = 268
(((75+(100+(4*25)))-5)-2) = 268
((5*((100+(25+4))-75))-2) = 268
(((75+(100+(25*4)))-5)-2) = 268
(2*(5+(100+(4+25)))) = 268
((5*(100+(4+(25-75))))-2) = 268
((5*(100+(4-(75-25))))-2) = 268
((5*(100-((75-25)-4)))-2) = 268
((5*(100+(4-(75-25))))-2) = 268
((5*(100-((75-25)-4)))-2) = 268
((5*(100+(4+(25-75))))-2) = 268
(2*(5+(100+(25+4)))) = 268
((5*(100+(25+(4-75))))-2) = 268
((5*(100+(25-(75-4))))-2) = 268
((5*(100-((75-4)-25)))-2) = 268
((5*(100+(25-(75-4))))-2) = 268
((5*(100-((75-4)-25)))-2) = 268
((5*(100+(25+(4-75))))-2) = 268
((5*(100-(75-(4+25))))-2) = 268
((5*(100+((4+25)-75)))-2) = 268
(((100+(75+(4*25)))-5)-2) = 268
((5*(100-(75-(25+4))))-2) = 268
((5*(100+((25+4)-75)))-2) = 268
(((100+(75+(25*4)))-5)-2) = 268
(2*(25+(4+(5+100)))) = 268
(2*(25+(4+(100+5)))) = 268
((((4*75)-5)-25)-2) = 268
(2*(25+(5+(4+100)))) = 268
((((75*4)-5)-25)-2) = 268
(2*(25+(5+(100+4)))) = 268
(2*(25+(100+(4+5)))) = 268
(2*(25+(100+(5+4)))) = 268
((((5*(4+75))-100)-25)-2) = 268
((((5*(75+4))-100)-25)-2) = 268
((75-(5-(100+(4*25))))-2) = 268
((75+((100+(4*25))-5))-2) = 268
((75-(5-(100+(25*4))))-2) = 268
((75+((100+(25*4))-5))-2) = 268
((75+(100-(5-(4*25))))-2) = 268
((75-((5-(4*25))-100))-2) = 268
((75+(100+((4*25)-5)))-2) = 268
((75+(100-(5-(25*4))))-2) = 268
((75-((5-(25*4))-100))-2) = 268
((75+(100+((25*4)-5)))-2) = 268
(2*(100+(4+(5+25)))) = 268
(2*(100+(4+(25+5)))) = 268
(2*(100+(5+(4+25)))) = 268
(2*(100+(5+(25+4)))) = 268
((100-(5-(75+(4*25))))-2) = 268
((100+((75+(4*25))-5))-2) = 268
((100-(5-(75+(25*4))))-2) = 268
((100+((75+(25*4))-5))-2) = 268
(2*(100+(25+(4+5)))) = 268
(2*(100+(25+(5+4)))) = 268
((((5*(4+75))-25)-100)-2) = 268
((((5*(75+4))-25)-100)-2) = 268
((100+(75-(5-(4*25))))-2) = 268
((100-((5-(4*25))-75))-2) = 268
((100+(75+((4*25)-5)))-2) = 268
((100+(75-(5-(25*4))))-2) = 268
((100-((5-(25*4))-75))-2) = 268
((100+(75+((25*4)-5)))-2) = 268
(((100*((75-5)-2))/25)-4) = 268
(((100*((75-5)-2))/25)-4) = 268
(((100*((75-2)-5))/25)-4) = 268
(((100*((75-2)-5))/25)-4) = 268
(((100*(75-(2+5)))/25)-4) = 268
(((100*(75-(5+2)))/25)-4) = 268
(4*(75-(2*(100/25)))) = 268
(4*(75-(2*(100/25)))) = 268
(4*(75-((2*100)/25))) = 268
(4*(75-((100*2)/25))) = 268
((((4*75)-25)-2)-5) = 268
((((75*4)-25)-2)-5) = 268
(((75+(100+(4*25)))-2)-5) = 268
(((75+(100+(25*4)))-2)-5) = 268
(((100+(75+(4*25)))-2)-5) = 268
(((100+(75+(25*4)))-2)-5) = 268
((((4*75)-2)-25)-5) = 268
((((75*4)-2)-25)-5) = 268
((75-(2-(100+(4*25))))-5) = 268
((75+((100+(4*25))-2))-5) = 268
((75-(2-(100+(25*4))))-5) = 268
((75+((100+(25*4))-2))-5) = 268
((75+(100-(2-(4*25))))-5) = 268
((75-((2-(4*25))-100))-5) = 268
((75+(100+((4*25)-2)))-5) = 268
((75+(100-(2-(25*4))))-5) = 268
((75-((2-(25*4))-100))-5) = 268
((75+(100+((25*4)-2)))-5) = 268
((100-(2-(75+(4*25))))-5) = 268
((100+((75+(4*25))-2))-5) = 268
((100-(2-(75+(25*4))))-5) = 268
((100+((75+(25*4))-2))-5) = 268
((100+(75-(2-(4*25))))-5) = 268
((100-((2-(4*25))-75))-5) = 268
((100+(75+((4*25)-2)))-5) = 268
((100+(75-(2-(25*4))))-5) = 268
((100-((2-(25*4))-75))-5) = 268
((100+(75+((25*4)-2)))-5) = 268
((((4*75)-5)-2)-25) = 268
((((75*4)-5)-2)-25) = 268
((((5*(4+75))-100)-2)-25) = 268
((((5*(75+4))-100)-2)-25) = 268
((((4*75)-2)-5)-25) = 268
((((75*4)-2)-5)-25) = 268
((75+(2*(4+(5+100))))-25) = 268
((75+(2*(4+(100+5))))-25) = 268
((75+(2*(5+(4+100))))-25) = 268
((75+(2*(5+(100+4))))-25) = 268
((75+(2*(100+(4+5))))-25) = 268
((75+(2*(100+(5+4))))-25) = 268
((((5*(4+75))-2)-100)-25) = 268
((((5*(75+4))-2)-100)-25) = 268
((100*(75-(2*4)))/25) = 268
((100*(75-(4*2)))/25) = 268
(75-(2+(5-(100+(4*25))))) = 268
(75-(2-((100+(4*25))-5))) = 268
(75+(((100+(4*25))-5)-2)) = 268
(75-(2+(5-(100+(25*4))))) = 268
(75-(2-((100+(25*4))-5))) = 268
(75+(((100+(25*4))-5)-2)) = 268
(75-(2-(100-(5-(4*25))))) = 268
(75+((100-(5-(4*25)))-2)) = 268
(75-(2+((5-(4*25))-100))) = 268
(75-(2-(100+((4*25)-5)))) = 268
(75+((100+((4*25)-5))-2)) = 268
(75-(2-(100-(5-(25*4))))) = 268
(75+((100-(5-(25*4)))-2)) = 268
(75-(2+((5-(25*4))-100))) = 268
(75-(2-(100+((25*4)-5)))) = 268
(75+((100+((25*4)-5))-2)) = 268
(75-(5+(2-(100+(4*25))))) = 268
(75-(5-((100+(4*25))-2))) = 268
(75+(((100+(4*25))-2)-5)) = 268
(75-(5+(2-(100+(25*4))))) = 268
(75-(5-((100+(25*4))-2))) = 268
(75+(((100+(25*4))-2)-5)) = 268
(75-(5-(100-(2-(4*25))))) = 268
(75+((100-(2-(4*25)))-5)) = 268
(75-(5+((2-(4*25))-100))) = 268
(75-(5-(100+((4*25)-2)))) = 268
(75+((100+((4*25)-2))-5)) = 268
(75-(5-(100-(2-(25*4))))) = 268
(75+((100-(2-(25*4)))-5)) = 268
(75-(5+((2-(25*4))-100))) = 268
(75-(5-(100+((25*4)-2)))) = 268
(75+((100+((25*4)-2))-5)) = 268
(75-(25-(2*(4+(5+100))))) = 268
(75+((2*(4+(5+100)))-25)) = 268
(75-(25-(2*(4+(100+5))))) = 268
(75+((2*(4+(100+5)))-25)) = 268
(75-(25-(2*(5+(4+100))))) = 268
(75+((2*(5+(4+100)))-25)) = 268
(75-(25-(2*(5+(100+4))))) = 268
(75+((2*(5+(100+4)))-25)) = 268
(75-(25-(2*(100+(4+5))))) = 268
(75+((2*(100+(4+5)))-25)) = 268
(75-(25-(2*(100+(5+4))))) = 268
(75+((2*(100+(5+4)))-25)) = 268
(75+(100-(2+(5-(4*25))))) = 268
(75-((2+(5-(4*25)))-100)) = 268
(75+(100-(2-((4*25)-5)))) = 268
(75-((2-((4*25)-5))-100)) = 268
(75+(100+(((4*25)-5)-2))) = 268
(75+(100-(2+(5-(25*4))))) = 268
(75-((2+(5-(25*4)))-100)) = 268
(75+(100-(2-((25*4)-5)))) = 268
(75-((2-((25*4)-5))-100)) = 268
(75+(100+(((25*4)-5)-2))) = 268
(75+(100-(5+(2-(4*25))))) = 268
(75-((5+(2-(4*25)))-100)) = 268
(75+(100-(5-((4*25)-2)))) = 268
(75-((5-((4*25)-2))-100)) = 268
(75+(100+(((4*25)-2)-5))) = 268
(75+(100-(5+(2-(25*4))))) = 268
(75-((5+(2-(25*4)))-100)) = 268
(75+(100-(5-((25*4)-2)))) = 268
(75-((5-((25*4)-2))-100)) = 268
(75+(100+(((25*4)-2)-5))) = 268
(100+(2*(4+(5+75)))) = 268
(100+(2*(4+(75+5)))) = 268
(100+(2*(4+(75+(25/5))))) = 268
(100+(2*(4+(75+(25/5))))) = 268
(100+(2*(5+(4+75)))) = 268
(100+(2*(5+(75+4)))) = 268
(100-(2+(5-(75+(4*25))))) = 268
(100-(2-((75+(4*25))-5))) = 268
(100+(((75+(4*25))-5)-2)) = 268
(100-(2+(5-(75+(25*4))))) = 268
(100-(2-((75+(25*4))-5))) = 268
(100+(((75+(25*4))-5)-2)) = 268
((((5*(4+75))-25)-2)-100) = 268
((((5*(75+4))-25)-2)-100) = 268
(100+(2*(75+(4+5)))) = 268
(100+(2*(75+(4+(25/5))))) = 268
(100+(2*(75+(4+(25/5))))) = 268
(100+(2*(75+(5+4)))) = 268
(100-(2-(75-(5-(4*25))))) = 268
(100+((75-(5-(4*25)))-2)) = 268
(100-(2+((5-(4*25))-75))) = 268
(100-(2-(75+((4*25)-5)))) = 268
(100+((75+((4*25)-5))-2)) = 268
(100-(2-(75-(5-(25*4))))) = 268
(100+((75-(5-(25*4)))-2)) = 268
(100-(2+((5-(25*4))-75))) = 268
(100-(2-(75+((25*4)-5)))) = 268
(100+((75+((25*4)-5))-2)) = 268
(100+(4*(2+(25+(75/5))))) = 268
(100+(4*(2+(25+(75/5))))) = 268
(100+(4*(25+(2+(75/5))))) = 268
(100+(4*(25+(2+(75/5))))) = 268
(100-(5+(2-(75+(4*25))))) = 268
(100-(5-((75+(4*25))-2))) = 268
(100+(((75+(4*25))-2)-5)) = 268
(100-(5+(2-(75+(25*4))))) = 268
(100-(5-((75+(25*4))-2))) = 268
(100+(((75+(25*4))-2)-5)) = 268
(100-(5-(75-(2-(4*25))))) = 268
(100+((75-(2-(4*25)))-5)) = 268
(100-(5+((2-(4*25))-75))) = 268
(100-(5-(75+((4*25)-2)))) = 268
(100+((75+((4*25)-2))-5)) = 268
(100-(5-(75-(2-(25*4))))) = 268
(100+((75-(2-(25*4)))-5)) = 268
(100-(5+((2-(25*4))-75))) = 268
(100-(5-(75+((25*4)-2)))) = 268
(100+((75+((25*4)-2))-5)) = 268
((((5*(4+75))-2)-25)-100) = 268
((((5*(75+4))-2)-25)-100) = 268
(100+(75-(2+(5-(4*25))))) = 268
(100-((2+(5-(4*25)))-75)) = 268
(100+(75-(2-((4*25)-5)))) = 268
(100-((2-((4*25)-5))-75)) = 268
(100+(75+(((4*25)-5)-2))) = 268
(100+(75-(2+(5-(25*4))))) = 268
(100-((2+(5-(25*4)))-75)) = 268
(100+(75-(2-((25*4)-5)))) = 268
(100-((2-((25*4)-5))-75)) = 268
(100+(75+(((25*4)-5)-2))) = 268
(100+(75-(5+(2-(4*25))))) = 268
(100-((5+(2-(4*25)))-75)) = 268
(100+(75-(5-((4*25)-2)))) = 268
(100-((5-((4*25)-2))-75)) = 268
(100+(75+(((4*25)-2)-5))) = 268
(100+(75-(5+(2-(25*4))))) = 268
(100-((5+(2-(25*4)))-75)) = 268
(100+(75-(5-((25*4)-2)))) = 268
(100-((5-((25*4)-2))-75)) = 268
(100+(75+(((25*4)-2)-5))) = 268

but of course, MANY of these are redundant due to commutativity.

One could easily avoid many of the solutions that are checked in the brute-force variant. One of the first steps could be to avoid the creation of nodes that contain commutative elements, and possibly implement an equals method for the quick-and-dirty Node class that I sketched there, which takes commutativity into account, and then use Sets of Nodes instead of the List. And further, "simple", "low level" optimizations may be possible as well (e.g. an early return when a perfect match is found).

And concerning your actual question, whether there is a solution that is "better" than brute force: My gut-feeling is that the answer is "no", but this depends on which problem should be solved. The key point is here: Assume that you are given a list of available numbers, and a desired result value. And assume, that it is not possible to create the result value from the given input values. E.g. when you have

input = { 1,2,3,4,5,6 }
result = 10000000000;

I think that in order to really prove that this is not possible, you have to enumerate all combinations (returning the "best" one in the end, which here will probably be 1*2*3*4*5*6). If you skip any combination, how should you be sure that it was not exactly the best one?

But again: This is just a gut feeling. Maybe someone who is more ... mathematically involved ... can prove me wrong ....

Wellspoken

OP's second rule says to only permit division with no remainder. – Lox

Yes, sorry, I already added an EDIT at the top mentioning that I overlooked this, I'll adjust the code accordingly – Wellspoken

Since for a,b >= 2 we always have ab >= a + b, the largest possible value you can get from those you give is (1+2)*3*4*5*6. Since that is smaller than 10^10, this is proof enough that you can't "build" that value from the ones given. – Edenedens

Tried it out (that's what programs are made for :D) and of course, you're right: 6*(5*(4*(3*(2+1))))) = 1080 is the maximum. However, a statement like this can hardly be generalized (or at least I assume that one could quickly get in touch with the nitty-gritty bits of number theory there...) – Wellspoken

It's a bit difficult to tell whether negative input values are allowed and whether we can use unary - (i.e. multiply with -1) or not. If fractions are allowed, it'll be more difficult to find a maximum, too, I think. – Edenedens