1
\$\begingroup\$

I just finished my program which calculates the solutions to this problem:

Outputs all possibilities to put + or - or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100.

Code in question:

package defaultpackage;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

class Main {
    static int[] pos_counter = {0,0,0,0,0,0,0,0};

    static Boolean running = true;

    public static void main(String[] args) {
        int counter = 0;

        while(running) {
            increment();
            oobcheck();
            try {
                counter = (int) calculate(printeq());
            } catch (ScriptException e2) {
                e2.printStackTrace();
            }
            if(counter==100) {
                System.out.print(printeq());
                System.out.print("=");
                System.out.println(100);
            }
        }
    }

    public static int[] increment(){
        int stepcounter = 7;
        pos_counter[7]++;
        while(stepcounter>= 0&&running){

            if(pos_counter[stepcounter]==3&&running){
                if(stepcounter-1 == -1){
                    running = false;
                } else{
                    pos_counter[stepcounter-1]++;
                    pos_counter[stepcounter]=0;
                }
            }
            stepcounter--;
        }
        return pos_counter;
    }

    public static double calculate(String s) throws ScriptException{
        ScriptEngineManager mgr = new ScriptEngineManager();
        ScriptEngine engine = mgr.getEngineByName("JavaScript");
        return (double) engine.eval(s);
    }

    public static void readout() {
        int stepcounter = 0;
        while(stepcounter <= 7) {
            System.out.print(pos_counter[stepcounter]);
            stepcounter++;
        }
        System.out.println("");
    }

    public static String printeq() {
        int stepcounter = 0;
        String read = "";
        while(stepcounter <= 7) {
            read = "" + read + (stepcounter+1);
            if(pos_counter[stepcounter] == 0){
            }else if(pos_counter[stepcounter] == 1) {
                read = read + "+";
            }else if(pos_counter[stepcounter] == 2) {
                read = read + "-";
            }
            stepcounter++;
        }
        read = read + "9";
        return read;
    }

    public static void oobcheck(){
        int stepcounter = 0;
        Boolean checker = true;
        while(checker&&stepcounter <= 7) {
            if(pos_counter[stepcounter] == 2) {
                stepcounter++;
                checker = true;
            }else{
                checker = false;
            }
            if(stepcounter==7){
                if(pos_counter[7] == 2) {
                    running = false;
                }
            }
        }
    }
}

My program works fine and spits out all the answers correctly but I'm looking to improve it. I've seen solutions to similar problems and they mostly take up less space or seem more organized.

Concrete questions:

  1. Where can I learn to improve code efficiency or organization?
  2. What could be used specifically to make my code faster and more efficient?
\$\endgroup\$
1
  • 6
    \$\begingroup\$ You're... evaluating strings in javascript to check whether they add up? \$\endgroup\$
    – BenC
    Sep 19, 2017 at 23:25

5 Answers 5

2
\$\begingroup\$

General remark

Short code (as in less space in code) is not necessarily easier to read, nor does it need to be faster. You can try to keep removing unnecessary stuff until it is as short as possible, but please keep it readable. Writing code is hard, reading code is twice as hard.

Short answer

  1. Online, everywhere, in books. "Effective Java" for example. Read about algorithms and data structures. Look at how others solved problems. Read many code reviews.

  2. Use a profiler and measure where your code is slow.

Longer answer

  1. You need to expose yourself to a lot of code, and start with simple problems. See how you would solve it, then look how others solved it and try to improve upon it.
  2. For this case: try to represent your operators and operands in such a way that you can evaluate them in Java. Generally: use the correct data structures and algorithms. That is most important. Then, try to use the right types. String concatenation is generally a lot slower in execution time than integer math.

Example

