Place +,-, nothing between 1, 2, ..., 9 (in this order) whose sum is 100

Question

I am trying to solve a programming problem and I see the size of program has increased a bit while I keep coding. I found this problem here.

Here is the problem:

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

I coded it in Java.

Here is the complete program.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;

/**
 * Write a program that outputs all possibilities to put + or - 
 * or nothing between the numbers 1, 2, ..., 9 (in this order) 
 * such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100. 
 */
/**
 * @author srk
 */

public class Problem5 {

    private final int START_INDEX = 0;
    private final String LEFT_SQUARE_BRACE = "[";
    private final String RIGHT_SQUARE_BRACE = "]";
    private final String SPLIT_STRING_REGEX = ",";
    private final String STRING_SUFFIX = ",";
    private final List<String> OPERATIONS = Arrays.asList("+", "-", "");

    public static void main(String[] args) {
        Problem5 problem5 = new Problem5();

        List<Integer> oneToNine = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        int resultantSum = 100;
        /* Step 1: Break it into functions */
        LinkedHashMap<String, List<StringBuilder>> fBreakUp = problem5
                .breakIntoFunctions(new ArrayList<>(oneToNine),
                        new LinkedHashMap<String, List<StringBuilder>>());
        /* Step2: Resolve each function from bottom up */
        problem5.workFromBottomUp(problem5.fBreakUpKeysFrmTail(fBreakUp),
                fBreakUp);
        /*
         * Step3: Evaluate all the combinations and fetch only those, whose sum
         * is 100
         */
        List<StringBuilder> allcombinations = fBreakUp.get(problem5
                .getfunction(oneToNine));
        System.out.println("Probable combinations -> " + allcombinations.size());
        List<String> specCombinations = problem5.getSpecCombinations(
                allcombinations, resultantSum);
        problem5.printResult(specCombinations);
    }

    private void printResult(List<String> specCombinations) {
        for (String combination : specCombinations) {
            System.out.println(combination);
        }
        System.out.println("Total combinations " + specCombinations.size());

    }

    private List<String> getSpecCombinations(
            List<StringBuilder> allcombinations, int resultantSum) {
        List<String> finalCombi = new ArrayList<>();

        for (StringBuilder csv : allcombinations) {
            for (String thisCombi : csv.toString().split(SPLIT_STRING_REGEX)) {
                if (findSum(thisCombi).compareTo(
                        BigInteger.valueOf(resultantSum)) == 0) {
                    finalCombi.add(thisCombi);
                }
            }
        }
        return finalCombi;

    }

    private static BigInteger findSum(String input) {
        /* Step1 : Split with + */
        String[] positives = input.split("[+]+");
        List<BigInteger> ListAfterExpEval = new ArrayList<>();
        for (String thisPosExp : positives) {
            BigInteger expValue = BigInteger.ZERO;
            if (thisPosExp.contains("-")) {
                /* Split with -, if it has */
                String[] negatives = thisPosExp.split("[-]+");
                for (String thisNegExp : negatives) {
                    /* Covert String to BigInteger */
                    BigInteger thisNumber = new BigInteger(thisNegExp);
                    if (expValue == BigInteger.ZERO) {
                        expValue = thisNumber;
                    } else {
                        expValue = expValue.subtract(thisNumber);
                    }
                }
                ListAfterExpEval.add(expValue);
            } else {
                /* could be a number */
                ListAfterExpEval.add(new BigInteger(thisPosExp));
            }

        }
        BigInteger finalSum = BigInteger.ZERO;
        for (BigInteger thisNum : ListAfterExpEval) {
            if (finalSum == BigInteger.ZERO) {
                finalSum = thisNum;
            } else {
                finalSum = finalSum.add(thisNum);
            }

        }
        return finalSum;
    }

    private void workFromBottomUp(List<String> fBreakUpKeys,
            LinkedHashMap<String, List<StringBuilder>> fBreakUp) {
        String tailKeyInFBreakUp = fBreakUpKeys.remove(START_INDEX);
        Iterator<String> fBreakUpKeysItr = fBreakUpKeys.iterator();
        String keyBeforeTail;
        while (fBreakUpKeysItr.hasNext()) {
            keyBeforeTail = fBreakUpKeysItr.next();
            fBreakUpKeysItr.remove();
            tailKeyInFBreakUp = resolveFunctions(tailKeyInFBreakUp,
                    keyBeforeTail, fBreakUp);
        }

    }

    private String resolveFunctions(String tailKeyInFBreakUp,
            String keyBeforeTail,
            LinkedHashMap<String, List<StringBuilder>> fBreakUp) {
        List<StringBuilder> fValToBeSubstituted = fBreakUp
                .get(tailKeyInFBreakUp);
        List<StringBuilder> fValsToBeResolved = fBreakUp.get(keyBeforeTail);
        for (StringBuilder fValToBeResolved : fValsToBeResolved) {
            int indexOfF = fValToBeResolved.indexOf(tailKeyInFBreakUp);
            if (indexOfF != -1) {
                fValToBeResolved.replace(indexOfF, fValToBeResolved.length(),
                        fValToBeSubstituted.toString());
                fValToBeResolved.replace(START_INDEX,
                        fValToBeResolved.length(),
                        cartesianProduct(fValToBeResolved));
            }
        }
        fBreakUp.remove(tailKeyInFBreakUp);
        return keyBeforeTail;
    }

