I am trying to write a program to find a zip file's password. I know the password consists of only lower-case letters and it's length does not exceed 6 characters. I wanted to check the passwords of length 1 first, then length 2 and so on.
So I used breadth first search, but then I realized that BFS consumes so much memory, and std::queue makes things even worse. So I had to switch to depth first search. BUT... depth first search does not check the shortest passwords first. So that's a problem. How can I improve the memory management in my bfs function, Or change my dfs function so that it would check the shortest passwords first (I'm not sure if the latter is even possible)
Also my estimation is that the bfs function would be using about 2 Gigabytes of memory. How can I fix this?
#include <iostream>
#include <queue>
std::string key = "banana";
void checkPassword(std::string s) {
if (s == key) { //example checker function
std::cout << "Password is : " << s << std::endl;
}
}
void bfs(std::string s = "") {
std::queue <std::string> q;
q.push(s);
while(q.size()) {
std::string u = q.front();
checkPassword(u);
q.pop();
if (u.size() < 6) {
for (int i = 'a'; i <= 'z'; i++) {
u += i;
q.push(u);
u.pop_back();
}
}
}
}
void dfs(std::string s = "") {
checkPassword(s);
if (s.size() < 6) {
for (int i = 'a'; i <= 'z'; i++) {
s.push_back(i);
dfs(s);
s.pop_back();
}
}
}
int main() {
dfs();
std::cout << "Finished Time : " << clock() / (double) CLOCKS_PER_SEC;
}