For example to evaluate and generate the permutations (using recursion just because we can :):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MakeHundred {

    private static int LENGTH = 8;

    // Encode the operators in a enum. We use the factor to implement
    // easier operation later on, and the display String as well.

    enum Operator {

        PLUS(1, "+"), MINUS(-1, "-"), NONE(0, "");

        private int factor;
        private String display;

        public String getDisplay() {
            return display;
        }

        Operator(int factor, String display) {
            this.factor = factor;
            this.display = display;
        }

        public int getFactor() {
            return factor;
        }

    }

    /**
     * Class for keeping a permutation, with is an list of operators which will be
     * used to create a sum, eg. 1 op1 2 op2 3.
     * 
     * @author RobAu
     *
     */
    public static class Permutation {

        Operator[] operators;

        // Just one operator
        public Permutation(Operator operator) {
            this.operators = new Operator[] { operator };
        }

        // Copy the given permutation, append the given operator
        public Permutation(Permutation sourcePermutation, Operator operatorToAppend) {
            this.operators = Arrays.copyOf(sourcePermutation.operators, sourcePermutation.operators.length + 1);
            this.operators[sourcePermutation.operators.length] = operatorToAppend;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < operators.length; i++) {
                sb.append(i + 1);
                sb.append(operators[i].getDisplay());
            }
            // append the last digit
            sb.append(operators.length + 1);
            return sb.toString();
        }

        public int evaluate() {
            int index = 0;
            int currentNumber = 0;
            int total = 0;

            // We start with a previous operator (+),
            // So the code becomes simpler.
            // 1+2 = 0 + 1 + 2.
            Operator operator = Operator.PLUS;

            while (index < LENGTH) {

                currentNumber += (index + 1);

                // If there is no operator, we are making a bigger number.
                if (operators[index] == Operator.NONE) {
                    currentNumber *= 10;
                } else {

                    // We increate the total by adding the current Number
                    // and using the previously seen operator
                    total += currentNumber * operator.getFactor();
                    currentNumber = 0;
                    operator = operators[index];
                }
                index++;
            }

            // add the last number.
            currentNumber += index + 1;
            total += currentNumber * operator.getFactor();

            return total;
        }

        /**
         * Generate all permutation with length <code>length</code>
         */
        public static List<Permutation> generate(int length) {
            return generate(null, length);
        }

        private static List<Permutation> generate(List<Permutation> permutations, int length) {

            List<Permutation> perms = new ArrayList<>();
            if (length == 1) {
                for (Operator o : Operator.values()) {
                    perms.add(new Permutation(o));
                }
            } else {
                for (Permutation p : generate(permutations, length - 1)) {
                    for (Operator o : Operator.values()) {
                        perms.add(new Permutation(p, o));
                    }
                }
            }
            return perms;
        }
    }

    public static void main(String[] args) {
        for (Permutation p : Permutation.generate(null, LENGTH)) {
            if (p.evaluate() == 100) {
                System.out.println(p);
            }
        }
    }
}

Including JVM startup this runs in:

real    0m0,088s
user    0m0,088s
sys 0m0,012s
\$\endgroup\$
1
\$\begingroup\$
    public static void oobcheck(){
        int stepcounter = 0;
        Boolean checker = true;
        while(checker&&stepcounter <= 7) {
            if(pos_counter[stepcounter] == 2) {
                stepcounter++;
                checker = true;
            }else{
                checker = false;
            }
            if(stepcounter==7){
                if(pos_counter[7] == 2) {
                    running = false;
                }
            }
        }
    }

This seems longer than it needs to be.

    public static void oobcheck() {
        int stepcounter = 0;
        while (stepcounter <= 7) {
            if (pos_counter[stepcounter] == 2) {
                if (stepcounter==7) {
                    running = false;
                    return;
                }

                stepcounter++;
            } else {
                break;
            }
        }
    }

We can save some code by moving the check into what we already have.

I prefer more whitespace.

We don't need to set checker to true, as it is already true at that point.

And we don't really need checker at all. We can replace it with a break statement.

But we can do better.

    public static void oobcheck() {
        int stepcounter = 0;
        while (stepcounter <= 7 && pos_counter[stepcounter] == 2) {
            if (stepcounter==7) {
                running = false;
                return;
            }

            stepcounter++;
        }
    }

Now we don't even need the break.

But we can still do better.

    public static void oobcheck() {
        int stepcounter = 0;
        while (stepcounter < 7 && pos_counter[stepcounter] == 2) {
            stepcounter++;
        }

        if (pos_counter[stepcounter] == 2) {
            running = false;
        }
    }

We don't need to check if we're on the last step on every step. We can just process all but the last step. Then we can check just once.

These changes may not have a big effect on performance, but they reduce the amount of code and simplify the method. Now we can easily see that we're checking if we've found all the possibilities.

There are still things wrong with this method. Why 7? What makes it magically the right number? Why 2? What's an oobcheck? But the fixes that I'd prefer are more complicated than just fixing this method.

Performance

If I had to guess, I'd say that the biggest reduction in performance comes from parsing the expressions as scripts. There's only \$3^8=6561\$ different possibilities. There are eight places for operators and three choices for each. If you write your own calculator, you don't have to convert to and from a string form each time. You can just work with the numbers and operations directly.

Another issue is that you start from scratch each time. But you only change one operator at a time. You could just recalculate that operator. But I doubt that will be necessary with an efficient parser.

\$\endgroup\$
1
  • \$\begingroup\$ "There are eight places for operators and three choices for each." That looks like an 8-digit base 3 number, between 00000000 and 22222222. Convert [0, 1, 2] to [<space>, +, -] and you have all possible combinations. \$\endgroup\$
    – rossum
    Sep 20, 2017 at 11:39
1
\$\begingroup\$

A few suggestions to improve your programming :

  • Learn about functional programming. That will give you a lot of ideas in how to use recursion in your algorithms
  • Slice your problems into smaller ones. And use really descriptive names in your code for functions and variables.
  • Learn how to use Java Streams. This is not as good a some functional languages, but still very cool to use. Keep them readable !
  • LEARN REGULAR EXPRESSIONS ! I had the chance to be taught really well about them in my first week of school, this is an invaluable tool that I've used countless times. Keep them readable as well :)
  • Books: SICP, Clean Code. Those two should get you on a good start.