    private String cartesianProduct(StringBuilder fValToBeResolved) {
        StringBuilder localSb = new StringBuilder();
        int indexOfLeftSqBrace = fValToBeResolved.indexOf(LEFT_SQUARE_BRACE);
        int indexOfRightSqBrace = fValToBeResolved.indexOf(RIGHT_SQUARE_BRACE);
        String prefix = fValToBeResolved.substring(START_INDEX,
                indexOfLeftSqBrace);
        List<String> resolvedVals = Arrays.asList(fValToBeResolved.substring(
                indexOfLeftSqBrace + 1, indexOfRightSqBrace).split(
                SPLIT_STRING_REGEX));
        for (String val : resolvedVals) {
            localSb.append(prefix.trim() + val.trim());
            if (resolvedVals.indexOf(val) != resolvedVals.size() - 1) {
                localSb.append(STRING_SUFFIX);
            }
        }
        return localSb.toString();
    }

    private List<String> fBreakUpKeysFrmTail(
            LinkedHashMap<String, List<StringBuilder>> fBreakUp) {
        List<String> functionsBreakUpKeys = new ArrayList<>(fBreakUp.keySet());
        Collections.reverse(functionsBreakUpKeys);
        return functionsBreakUpKeys;
    }

    private LinkedHashMap<String, List<StringBuilder>> breakIntoFunctions(
            List<Integer> workList,
            LinkedHashMap<String, List<StringBuilder>> fBreakUp) {

        String function = getfunction(workList);
        String head = getHeadAndRemoveit(workList);

        boolean workListSizeIsOne = workList.size() == 1 ? true : false;
        ArrayList<StringBuilder> breakDownValues = new ArrayList<>();

        for (String operation : OPERATIONS) {
            StringBuilder sb = new StringBuilder();
            if (!(workListSizeIsOne ? breakDownValues.add(sb.append(head
                    + operation + workList.get(START_INDEX))) : breakDownValues
                    .add(sb.append(head + operation + getfunction(workList)))))
                break;

        }
        fBreakUp.put(function, breakDownValues);

        if (!workList.isEmpty() && !workListSizeIsOne)
            breakIntoFunctions(workList, fBreakUp);

        return fBreakUp;
    }

    private String getHeadAndRemoveit(List<Integer> workList) {
        Integer headElement = workList.get(START_INDEX);
        workList.remove(headElement);
        return String.valueOf(headElement);
    }

    private String getfunction(List<Integer> list) {
        StringBuilder sb = new StringBuilder("f(");
        for (Integer integ : list) {
            sb.append(integ);
        }
        return sb.append(")").toString();
    }

}

What are the points, where it could be improved and optimized?

Answer 1

Your code works correctly (as far as I can tell), but it took me a while to understand how it works.

• First, a string list of all possible combinations is built recursively. As part of this process, lists are converted to their string representation, in resolveFunctions(), at

          fValToBeResolved.replace(indexOfF, fValToBeResolved.length(),
                  fValToBeSubstituted.toString());
  

  Later, in cartesianProduct(), these strings are dissected again by locating the left and right square bracket, and a regular expression split.

  I do not know if the string representation of a List as comma-separated items enclosed in square brackets is documented (Java is not my first language), but clearly stating that you rely on it would help the understanding of your code.

• Then all strings are evaluated as expressions, in order to keep only those which give the desired target sum. This is done by regular expression splits on "+" and "-" and adding/subtracting the components.

  Using BigInteger seems unnecessary to me since all possible values fit into a (32-bit) integer.

  The evaluation of an expression of the form "a-b-c-d" is fragile, as it assumes that no intermediate result is zero.

The code is difficult to understand (well, at least to me). It is not obvious what a variable named fBreakUp represents, or what functions named

private List<String> fBreakUpKeysFrmTail(...)
private LinkedHashMap<String, List<StringBuilder>> breakIntoFunctions(...)
private String cartesianProduct(StringBuilder fValToBeResolved) 

do. Documenting each function (and adding an example) would help.

Generally, your approach looks unnecessary complicated to me. There are many conversions between numbers, strings, lists, and hash maps, and a lot of string operations.

Instead of building (all) possible expression as strings and evaluating these, you can combine consecutive digits to a number, add or subtract this number from the desired target sum, and then (recursively) repeat the process with the remaining digits.

Here is an example how that could work:

public class Problem5 {

