I'm learning java atm and I am kinda stuck at the current task, that my trainer gave me yesterday...
The exercise is:
- Create a 4 digit password (Just as String variable). (Allowed are numbers between 0-9 and one ore more of these special chars: '!','#','%')
- Find a way to bruteforce the password, by going through all possibilities.
- Measure and output the time that it took for processing.
- 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!
CodePudding user response：
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("%%%%");
}
CodePudding user response：
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 :)
CodePudding user response：
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.
If your app has the org.apache.commons.collections4 library as a dependency then you can easily calculate all the permutations of digits with CollectionUtils.permutations(). 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 apache and 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();
long start1 = System.currentTimeMillis();
CollectionUtils.permutations(Arrays.asList(digits)).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.");
If your application does not have org.apache.commons.collections4 as a dependency and you don't want to add it, then you can also generate the permutations of digits in your own code. You can find an example on how to do that 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.