Algorithm to find combinations of integers and any operand to obtain a fixed result

Question

I am writing a program that takes 4 numbers as input and then attempts to see if a combination of addition subtraction division and multiplication of the four numbers can make them equal to 24. My way was creating a method for every single possible combination of the four numbers and the 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 do create a while loop for each method that if the method returns true, will print that the method it stopped on, was the 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 like + and - so that I can put them in an array and just use some nested for loops to write this?

You don't necessarily need a new method for subtraction alone. You can use the same method you used for addition but send a negative value instead. — Ceelos, Nov 02 '15 at 18:32
It gets more complicated I don't think that would save me much time, because I have method where addition and subtraction and division are combined — Gabe Spound, Nov 02 '15 at 18:33
You should be able to put logic of all 4 methods in a single method. — yogidilip, Nov 02 '15 at 18:33
there are hundreds of methods, its not just adding all four, subtracting all four, multiplying all four, and dividing all four, It's a combination of all of them, in different orders. — Gabe Spound, Nov 02 '15 at 18:35
Do you need to find all combinations or just one is sufficient ? — Gaël J, Nov 02 '15 at 18:36
How are you dealing with the order of operations? Do you have to worry at all about the associativity of those 4 numbers? — NotAGenie, Nov 02 '15 at 19:27
If provided 528, 11, 7 and 14, is `528 / 14 * 7 / 11` a valid solution? Or should `528 / 14 == 38` (like it does with integers)? — Andreas, Nov 02 '15 at 20:15
Here's the same question, but with precendence (brackets). I provided solutions in javascript, but the logic should be useful here too: http://stackoverflow.com/questions/32229242/solution-finder-algorithm-using-basic-operations/32237550#32237550 (look at the second version of the code, the first is overly complicated) — m69's been on strike for years, Nov 03 '15 at 00:30
I solved this with a nested loop to find all combinations of operators and a combinatoric algorithm to find all permutations of the numbers. I had an enum for the operators. There are also 5 unique ways to apply brackets (precedence) to the operations, for four operands. — David Conrad, Nov 09 '15 at 21:54
Why exactly to you do while(condition){do stuff; break;} instead of if(condition){do stuff;}? Also, you really shouldn't name that function "add". If I read add, I assume that this will add the numbers and return their sum or something like that, and I will certainly not assume that it will compare them to a magic number. Better would be to return the sum and set your condition to sum(a,b,c,d) == 24. Just wanted to tell you that for code you will write in the future, not that this helps with the actual problem, but there are two competent answers out there already. — Aziuth, Oct 31 '16 at 16:04

ergonaut · Answer 1 · 2015-11-02T20:21:49.620

2

Assuming the operands are fixed, you can create a generator which dumps out the possible operators, and pass them to an 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 could be done like this:

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

where generator implements the java.util.Iterator interface that initializes with all the operators (+-*/) and dumps out all the 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 is [+-/] it would check

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

I should add there's all kinds of efficiencies you can add later, but you're question is how you can do this with a better strategy. There are a few comments on details from other users, but I wouldn't worry about it now. First you need to set up this kind of framework, then you can worry about the details. Most key to this, is that you do not need to make 100s of similar looking methods.

edited Nov 02 '15 at 20:21

answered Nov 02 '15 at 18:46

ergonaut

6,929
1
17
47

Where is the evaluatesTo method? Where do I pass in the operators? How would this all get structured? – Gabe Spound Nov 02 '15 at 18:51
Also, After importing Java.util.Iterator My IDE can't find generator – Gabe Spound Nov 02 '15 at 18:55
You have to implement generator. – ergonaut Nov 02 '15 at 19:02
I'm still new to java so could you explain each step a bit more, I'm really not trying to get anybody to do this for me(there would be no reason to, it's not an assignment, its purely educational), but i don't understand what to do. – Gabe Spound Nov 02 '15 at 19:04
The hard part here isn't the methods and what they're to be. It's figuring out a way to generate all 256 combinations of +,-,/,* efficiently – Ceelos Nov 02 '15 at 19:10
ok, but I don't know what generator is or how to use it, or what ops is. Where do I start? – Gabe Spound Nov 02 '15 at 19:11
1

http://stackoverflow.com/questions/10305153/generating-all-possible-permutations-of-a-list-recursively – ergonaut Nov 02 '15 at 19:11

score 2 · Answer 2 · edited Jul 26 '21 at 09:19

I did some digging around for you.
I found this stackexchange question going over how to create all possible combinations for a given set of characters. You can use this to generate all possible combinations of +,-,/,* by using the method described in the question.

public static void combinations(int maxLength, char[] alphabet, String curr) {
  // If the current string has reached it's 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 it with something like

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

After (or instead of) printing out the new combination (System.out.println(curr);) you can call a method to interpret the output.
You can go off of something similar to this stackoverflow simple calculator example.
For instance, you can have something like:

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

I think this should be enough to get you going.

Had time on my hands and wanted to finish this since I found it interesting. Here ya go. This works exactly to 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's 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 it interesting I used random numbers. Not sure how you're getting your number input. One thing to keep in mind is that decimals are dropped in division when dealing with the Integer. So something like 12/64 = 0 or 11/5=2.
Here's a sample 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 run due to the really tricky ones like /// and *** due to the 100 random integer cap. Also, I didn't bother to make this as clean/efficient as possible and didn't watch for object leaks/unnecessary object creation. That will be up to you.

it's super slow because you're modifying the string and then parse the string and evaluate each time. Storing only the operators are much more efficient — phuclv, Jul 25 '21 at 09:05

Algorithm to find combinations of integers and any operand to obtain a fixed result

2 Answers2