4
\$\begingroup\$

I came across this mathematical puzzle, where one really cool answer was a python script to brute force answers.

Here's my take, which is essentially a translation of that to Java:

public class TerribleMath {

    public static void main(String[] args) {
        findAndPrintSolutions(1, 20);
    }

    private static void findAndPrintSolutions(int from, int to) {
        for (int a = from; a < to; a++) {
            for (int b = from; b < to; b++) {
                for (int c = from; c < to; c++) {
                    for (int d = from; d < to; d++) {
                        for (int e = from; e < to; e++) {
                            for (int f = from; f < to; f++) {
                                for (int g = from; g < to; g++) {
                                    for (int h = from; h < to; h++) {
                                        if (isSolution(a, b, c, d, e, f, g, h))
                                            printSolution(new int[] { a, b, c, d, e, f, g, h });
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g, int h) {
        if (a + b - 9 != 4)
            return false;
        if ((c - d) * e != 4)
            return false;
        if (f + g - h != 4)
            return false;
        if ((a + c) / f != 4)
            return false;
        if ((b - d) * g != 4)
            return false;
        if (9 - e - h != 4)
            return false;
        return true;
    }

    private static void printSolution(int[] variables) {
        StringBuilder output = new StringBuilder();
        for (int variable : variables) {
            output.append(variable + ", ");
        }
        output.deleteCharAt(output.length() - 1);
        output.deleteCharAt(output.length() - 1);
        System.out.println(output.toString());
    }
}

There are a few ways of abusing the findAndPrintSolutions method that I know of. Also, I get the feeling it could be recursive, although I'm not sure exactly how to write that. Lastly, the class name comes from the fact that the puzzle had to be solved by not doing operations in the pemdas order.

\$\endgroup\$
  • 1
    \$\begingroup\$ We can see in the answers that you found a bug, there's no need to say "Edit found a bug" in the question. \$\endgroup\$ – Simon Forsberg Oct 10 '16 at 13:43
7
\$\begingroup\$

If willing to mix the solution checking logic into the candidate generation logic, we can do better if we drop the requirement that we brute force the entire answer.

private static void findAndPrintSolutions(int from, int to) {
    for (int a = from; a < to; a++) {
        // if a + b - 9 == 4, then 
        int b = 13 - a;
        if (from > b || b > to) {
            continue;
        }

        for (int c = from; c < to; c++) {
            // if (a + c) / f == 4
            int f = (a + c) / 4;
            if (from > f || f > to) {
                continue;
            }

            for (int d = from; d < to; d++) {
                if (c == d || b == d) {
                    // these cause divide by zero errors later, so skip them
                    continue;
                }

                // if (c - d) * e == 4
                int e = 4 / (c - d);
                if (from > e || e > to) {
                    continue;
                }

                // if (b - d) * g == 4
                int g = 4 / (b - d);
                if (from > g || g > to) {
                    continue;
                }

                // if 9 - e - h == 4
                int h = 5 - e;
                if (from > h || h > to) {
                    continue;
                }

                if (isSolution(a, b, c, d, e, f, g, h)) {
                    printSolution(new int[] { a, b, c, d, e, f, g, h });
                }
            }
        }
    }
}

This would drop us from 25,600,000,000 iterations of the innermost loop to 8000 with a modest increase in complexity per iteration. This works because the equations in the solution checker tell us constraints that we can use to determine some of the variables if we have others (comments in the code with more specific explanations). With sufficient algebra you might eliminate one of the remaining three loops as well. Note that we have an additional equation that we are not using (f + g - h == 4).

Added logic to verify that the calculated variables are within the from/to range. This doesn't seem to have been necessary for this particular problem, but that seems likely to have been just luck. I think that you could probably demonstrate that by setting from to 1 and to to 6.

\$\endgroup\$
  • \$\begingroup\$ You could even check that from <= b && b < to and f * 4 == a + c to save some more time. \$\endgroup\$ – Roland Illig Apr 19 '16 at 6:04
  • \$\begingroup\$ Yes, but what's stopping the integer division error from accidentally creating a candidate? \$\endgroup\$ – Amani Kilumanga Apr 20 '16 at 5:57
  • 1
    \$\begingroup\$ The a, c, and d variables aren't created by division. The other variables are created deterministically from those three. So each candidate has different a, c, and d values. The other five values may be wrong, but they can't make a duplicate candidate because the three are different. In order to get a duplicate, you need all eight variables to be the same. But integer division can only mess up three of them (the ones with division). If we calculated all eight variables, then we'd need to worry. But we don't. \$\endgroup\$ – mdfst13 Apr 20 '16 at 6:03
3
\$\begingroup\$

Simplifying conditionals

if (a + b - 9 != 4)
    return false;
if ((c - d) * e != 4)
    return false;
if (f + g - h != 4)
    return false;
if ((a + c) / f != 4)
    return false;
if ((b - d) * g != 4)
    return false;
if (9 - e - h != 4)
    return false;
return true;

You can chain the conditions with && to keep it more succinct:

return (a + b - 9 == 4)
    && ((c - d) * e == 4)
    && (f + g - h == 4)
    && ((a + c) / f == 4)
    && ((b - d) * g == 4)
    && (9 - e - h == 4);

Varargs

Since Java 1.5, you can use varargs so that you don't need an explicit int[] array:

// usage
printSolution(a, b, c, d, e, f, g, h);

private static void printSolution(int... variables) {
    StringBuilder output = new StringBuilder();
    for (int variable : variables) {
        output.append(variable + ", ");
    }
    // why - 1 twice? because char (thanks @mdfst13)
    // output.deleteCharAt(output.length() - 1);
    // output.deleteCharAt(output.length() - 1);
    // System.out.println(output.toString());
    System.out.println(output.substring(0, output.length() - 2));
}

Actually, if you are on Java 8, that can be a little simpler with the help of IntStream

private static void printSolution(int... variables) {
    System.out.println(IntStream.of(variables)
                                .mapToObj(String::valueOf)
                                .collect(Collectors.joining(", ")));
}

We convert each int element of the IntStream using String::valueOf as a method reference, then joining() them together using ", ".

\$\endgroup\$
  • \$\begingroup\$ Wow. Didn't know about varargs, and nice catch on the substring. Not sure if I like IntStream yet (looks a bit cluttered). But awesome nonetheless. \$\endgroup\$ – Amani Kilumanga Apr 19 '16 at 3:34
3
\$\begingroup\$

If you want to get rid of nesting, I'd start by changing from eight variables to an array. So

    private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g, int h) {
        if (a + b - 9 != 4)
            return false;
        if ((c - d) * e != 4)
            return false;
        if (f + g - h != 4)
            return false;
        if ((a + c) / f != 4)
            return false;
        if ((b - d) * g != 4)
            return false;
        if (9 - e - h != 4)
            return false;
        return true;
    }

would become

    private static boolean isSolution(int[] variables) {
        if (variables[0] + variables[1] - 9 != 4) {
            return false;
        }

        if ((variables[2] - variables[3]) * variables[4] != 4) {
            return false;
        }

        if (variables[5] + variables[6] - variables[7] != 4) {
            return false;
        }

        if ((variables[0] + variables[2]) / variables[5] != 4) {
            return false;
        }

        if ((variables[1] - variables[3]) * variables[6] != 4) {
            return false;
        }

        if (9 - variables[4] - variables[7] != 4) {
            return false;
        }

        return true;
    }

Added {} and whitespace for ease of future reading and editing.

Or the simpler (as in the @h.j.k. answer)

    private static boolean isSolution(int[] variables) {
        return  (variables[0] + variables[1] - 9 == 4) 
             && ((variables[2] - variables[3]) * a[4] == 4)
             && (variables[5] + variables[6] - variables[7] == 4) {
             && ((variables[0] + variables[2]) / variables[5] == 4) {
             && ((variables[1] - variables[3]) * variables[6] == 4) {
             && (9 - variables[4] - variables[7] == 4);
    }

And with a little algebra

    private static boolean isSolution(int[] variables) {
        return  (variables[0] + variables[1] == 13) 
            && ((variables[2] - variables[3]) * variables[4] == 4)
            && (variables[5] + variables[6] - variables[7] == 4)
            && ((variables[0] + variables[2]) / variables[5] == 4)
            && ((variables[1] - variables[3]) * variables[6] == 4)
            && (5 == variables[4] + variables[7]);
    }

Why do the extra math on each iteration?

Any of these allow you to call this with an array as in

    private void findAndPrintSolutions(int[] variables, int current) {
        if (current >= variables.length) {
            if (isSolution(variables)) {
                printSolution(variables);
            }

            return;
        }

        for (int i = from; i < to; i++) {
            variables[current] = i;
            findAndPrintSolutions(variables, current + 1);
        }
    }

The printSolution method already took an array, so this was consistent.

I also moved to and from into field variables as they never change.

I called this from

    public void findAndPrintSolutions() {
        findAndPrintSolutions(new int[SIZE], 0);
    }

Note that I changed this from private to public so that it could be used outside this class while I left the recursive method only accessible from this class.

General purpose

This is going to be slower, as it adds additional overhead to the original iterative solution. But the real advantage of a recursive solution is adaptability. So let's keep going.

CHARGE!

We can define an interface:

public interface SolutionChecker {

    public boolean isSolution(Integer[] variables);
    public int getSize();
    public int getTo();
    public int getFrom();

}

This allows us to abstract away from any particular solution. In this example, we could implement it as something like

public class TerribleMathSolutionChecker implements SolutionChecker {

    private final int SIZE = 8;
    private final int TO;
    private final int FROM;

    public TerribleMathSolutionChecker(int from, int to) {
        FROM = from;
        TO = to;
    }

    @Override
    public boolean isSolution(Integer[] variables) {
        return (variables[0] + variables[1] == 13) 
                && ((variables[2] - variables[3]) * variables[4] == 4)
                && (variables[5] + variables[6] - variables[7] == 4)
                && ((variables[0] + variables[2]) / variables[5] == 4)
                && ((variables[1] - variables[3]) * variables[6] == 4)
                && (5 == variables[4] + variables[7]);
    }

    @Override
    public int getSize() {
        return SIZE;
    }

    @Override
    public int getTo() {
        return TO;
    }

    @Override
    public int getFrom() {
        return FROM;
    }

}

Hardcoded the size, as it needs to match isSolution.

So we can handle terrible math today and rather swell math tomorrow. We aren't stuck writing one off code that we'll never use again. So here's our brute force solver:

public class BruteForceSolver {

    private final SolutionChecker checker;
    private final List<Integer[]> solutions = new ArrayList<>();

    public BruteForceSolver(SolutionChecker checker) {
        this.checker = checker;
    }

    private void solve() {
        solve(new Integer[checker.getSize()], 0);
    }

    private void solve(Integer[] variables, int current) {
        if (current >= variables.length) {
            if (checker.isSolution(variables)) {
                solutions.add(variables.clone());
            }

            return;
        }

        for (int i = checker.getFrom(), n = checker.getTo(); i < n; i++) {
            variables[current] = i;
            solve(variables, current + 1);
        }
    }

    private static void printSolution(Integer[] solution) {
        StringBuilder output = new StringBuilder();
        output.append(solution[0]);
        for (int i = 1; i < solution.length; i++) {
            output.append(", " + solution[i]);
        }

        System.out.println(output.toString());
    }

    public void printSolutions() {
        for (Integer[] solution : solutions) {
            printSolution(solution);
        }
    }

}

which we can use with something like

    public static void main(String[] args) {
        BruteForceSolver problem = new BruteForceSolver(new TerribleMathSolutionChecker(1, 20));
        problem.solve();
        problem.printSolutions();
    }

Note that I also separated output from solving here. That makes the code more reusable. I can solve without printing or print without solving again.

You may recognize the pattern used. It's essentially the same one as used with sorting using a custom Comparator. Define an interface and implement it to allow reuse of common logic for multiple problems.

\$\endgroup\$
1
\$\begingroup\$
private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g, int h) {
    if (a + b - 9 != 4)
        return false;
    if ((c - d) * e != 4)
        return false;
    if (f + g - h != 4)
        return false;
    if ((a + c) / f != 4)
        return false;
    if ((b - d) * g != 4)
        return false;
    if (9 - e - h != 4)
        return false;
    return true;
}

The above method is bugged in cases where all equations evaluate and a + c / f evaluates to a decimal, where the integer-part is a 4. This can be solved by refactoring (a + c) / f != 4 as a + c != 4 * f.

This also allows for solutions where either variable is equal to 0.

Combine the above with @mdfst13's answer (the part about not doing unnecessary calculations) and @h.j.k.'s answer (chaining conditionals), and you have a reliable method to check if any int combination makes a solution.

private boolean isSolved(int a, int b, int c, int d, int e, int f, int g, int h) {
    return (a + b - 9 == 4) && ((c - d) * e == 4) && (f + g - h == 4) && ((a + c) == 4 * f) && ((b - d) * g == 4)
            && (9 - e - h == 4);
}
\$\endgroup\$
0
\$\begingroup\$

Because if statements are apparently slow, use bitwise operations:

private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g, int h) {

    int result = ((a + b) ^ 13);
    result |= ((c - d) * e) ^ 4;
    result |= (f + g - h) ^ 4;
    result |= ((a + c) / f) ^ 4;
    result |= ((b - d) * g ) ^ 4;
    result |= (e + h) ^ 5;

    return result == 0;
}

Because of how if statements are processed, it involves the starting and stopping of the processing which slows things down (if I read that article right). I believe the analogy of a train coming to a fork in the tracks being too slow to stop. Bitwise operations eliminate this.

\$\endgroup\$
  • \$\begingroup\$ By "that article", are you referring to the top-voted answer on SO? \$\endgroup\$ – Amani Kilumanga Apr 20 '16 at 1:42
  • \$\begingroup\$ Clarify, what's SO? \$\endgroup\$ – Jean Valjean Apr 20 '16 at 1:42
  • \$\begingroup\$ stack overflow \$\endgroup\$ – Amani Kilumanga Apr 20 '16 at 1:43
  • 1
    \$\begingroup\$ I saw it on an MIT research articles about optimization in processing and it touched on the if/else statement. I take it he read the same article \$\endgroup\$ – Jean Valjean Apr 20 '16 at 1:50
  • 3
    \$\begingroup\$ This answer could maybe benefit from some benchmarking stats. Oh and if you could link that article (or quote it) for reference, that would be helpful. \$\endgroup\$ – Amani Kilumanga Apr 20 '16 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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