Brainfuck Brute力

Question

我试图蛮力代码Brainfuck代码，以获得所需的输出。为此，我需要我的代码尽可能快。一般来说，我对Java相当陌生，而且代码编写得很快，所以不要以为我做某事是有充分理由的。

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));
    }

}

我使用Patterns类，这样就不必对模式进行多次编译。BruteForceBF函数获取要生成的文本、起始位置和允许程序运行的最大时间(毫秒)。如果在找到程序之前使用了最大时间，那么它将输出它达到了多远，以便在下次运行它时，我可以将结束位置作为函数应该启动的位置，以便它可以在下次运行时停止运行。如果有帮助的话，我会在Mac上用Eclipse运行代码。

Answer 1

我试图蛮力代码Brainfuck代码，以获得所需的输出。为此，我需要我的代码尽可能快。

对不起，这两种说法是不可能结合在一起的。如果你想要一个快速的方法，不要纯粹的蛮力。最短的程序，目前已知的生产“你好，世界”在Brainfuck 是78个字节，和一些东西，你的蛮力方法将无法在一个现实的时间内产生。相反，我建议用数学的方法来解决这个问题。

至于您的代码本身，一些一般性建议：

• first，second和third都是糟糕的名字。请描述每种模式的用途。
• 您不需要Patterns类来拥有模式常量，它们可以存储在外部类中。
• 避免让一切都变成static。灵活的程序来自于拥有您操作和传递的对象。
• 使用System.nanoTime检查已经过去了多少时间。System.currentTimeMillis()依赖于您的计算机日历，如果在此过程中修改系统时间，则会混淆程序。
• 避免那些code = code.replace("0", "+");语句。在字符串中搜索和替换不是很快(尽管考虑到算法，您不会注意到有什么不同)。由于您首先是生成代码的人，所以将+放在那里而不是0。