And now, my take on your problem, I don't claim perfection, but I hope it will be food for thoughts.

public class AllCombi {

  private int startOfRange;
  private int endOfRange;

  public AllCombi(int start, int end) {
    this.startOfRange = start;
    this.endOfRange = end;
  }

  private List<String> generateCombinations() {
    return generateCombinationsRec(startOfRange, endOfRange, "", new ArrayList<>());
  }

  /**
   * Recursively generate all combinations as Strings stored in combinations. Recursion is usually a
   * good call when traversing a graph (which is kind of what it is here, a graph of numbers and
   * symbols)j
   */
  private List<String> generateCombinationsRec(int start, int end, String current,
      List<String> combinations) {
    if (start == end) {
      combinations.add(current + Integer.toString(start));
    } else {
      generateCombinationsRec(start + 1, end, current + start, combinations);
      generateCombinationsRec(start + 1, end, current + start + '+', combinations);
      generateCombinationsRec(start + 1, end, current + start + '-', combinations);
    }
    return combinations;
  }

  private int evaluateExpression(String expression) {
    // this split is using a regular expression that keeps the sign before the number : eg.
    // "1-2+34-5" will give ["1", "-2", "+34", "-5"]
    String[] allNumbersWithSign = expression.split("(?=(\\+|-))");

    // Here, we make a stream of our split, so we can use Stream operations like map and reduce
    Optional<Integer> sum = Stream.of(allNumbersWithSign)
        // The map operation parses each string, so +9 will give Int:9 and -8 will give Int:8
        .map(Integer::parseInt)
        // The reduction sums all the element
        .reduce((a, b) -> a
            + b);

    // The result is an Optional<Int> and the -1 is really there for decoration
    return sum.orElse(-1);
  }

  public void run() {
    // Generate all possible expressions
    generateCombinations().stream()
        // Keep only the ones that evaluate to 100
        .filter(expr -> (evaluateExpression(expr) == 100))
        // Print them
        .forEach(System.out::println);
  }

  public static void main(String[] args) {
    new AllCombi(1, 9).run();
  }

}
\$\endgroup\$
3
  • \$\begingroup\$ You can create use mapToInt and use sum() on your stream as well :). Guess it will be somewhat slow because of all the String manipulation and regex matching. \$\endgroup\$ Sep 20, 2017 at 13:26
  • \$\begingroup\$ Yes, but it would neither showcase the generic map() and reduce(), neither the regular expressions I advocate to learn :) BTW, you could also directly generate a List<List<Integer>> when generating the combinations, thus not using any matching at all, an exercise left to the OP :) \$\endgroup\$ Sep 20, 2017 at 14:16
  • \$\begingroup\$ At least reduce with a nice .reduce(0, Integer::sum); then to show off method-references :) \$\endgroup\$ Sep 20, 2017 at 15:09
0
\$\begingroup\$

Check my solution:

public class Main {

    static final String input = "123456789";

    private static void search(
            String str,    // the part of the input processed so far
            int sum,       // intermediate sum
            int start,     // start of a current operand
            int pos,       // current position in the input string
            boolean sign)  // signum (+ or -)
   {
        String operand = input.substring(start, pos);
        int opInt = Integer.parseInt(operand);
        if (pos == input.length()) {
            sum = sum + (sign ? opInt : -opInt);
            if (sum == 100)
                System.out.println(str + operand + "=100");
            return;
        }
        // skip sign
        search(str, sum, start, pos+1, sign);
        // calculate an intermediate sum
        sum = sum + (sign ? opInt : -opInt);
        // continue with next operand
        // add +
        search(str + operand + "+", sum, pos, pos+1, true);
        // add -
        search(str + operand + "-", sum, pos, pos+1, false);
    }

    public static void main(String[] args) {
        search("", 0, 0, 1, true);
    }
}

It works more then 1000 times faster (7 millis vs. 9 sec on my CPU).

I hope it is well documented.

Other respondents already answered how to learn to optimize a performance, I cannot add anything else here.

\$\endgroup\$
0
\$\begingroup\$

Other answer, if this is an assignment, and the wording does not explicitly asks you to compute the values :

    System.out.println("123+45-67+8-9=100\r\n" +
        "123+4-5+67-89=100\r\n" +
        "123-45-67+89=100\r\n" +
        "123-4-5-6-7+8-9=100\r\n" +
        "12+3+4+5-6-7+89=100\r\n" +
        "12+3-4+5+67+8+9=100\r\n" +
        "12-3-4+5-6+7+89=100\r\n" +
        "1+23-4+56+7+8+9=100\r\n" +
        "1+23-4+5+6+78-9=100\r\n" +
        "1+2+34-5+67-8+9=100\r\n" +
        "1+2+3-4+5+6+78+9=100\r\n");

Always a hit :)

\$\endgroup\$
1
  • \$\begingroup\$ A shame people always target Windows :) \$\endgroup\$ Sep 20, 2017 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.