java - 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-(