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!

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 ....