Brainfuck Brute Force

Question

I am trying to brute force code Brainfuck code to get the desired output. For this, I need my code to be as fast as possible. I am fairly new to Java and making my code fast, in general, so don't assume that I have done something for a good reason.

import java.util.regex.Pattern;
public class BruteForceBF {
    public static class Patterns {
        final static Pattern first = Pattern.compile("\\[[^+-]*\\]");
        final static Pattern second = Pattern.compile("\\[[+-]\\]");
        final static Pattern third = Pattern.compile("\\[[+-]*\\]");
    }
    public static String interpret(String code) {
        final int LENGTH = 255;
        final int MAXNUM = 255;
        final int MAXLOOP = countOccurrences(code, '[') == 1 ? 256 : 65536;
        int[] mem = new int[LENGTH];
        int dataPointer= 0;
        int l = 0;
        int loops = 0;
        String output = "";
        for(int i = 0; i < code.length(); i++) {
            if(code.charAt(i) == '>') {
                dataPointer = (dataPointer == LENGTH-1) ? 0 : dataPointer + 1;
            } else if(code.charAt(i) == '<') {
                dataPointer = (dataPointer == 0) ? LENGTH-1 : dataPointer - 1;
            } else if(code.charAt(i) == '+') {
                if (mem[dataPointer] != MAXNUM) {
                    mem[dataPointer]++;
                } else {
                    mem[dataPointer] = 0;
                }
            } else if(code.charAt(i) == '-') {
                if (mem[dataPointer] != 0) {
                    mem[dataPointer]--;
                } else {
                    mem[dataPointer] = MAXNUM;
                }
            } else if(code.charAt(i) == '.') {
                output += (char) mem[dataPointer];
            } else if(code.charAt(i) == '[') {
                if(mem[dataPointer] == 0) {
                    i++;
                    while((l > 0 || code.charAt(i) != ']') && i < MAXNUM) {
                        if(code.charAt(i) == '[') l++;
                        if(code.charAt(i) == ']') l--;
                        i++;
                    }
                }
            } else if(code.charAt(i) == ']') {
                if(mem[dataPointer] != 0 && loops < MAXLOOP) {
                    loops++;
                    i--;
                    while(l > 0 || code.charAt(i) != '[') {
                        if(code.charAt(i) == ']') l++;
                        if(code.charAt(i) == '[') l--;
                        i--;
                    }
                    i--;
                }
            }
        }
    return output;
    }
    public static int countOccurrences(String haystack, char needle) {
        int count = 0;
        for (int i=0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle) {
                 count++;
            }
        }
        return count;
    }
    public static Boolean checkBrackets(String code){
        int openParens = 0;
        for (int i=0; i<code.length(); i++) {
            char chr = code.charAt(i);
            if (chr == '[') {
                openParens++;
            } else if (chr == ']') {
                if (openParens == 0) {
                    return false;
                } else {
                    openParens--;
                }
            }
        }
        return openParens == 0;
    }
    public static boolean pass(String code) {
        return code.contains("+-") || code.contains("-+") || code.contains("[]") || 
                code.contains("][") ||code.contains("><") || code.contains("<>") || 
                Patterns.first.matcher(code).find() || 
                (!Patterns.second.matcher(code).find() && 
                        Patterns.third.matcher(code).find());
    }
    public static String BruteForce(String text, int time, int pos) {
        System.out.println("Starting to Brute Force " + text);
        long start = System.currentTimeMillis();
        int i = pos - 1;
        String finalCode = "";
        while (System.currentTimeMillis() - start < time) {
            i++;
            String code = Integer.toOctalString(i);
            if (code.contains("7")) {continue;}
            code = code.replace("0", "+"); 
            code = code.replace("1", "-"); 
            code = code.replace("2", "[");
            code = code.replace("3", "]");
            code = code.replace("4", ">");
            code = code.replace("5", "<");
            code = code.replace("6", ".");
            if (!code.contains(".")) {continue;}
            else if (countOccurrences(code, '[') != countOccurrences(code, ']')) {continue;}
            else if (!((code.startsWith("+")||code.startsWith("-"))&&(code.endsWith("+")||code.endsWith("-")||code.endsWith(".")||code.endsWith("]")))) {continue;}
            else if (countOccurrences(code, '.') > text.length()) {continue;}
            else if (!checkBrackets(code)) {continue;}
            else if (pass(code)) {continue;}
            String value;
            try {value = interpret(code);}
            catch (Exception e) {value = "";}
            if (value.equals(text)) {
                finalCode = code;
                break;
            }
        }
        if (finalCode != "") {
            return finalCode;
        } else {
            return "Was not given enough time to finish, ended at " + Integer.toString(i);
        }
    }
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(BruteForce("Hello World", 1000, 289830));
        long end = System.currentTimeMillis();
        System.out.println("Done, started at " + Long.toString(start) + " ended at " + Long.toString(end) + " which is " + Long.toString(end-start));
    }

}

I am using the Patterns class so that the patterns do not have to be compiled multiple times. The BruteForceBF function takes the text to be generated, the starting position, and the max time (in milliseconds) to allow the program to run. If the max time is used before the program is found, then it will output how far it got so that the next time I run it I can put the end position as the place where the function should start so that it can start where it left off the next time it is run. If it helps I am running the code on a Mac, with Eclipse.

Answer 1

I am trying to brute force code Brainfuck code to get the desired output.

For this, I need my code to be as fast as possible.

I am sorry, but those two statements are impossible to combine. If you want a fast approach, don't purely brute-force. The shortest program known at the moment to produce "Hello, World" in Brainfuck is 78 bytes, and something that your brute force approach would not be able to produce in a realistic period of time. Instead I would suggest making a mathematical approach to the problem.

---

As for your code itself, some general suggestions:

• first, second and third are lousy names. Describe what each pattern is used for instead.
• You don't need the Patterns class to have your Pattern constants, they can be stored in your outer class.
• Avoid making everything static. Flexible programs comes from having objects that you manipulate and pass around.
• Use System.nanoTime to check how much time has passed. System.currentTimeMillis() is dependent on your computer calendar, if you modify your system time during the process you will confuse your program.
• Avoid those code = code.replace("0", "+"); statements. Searching and replacing in strings is not very fast (although considering the algorithm, you will not notice much difference). As you are the one generating your code in the first place, put a + there instead of a 0.