    private static void buildSum(String prefix, int lowDigit, int highDigit, int target) {
        if (lowDigit > highDigit) {
            // All digits used – did we hit the target?
            if (target == 0) {
                System.out.println(prefix);
            }
        } else {
            // Combine digits, starting with `lowDigit`, to a single number `n`.
            // Add or subtract `n` from the current target, and call recursively
            // with the remaining digits:
            int n = 0;
            for (int i = lowDigit; i <= highDigit; i++) {
                n = 10 * n + i;
                if (prefix == null) {
                    // Initial call: Use `n` as first number:
                    buildSum(Integer.toString(n), i + 1, highDigit, target - n);
                } else {
                    // Recursive call: Add or subtract `n`:
                    buildSum(prefix + "+" + n, i + 1, highDigit, target - n);
                    buildSum(prefix + "-" + n, i + 1, highDigit, target + n);
                }
            }
        }
    }

    public static void main(String[] args) {
        buildSum(null, 1, 9, 100);
    }
}

In my test this ran twice as fast as your code (approx 0.2 vs 0.4 seconds on a 1.2 GHz Intel Core m5 MacBook).

Further suggestion: It might help to estimate how large the remaining value can be. For example, if we already have the prefix 123456 then at most 789 can be subtracted, and reaching the target value 100 is impossible. This would allow to shortcut the recursion in many cases.

Answer 2

• Your method breakIntoFunctions seems to fulfill the purpose of a recursive method, but in fact, it is not. Generally, a recursive method is something like this:

  f(n) {
      if (n==1) {
          return something;
      } else {
          return the result of some operation involving f(n-1);
      }
  }
  

  But the method breakIntoFunctions behaves more like this:

  f(n) {
      if (n==1) {
          return something;
      } else {
          tell the caller that f(n) must be computed from f(n-1);
      }
  }
  

  So it doesn't actually compute the result itself, but only makes a note somewhere (i.e. the Map fBreakUp) about how the result can be computed. True, it calls f(n-1) later on, but it doesn't use the value returned by f(n-1) to compute the result. This requires you to delegate the quasi-recursive computation of the result to a mess of other methods, most of which make assumptions about the arguments that are passed to them based on the context in which you intend to call them. For example, the method workFromBottomUp assumes that the last item in fBreakUp is mapped to a String that doesn't need to be decomposed further, and that the Strings in fBreakUpKeys are the keys from fBreakUp in reverse order. This means that you have to crawl through the whole code to understand what a method does, which defies the point of organizing code into methods and instead lays a foundation for spaghetti code.

• Also, you reduce the whole concept of object-oriented programming to absurdity with your method cartesianProduct and how you use it in resolveFunctions. You are, in effect, stripping a List of all of its functionality in resolveFunctions by converting it to a String via List.toString(), and then, in order to re-gain the functionality of the List, cartesianProduct parses the String back to a List. And what does cartesianProduct do with the List? Right, it converts the List to a String again, this time with a home-made algorithm rather than List.toString(), so that it can be combined into one String representation of a List with everything before the old list. Why don't you instead simply replace an entry in the old list (e.g. "7+f(89)") with three new entries (e.g. "7+8+9", "7+8-9" and "7+89") instead of modifying the single entry to represent 3 values (i.e. "7+8+9,7+8-9,7+89")? That way, you would also get a meaningful number when you call allcombinations.size() in the main method, instead of the completely useless value 3, which only represents the number of sub-steps at the first level of the recursion tree.

• What is this?

  for (String operation : OPERATIONS) {
      StringBuilder sb = new StringBuilder();
      if (!(workListSizeIsOne ? breakDownValues.add(sb.append(head
              + operation + workList.get(START_INDEX))) : breakDownValues
              .add(sb.append(head + operation + getfunction(workList)))))
          break;
  
  }
  

  Specifically, this part:

  if (!(workListSizeIsOne ? breakDownValues.add(sb.append(head
          + operation + workList.get(START_INDEX))) : breakDownValues
          .add(sb.append(head + operation + getfunction(workList)))))
      break;
  

  This is flat-out code obfuscation. Essentially, it boils down to to the following:

  if (!someList.add(someItem)) {
      break;
  }
  

  And List.add(E) always returns true (if it returns at all, meaning if it doesn't throw an exception). So the above becomes:

  if (false) {
      // who cares?
  }
  

  Only that the expression evaluating to false has side effects. The side effects are:

  String workListAsString;
  if (workListSizeIsOne) {
      workListAsString = workList.get(START_INDEX).toString();
  } else {
      workListAsString = getfunction(workList);
  }
  breakDownValues.add(sb.append(head).append(operation).append(workListAsString));
  

  Since this is, in the end, all that the for loop does, it is absolutely inappropriate to disguise this as a side-effect of an expression whose evaluation is completely pointless.

• Finally, about the variables START_INDEX, LEFT_SQUARE_BRACE and RIGHT_SQUARE_BRACE. Maybe you have been conditioned into being terrified of numeric or String literals because of the complications arising from the usage of magic numbers. But declaring a final field named LEFT_SQUARE_BRACE that holds a left square brace does not solve or prevent any problems that usually come with magic numbers. For example, in code that deals with numbers, you could hard-code the number of possible digits as a magic number 10, and as soon as it occurs to you that you might want to extend the functionality of the program to also deal with hexadecimal numbers, you are in trouble because you used a magic number. But here, LEFT_SQUARE_BRACE can, by definition, not contain anything other than a left square brace, so this field is simply redundant. You might take a look at this.