Generate all combinations of mathematical expressions that add to target (Java homework/interview)

Question

I've tried to solve the problem below for a coding challenge but could not finish it in 1 hour. I have an idea on how the algorithm works but I'm not quite sure how to best implement it. I have my code and problem below.

The first 12 digits of pi are 314159265358. We can make these digits into an expression evaluating to 27182 (first 5 digits of e) as follows:

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

or

3 + 1 - 415 * 92 + 65358 = 27182

Notice that the order of the input digits is not changed. Operators (+,-,/, or *) are simply inserted to create the expression.

Write a function to take a list of numbers and a target, and return all the ways that those numbers can be formed into expressions evaluating to the target

For example:
f("314159265358", 27182) should print:

3 + 1 - 415 * 92 + 65358 = 27182
3 * 1 + 4 * 159 + 26535 + 8 = 27182
3 / 1 + 4 * 159 + 26535 + 8 = 27182
3 * 14 * 15 + 9 + 26535 + 8 = 27182
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

This problem is difficult since you can have any combination of numbers and you don't consider one number at a time. I wasn't sure how to do the combinations and recursion for that step. Notice that parentheses are not provided in the solution, however order of operations is preserved.

My goal is to start off with say

{"3"}
then
{"31", "3+1", "3-1", "3*1" "3/1"}
then
{"314", "31+4", "3+1+4", "3-1-4", "31/4", "31*4", "31-4"} etc.

then look at the every value in the list each time and see if it is target value. If it is, add that string to result list.

Here is my code

public static List<String> combinations(String nums, int target)
    {

        List<String> tempResultList = new ArrayList<String>();
        List<String> realResultList = new ArrayList<String>();
        String originalNum = Character.toString(nums.charAt(0));


        for (int i = 0; i < nums.length(); i++)
        {
            if (i > 0)
            {
                originalNum += nums.charAt(i); //start off with a new number to decompose
            }
            tempResultList.add(originalNum);
            char[] originalNumCharArray = originalNum.toCharArray();
            for (int j = 0; j < originalNumCharArray.length; j++)
            {
                //go through every character to find the combinations?
                // maybe recursion here instead of iterative would be easier...
            }
            for (String s : tempResultList)
            {
                //try to evaluate
                int temp = 0;
               if (s.contains("*") || s.contains("/") || s.contains("+") || s.contains("-"))
               {
                  //evaluate expression
               } else {
                   //just a number
               }
                if (temp == target)
                {
                    realResultList.add(s);
                }

            }
         tempResultList.clear();
        }
        return realResultList;
    }

Could someone help with this problem? Looking for an answer with coding in it, since I need help with the generation of possibilities

Eiffel

Since for every digit you multiply the number of expressions to evaluate by 5, it means that after 12 digits, you'll have 244140625 potential solutions. And while that number isn't insanely large, it probably isn't what the interviewers were looking for. – Wetnurse

I copied and pasted the exact question. It was specifically written/implemented to weed out candidates, so it is difficult of course. – Eiffel

The question is fine, what I tried to say is that they probably looked for a better answer than brute-forcing it. – Wetnurse

The problem is given via webform so I have no idea. Only possible solutions involve some sort of brute force anyway. – Eiffel

Actually there are only 5^11 or 48,828,125 possibilities. To generate them, think of it as a string manipulation: you have 12 character: 314159265358, and thus 11 places in which to insert either nothing (so the digits are chained into a larger number) or one of 4 operators. Permutating through those 5 choices at 11 places will generate all the possibilities. – Micronesian

Btw, your list of results is missing 3 + 1 * 4 * 159 + 26535 + 8 = 27182 and 3141 / 5 / 9 * 26 * 5 * 3 - 5 * 8 = 27182. – Micronesian

Answer 1

I don't think it's necessary to build a tree, you should be able to calculate as you go -- you just need to delay additions and subtractions slightly in order to be able take the precedence into account correctly:

static void check(double sum, double previous, String digits, double target, String expr) {
   if (digits.length() == 0) {
     if (sum + previous == target) {
       System.out.println(expr + " = " + target);
     }
   } else {
     for (int i = 1; i <= digits.length(); i++) {
       double current = Double.parseDouble(digits.substring(0, i));
       String remaining = digits.substring(i);
       check(sum + previous, current, remaining, target, expr + " + " + current);
       check(sum, previous * current, remaining, target, expr + " * " + current);
       check(sum, previous / current, remaining, target, expr + " / " + current);
       check(sum + previous, -current, remaining, target, expr + " - " + current);
     }
   }
 }

 static void f(String digits, double target) {
   for (int i = 1; i <= digits.length(); i++) {
     String current = digits.substring(0, i);
     check(0, Double.parseDouble(current), digits.substring(i), target, current);
   }
 } 

Joelynn

This is an interesting algorithm and it seems to work, but it is a little strange. So, it tries out all the "+" first, then uses sum and previous to backtrack for correct expressions? What's with the -current? – Eiffel

