How can I shorten the processing time of my (very basic) bruteforce algorithm?

Question

I'm learning java atm and I am kinda stuck at the current task, that my trainer gave me yesterday...

The exercise is:

1. Create a 4 digit password (Just as String variable). (Allowed are numbers between 0-9 and one ore more of these special chars: '!','#','%')
2. Find a way to bruteforce the password, by going through all possibilities.
3. Measure and output the time that it took for processing.
4. Additionally, output how many "tries" it needed to find the password.

(My trainer said that I should use as less methods as possible, because I don't even now yet how to write methods or how to use classes, etc.)

I managed it to work, but at how it is now, it takes about 60ms to go through the loops. My trainer now told me, that I should try to make it process faster, so that it takes about 20ms minimum.

I already now what makes my code slow. Its because i ALWAYS go through ALL possibilities, add ALL OF THEM into an ArreyList and THEN I check, if the pw matches with one of those possibilities in the ArreyList. Waste of time. Now my goal is to go through the possibilities like i did before, but ONLY until the password is found. After that, it should brake the loop, so that it also stops adding the rest of the unnecessary combinations. I tried and tried, but now I decided to call for help :)

That's my code:

        import java.util.ArrayList;
        import java.util.Scanner;

        public class trynew {
        public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);

        char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

        System.out.println("\nPlease create 4 digit password. Allowed are numbers between 0-9 and following characters: #,!,%");

        String passw = scn.nextLine();

        ArrayList<String> check_it = new ArrayList<String>();

        long start1 = System.currentTimeMillis();

        for (int i = 0; i < digits.length; i++) {
            for (int j = 0; j < digits.length; j++) {
                for (int k = 0; k < digits.length; k++) {
                    for (int l = 0; l < digits.length; l++) {
                        check_it.add(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]);
                    }
                }
            }
        }

        long end1 = System.currentTimeMillis();

        for (String sv : check_it) {
            if (sv.equals(passw)) {
                System.out.println("\nThe Password is: " + sv);
                System.out.println("It took " + check_it.indexOf(sv) + " tries, to find the password.");
            }
        }
        System.out.println("Process time was " + (end1 - start1) + " milliseconds.");


        }
    }




My approach  was to make the loop like that:

    for (int i = 0; i < digits.length; i++) { 
        for (int j = 0; j < digits.length; j++) {
            for (int k = 0; k < digits.length; k++) {
                for (int l = 0; l < digits.length; l++) {

                   if (!(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw)){
                        check_it.add(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]);
                    }

                }
            }
        }
    }

Then I tried using a while loop instead of the if, I tried setting booleans, etc. I also managed that it only adds combinations until pw is found, but somehow the processing time won't go down :/

The reason why I want to add the combos into check_it ArreyList is because otherwise, I wouldn't now how I get the numbers of tries it took, until pw is found...

Can someone help me please, or poke me at the right direction?! Thanks & Greets!

Answer 1

Here's what I came up with.

private static final char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

public static int guessPw(String pw) {
    int attempts = 0;
    char [] word = new char[pw.length()];
    for (char a : digits) {
        word[0] = a;
        for (char b : digits) {
            word[1] = b;
            for (char c : digits) {
                word[2] = c;
                for (char d : digits) {
                    word[3] = d;
                    attempts++;
                    if (pw.equals(String.valueOf(word))) {
                        return attempts;
                    }
                }
            }
        }
    }
    return -1;
}

public static void timeAttempt(String pw) {     
    long start = System.nanoTime();
    int attempts = guessPw(pw);

    
    System.out.println(String.format("It took %dms and %d attempts to guess '%s'", TimeUnit.MILLISECONDS.toSeconds(System.nanoTime() - start), attempts, pw));
}
public static void main(String[] args) {
    timeAttempt("0000");
    timeAttempt("%%%%");
}

Answer 2

This code should work. It just breaks every loop if the password has been found.

   int tries = 0;
   boolean found = false;
   for (int i = 0; i < digits.length; i++) {
            for (int j = 0; j < digits.length; j++) {
                for (int k = 0; k < digits.length; k++) {
                    for (int l = 0; l < digits.length; l++) {
                        tries++;
                        if ((digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw)) {
                           found = true;
                           break;
                        }
                    }
                    if (found)
                      break;
                }
               if (found)
                  break;
            }
            if (found)
                  break;
        }

I wouldn't recommend to use this code tho! It's pretty sketchy. Why don't you make the for loops a function? From there you can return the tries when you find the password. But I think you can figure this out on your own :)

EDIT: I'll give you an hint for a solution without a function. What do you think about this while loop?

while(!(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw))

In there you just need to 'grow' l, k, j and i in the right order :)

