An algorithm for finding combinations of integers and any operand to obtain a fixed result

Question

I write a program that takes 4 numbers as input, and then tries to figure out if a combination of division addition and multiplication of four numbers can make them equal 24. My path created a method for every possible combination of four numbers and four operands, which is a bit verbose . Here is an example of 2 methods.

public static boolean add(int a, int b, int c, int d){ boolean adBool; adBool = a + b + c + d == 24; return adBool; } public static boolean sub1(int a, int b, int c, int d){ boolean subBool1; subBool1 = a - b - c - d == 24; return subBool1; } 

Then, in my main, I create a while loop for each method, which, if the method returns true, will print that the method it stopped at was a solution. Here is an example.

 while (add(num1, num2, num3, num4)){ System.out.println("Your solution is " + num1 + " + " + num2 + " + " + num3 + " + " + num4 + " = 24\nCongratulations!"); break; } while (sub1(num1, num2, num3, num4)){ System.out.println("Your solution is " + num1 + " - " + num2 + " - " + num3 + " - " + num4 + " = 24\nCongratulations!"); break; } 

Is there a way to store operands such as + and - so that I can put them in an array and just use some nested loops for writing?

Answer 1

Assuming the operands are fixed, you can create a generator that unloads the possible operators and pass them to the evaluator to determine if they are true.

 while (generator.hasNext()){ Operators ops = generator.getNext(); if evaluatesTo(operand1, operand2, operand3, operand4, 24, ops){ // print it } } 

A simple generator can be performed as follows:

 List<String> list = new ArrayList<String>(); list.add("+++"); list.add("++-"); ... Iterator generator = list.iterator(); 

where the generator implements the java.util.Iterator interface, which initializes all the operators (+ - * /) and unloads all permutations of size 3.

The evalutesTo method simply calculates it:

 public boolean (int operand1, int operand2, int operand3, int operand4, int total, Operators ops ){ // calculate operand1 "ops.get(0)" operand2 "ops.get(1)" operand3 "ops.get(2)" operand4 == total } 

So if ops [+ - /], it will check

 if (operand1 + operand2 - operand3 / operand4 == 24) return true; 

I have to add there all kinds of efficiency that you can add later, but you doubt how you can do this with a better strategy. There are a few comments about the details from other users, but I would not worry about that now. First you need to configure this kind of framework, then you can worry about the details. The key point in this is that you do not need to create 100 similar methods.

Answer 2

I have done something for you.
I found this stackexchange question to find out how to create all possible combinations for a given character set. You can use this to create all possible combinations of +, -, /, * using the method described in the question

  public static void combinations(int maxLength, char[] alphabet, String curr) { // If the current string has reached it maximum length if (curr.length() == maxLength) { System.out.println(curr); // Else add each letter from the alphabet to new strings and process these new strings again } else { for (int i = 0; i < alphabet.length; i++) { String oldCurr = curr; curr += alphabet[i]; combinations(maxLength, alphabet, curr); curr = oldCurr; } } } 

and calling him something like

 char[] operators = new char[]{'+', '-', '/', '*'}; combinations(3, operators , ""); //You want to call it with 3 since you only need 3 operators. 

After (or instead) printing a new combination ( System.out.println(curr); ) you can call the method to interpret the output.
You can hide something similar to this fooobar.com/questions/1235039 / ....
For example, you might have something like:

 if(curr.charAt(0) == '+'){ //add the first and second number } 

I think that should be enough for you to go.

EDIT
I had time on hand and I wanted to finish it, since I found it interesting. Here you go. This works exactly with what you need.

 import java.util.Random; import javax.script.ScriptEngine; import javax.script.ScriptEngineManager; import javax.script.ScriptException; public class Blah { public static void main(String[] args) throws ScriptException { char[] operators= new char[]{'+', '-', '/', '*'}; combinations(3, operators, ""); } public static void combinations(int maxLength, char[] alphabet, String curr) throws ScriptException { // If the current string has reached it maximum length if (curr.length() == maxLength) { System.out.println(curr); calculate(curr); // Else add each letter from the alphabet to new strings and process these new strings again } else { for (int i = 0; i < alphabet.length; i++) { String oldCurr = curr; curr += alphabet[i]; combinations(maxLength, alphabet, curr); curr = oldCurr; } } } private static void calculate(String operators) throws ScriptException { int operand1, operand2, operand3, operand4; Random randGen = new Random(); ScriptEngineManager mgr = new ScriptEngineManager(); ScriptEngine engine = mgr.getEngineByName("JavaScript"); int result = 0; String operation = ""; // this will hold all the operands and operators while (result != 20) { operand1 = randGen.nextInt(101); operand2 = randGen.nextInt(101); operand3 = randGen.nextInt(101); operand4 = randGen.nextInt(101); /*So here is where it got a bit tricky and you can go different ways about this. I went the easy way and used the built-in Javascript engine.*/ operation = String.valueOf(operand1) + operators.charAt(0) + String.valueOf(operand2) + operators.charAt(1) + String.valueOf(operand3) + operators.charAt(2) + String.valueOf(operand4); // System.out.println(operation); result = (int) Double.parseDouble(engine.eval(operation).toString()); } System.out.println(operation + "= 20"); } } 

To make this interesting, I used random numbers. Not sure how you get your input number. One thing to keep in mind is that decimals are reset when split when working with Integer. So something like 12/64 = 0 or 11/5 = 2.
Here's an example output:

 run: +++ 0+0+10+10= 20 ++- 59+3+38-80= 20 ++/ 19+0+66/53= 20 ++* 15+5+0*54= 20 +-+ 23+26-97+68= 20 +-- 87+66-73-60= 20 +-/ 15+5-0/33= 20 +-* 63+57-50*2= 20 +/+ 8+61/37+11= 20 +/- 72+38/55-52= 20 +// 20+61/71/8= 20 +/* 18+5/28*14= 20 +*+ 2+0*14+18= 20 +*- 35+1*75-90= 20 +*/ 20+8*5/54= 20 +** 20+91*0*2= 20 -++ 37-100+17+66= 20 -+- 65-89+46-2= 20 -+/ 52-32+33/84= 20 -+* 52-32+44*0= 20 --+ 39-74-22+77= 20 --- 92-0-54-18= 20 --/ 62-41-45/73= 20 --* 54-34-0*82= 20 -/+ 22-98/9+9= 20 -/- 66-27/71-45= 20 -// 20-0/17/41= 20 -/* 42-20/71*76= 20 -*+ 9-2*0+11= 20 -*- 90-6*10-10= 20 -*/ 40-75*24/90= 20 -** 20-0*26*90= 20 /++ 65/47+6+13= 20 /+- 91/5+56-54= 20 /+/ 64/4+69/16= 20 /+* 54/81+2*10= 20 /-+ 80/89-68+88= 20 /-- 65/2-11-1= 20 /-/ 86/4-96/98= 20 /-* 80/4-0*100= 20 //+ 12/64/57+20= 20 //- 64/1/1-44= 20 /// 82/1/4/1= 20 //* 45/7/18*57= 20 /*+ 45/12*4+5= 20 /*- 44/21*45-74= 20 /*/ 87/6*55/38= 20 /** 29/76*5*11= 20 *++ 0*36+3+17= 20 *+- 4*13+55-87= 20 *+/ 2*10+14/72= 20 *+* 0*100+2*10= 20 *-+ 49*1-29+0= 20 *-- 48*2-54-22= 20 *-/ 1*21-11/73= 20 *-* 44*52-27*84= 20 */+ 7*8/56+19= 20 */- 38*77/55-33= 20 *// 95*99/6/77= 20 */* 2*9/72*83= 20 **+ 0*11*40+20= 20 **- 8*6*1-28= 20 **/ 29*59*1/82= 20 *** 4*1*5*1= 20 BUILD SUCCESSFUL (total time: 34 minutes 35 seconds) 

Took 34 minutes to complete the launch due to very complex ones like /// and *** because of 100 random whole caps. In addition, I did not bother to make it as clean / efficient as possible and did not observe the leakage of objects / unnecessary creation of objects. It will be for you :)
Hooray!