Geek Answers Handbook

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

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

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

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

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

Rules:

  • you can use these arithmetic operations: +, -, *, /, ().
  • when you use division, the reminder should be 0 (6/3 is fine, but 6/4 is not ok!).
  • You cannot use the same number more than once. In addition, you can avoid using a number (for example: 100 in our previous example).

Is there a better solution than writing all the possibilities and taking the closest? Since this answer made me write too many lines of code, thanks!

+4
java math algorithm puzzle discrete-mathematics
source share
1 answer

In fact, brute force decision is really not so much code

(EDIT: changed the code a bit because some of the rules were incorrectly 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()+")"; } } }

He finds quite some solutions ....

(EDIT: Updated according to modified 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 them are redundant due to commutativity.

Many solutions tested in brute force variant can easily be avoided. One of the first steps may be to avoid creating nodes containing commutative elements, and perhaps implement the equals method for the quick and dirty Node class that I sketched there that takes into account commutativity, and then use the Set nodes, not List . And, besides, “simple”, “low-level” optimization is possible (for example, early return when an ideal match is found).

And regarding your actual question, is there a solution that is “better” than brute force: my gut feeling is that the answer is “no,” but it depends on what problem needs to be solved. The key point here is: Suppose you are presented with a list of available numbers and the desired value of the result. And suppose it is not possible to create a result value from given input values. For example. when you have

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

I think that in order to really prove that this is impossible, you have to list all the combinations (returning the "best" at the end, which is likely to be 1*2*3*4*5*6 ). If you miss any combination , how should you be sure that it is not the best?

But then again: it's just a gut feeling. Maybe someone who is more ... mathematically involved ... can prove that I'm wrong ....

+7
source share

More articles:


All Articles