It just delays + and - giving * and / the opportunity to grab the previous number. -current avoids keeping track of whether a + or - is still pending, taking advantage of a - b * c = a + (-b * c) – Joelynn

For multiplication and division, why do we need to pass previous * current or previous / current rather than just current? – Revival

* and / have the highest precedence, so they can be executed immediately. If just current would be passed, previous would get dropped. – Joelynn

Answer 2

First, you need a method where you can input the expression

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8

and get the answer:

27182

Next, you need to create a tree structure. Your first and second levels are complete.

3
31, 3 + 1, 3 - 1, 3 * 1, 3 / 1

Your third level lacks a few expressions.

31 -> 314, 31 + 4, 31 - 4, 31 * 4, 31 / 4
3 + 1 -> 3 + 14, 3 + 1 + 4, 3 + 1 - 4, 3 + 1 * 4, 3 + 1 / 4
3 - 1 -> 3 - 14, 3 - 1 + 4, 3 - 1 - 4, 3 - 1 * 4, 3 - 1 / 4
3 * 1 -> 3 * 14, 3 * 1 + 4, 3 * 1 - 4, 3 * 1 * 4, 3 * 1 / 4
3 / 1 -> 3 / 14, 3 / 1 + 4, 3 / 1 - 4, 3 / 1 * 4, 3 / 1 / 4

You can stop adding leaves to a branch of the tree when a division yields a non integer.

As you can see, the number of leaves at each level of your tree is going to increase at a rapid rate.

For each leaf, you have to append the next value, the next value added, subtracted, multiplied, and divided. As a final example, here are 5 of the fourth level leaves:

3 * 1 + 4 -> 3 * 1 + 41, 3 * 1 + 4 + 1, 3 * 1 + 4 - 1, 3 * 1 + 4 * 1,
    3 * 1 + 4 / 1

Your code has to generate 5 expression leaves for each leaf until you've used all of the input digits.

When you've used all of the input digits, check each leaf equation to see if it equals the value.

Transcendence

...and for each leaf you can store the result so far to stop evaluating the same sub-expression over and over again. – Wetnurse

"First, you need a method where you can input the expression 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 and get the answer: 27182" System.out.println(3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8); gives the correct answer without needing parentheses – Eiffel

I need help generating those possibilities – Eiffel

@John61590: I've explained the solution as best as I can. The next step is writing the program. Create a data class to hold the expression and build a tree structure with instances of your data class as nodes (leaves). – Transcendence

I've got something like public static void printMathComb(String prefix,String str, List<String> results) { if (str.length() == 0) { System.out.println(prefix); results.add(prefix); return; } printMathComb(prefix + " + " + str.substring(0, 1), str.substring(1), results); printMathComb(prefix + " - " + str.substring(0, 1), str.substring(1), results); printMathComb(prefix + " * " + str.substring(0, 1), str.substring(1), results); printMathComb(prefix + " / " + str.substring(0, 1), str.substring(1), results); } – Eiffel

@John61590: You don't use recursion to build a tree. – Transcendence

@GilbertLeBlanc I'm asking about how to do "31 -> 314, 31 + 4, 31 - 4, 31 * 4, 31 / 4 3 + 1 -> 3 + 14, 3 + 1 + 4, 3 + 1 - 4, 3 + 1 * 4, 3 + 1 / 4 3 - 1 -> 3 - 14, 3 - 1 + 4, 3 - 1 - 4, 3 - 1 * 4, 3 - 1 / 4 3 * 1 -> 3 * 14, 3 * 1 + 4, 3 * 1 - 4, 3 * 1 * 4, 3 * 1 / 4 3 / 1 -> 3 / 14, 3 / 1 + 4, 3 / 1 - 4, 3 / 1 * 4, 3 / 1 / 4" in the tree – Eiffel

why would you prevent non-integers? consider list = 3525, target = 1 – Remorse

Why would you want to generate an explicit tree if you can keep all the values you need on the recursion stack? – Joelynn

Answer 3

My Javascript implementation:
Will improve the code using web worker later on

// was not allowed to use eval , so this is my replacement for the eval function.
function evaluate(expr) {
  return new Function('return '+expr)();
 }
 function calc(expr,input,target) { 
   if (input.length==1) { 
    // I'm not allowed to use eval, so I will use my function evaluate
    //if (eval(expr+input)==target) console.log(expr+input+"="+target);
    if (evaluate(expr+input)==target) document.body.innerHTML+=expr+input+"="+target+"<br>";
   }
   else { 
     for(var i=1;i<=input.length;i++) {
      var left=input.substring(0,i);
      var right=input.substring(i);
      ['+','-','*','/'].forEach(function(oper) {
         calc(expr+left+oper,right,target);
      },this);
     }
   }
 };
 function f(input,total) {
  calc("",input,total);
 }

Deist