Answer 3

The reason why its processing so slow is because all of your code is running in a single thread. You can greatly reduce the overall processing time by making the brute force code multi threaded.

Another reason why your application is running slow is because it uses many nested loops to determine all the possible combinations of digits. Instead of using those nested loops its better to calculate the permutation of digits.

Once you have a list of all possible permutations you could use java 8's parallelStream() and anyMatch() to check which permutation matches the password in a multithreaded way. In other words the computer will be able to match 2 or more permutations with pass simultaneously which will greatly reduce the processing time. Below is an example that uses parallelStream()/anyMatch().

    AtomicInteger threadSafeCounter = new AtomicInteger(); //Always use a thread safe integer when multiple threads will be manipulating it. This is to avoid race conditions.

    char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

    Scanner scn = new Scanner(System.in);

    System.out.println("\nPlease create 4 digit password. Allowed are numbers between 0-9 and following characters: #,!,%");

    String passw = scn.nextLine();

List<String> permutationList = new ArrayList(); //Calculate the 4-digit permutations from `digits` and add them to this list.

    long start1 = System.currentTimeMillis();
    permutationList.parallelStream().anyMatch(combination -> {
        threadSafeCounter.incrementAndGet();
        if(combination.equals(passw)){
            System.out.println("\nthe password is " + passw);
            System.out.println("It took " + threadSafeCounter.get() + " tries, to find the password.");
            return true;
        }
        else return false;
    });

    long end1 = System.currentTimeMillis();

    System.out.println("Process time was " + (end1 - start1) + " milliseconds.");

You can find an example on how to generate permutations from digits in this in this SO thread. The permutation generation code itself could be made multithreaded as well if you adapt the code posted by Subash in the aforementioned SO thread. To do that you need to use the Fork/Join framework.

EDIT: Heres a nice article that explains the difference between permutations and combinations. The reason why i'm calculating permutations and not combinations in my example is because order/arrangement matters in this case.

Answer 4

Very similar to what Ryan posted. Basically you want to avoid creating a STRING.

Here I converted the entered password to a char array and compare the entered password with the generated password using Arrays.equals():

  public static void main(String[] args) {       
    Scanner scn = new Scanner(System.in);

    char[] digits = {'0', '1', '2', '3', '4', '5', '6', 
                     '7', '8', '9', '#', '!', '%'};

    System.out.println("\nPlease create 4 digit password.");
    System.out.println("Allowed are numbers between 0-9 and following characters: #,!,%");
    System.out.print("Password: ");
    
    String response = scn.nextLine();
    char[] password = response.toCharArray();
    
    long start1 = System.currentTimeMillis();

    int counter = 0;
    char[] pw = new char[4];
    boolean foundIt = false;
    for (int i = 0; i < digits.length && !foundIt; i++) {
        pw[0] = digits[i];
        for (int j = 0; j < digits.length && !foundIt; j++) {
            pw[1] = digits[j];
            for (int k = 0; k < digits.length && !foundIt; k++) {
                pw[2] = digits[k];
                for (int l = 0; l < digits.length && !foundIt; l++) {
                  counter++;
                  pw[3] = digits[l];
                  foundIt = Arrays.equals(pw, password);
                }
            }
        }
    }
  
    long end1 = System.currentTimeMillis();

    System.out.println("\nThe Password is: " + response);
    System.out.println("It took " + counter + " tries, to find the password.");

    System.out.println("Process time was " + (end1 - start1) + " milliseconds.");
  }

Answer 5

Your approach of breaking out of the loop once the password is found is a step in the right direction. However, the issue with your current code is that it still generates all the possible combinations before checking if the password is found, which can be quite time-consuming.

Instead, you can modify your loop to check each combination as it is generated, and break out of the loop once the password is found. Here is one way you can do it:

String foundPassword = null;
int numTries = 0;

long startTime = System.currentTimeMillis();

for (int i = 0; i < digits.length; i++) {
    for (int j = 0; j < digits.length; j++) {
        for (int k = 0; k < digits.length; k++) {
            for (int l = 0; l < digits.length; l++) {
                String combination = digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l];
                numTries++;
                if (combination.equals(passw)) {
                    foundPassword = combination;
                    break;
                }
            }
            if (foundPassword != null) {
                break;
            }
        }
        if (foundPassword != null) {
            break;
        }
    }
    if (foundPassword != null) {
        break;
    }
}

long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;

if (foundPassword != null) {
    System.out.println("\nThe Password is: " + foundPassword);
    System.out.println("It took " + numTries + " tries, to find the password.");
} else {
    System.out.println("Password not found.");
}
System.out.println("Process time was " + elapsedTime + " milliseconds.");