# PSET 2 - Can Crack be implemented for 5 characters in a more efficient way?

Okay, so I've finished the crack problem, and it runs, but since the pset2 now tells us the passwords can be upto 5 characters long, it takes about 48 minutes to get the password match for "zzzzz".

I have to use a lot of nested for loops, and since it has to check for all the character lengths, it's slowing down the program. And, recursion will end up being slow too so I can't do that either.

Is there a more efficient way to solve this that would take considerably less time?
I also can't figure out if there are ways to not use nested for loops. Please help!

• Great question. I'm assuming the brute force approach is what is necessary to move forward on this problem. If there are 52 possible letters used in a password, then that's 52^5 comparisons...Does anyone have any recommended resources for reading on this to come up with a more elegant solution?
– wlh
Feb 21, 2018 at 18:53
• A common approach in password cracking is to try hashing the entries of a dictionary first, before resulting to brute forcing random combinations. en.wikipedia.org/wiki/Dictionary_attack Apr 24, 2018 at 15:49

I'm not sure if this is faster, but it is an alternative to nesting loops:

``````#include <stdio.h>

#define FIRST_CHAR 'a'
#define LAST_CHAR 'f'
#define MAX_LENGTH 4

// This just makes the type bool actually exist
// cs50.h has a line that does just this
typedef enum {false, true} bool;

bool cycle(char s[]);

int main(void)
{
char s[MAX_LENGTH + 1] = {'\0'}; // Initialise all values to \0
s[0] = FIRST_CHAR; // Set first char

int cycle_return_value;

do
{
// Do something
printf("%s\n", s);

cycle_return_value = cycle(s);
}
while (cycle_return_value);
}

bool cycle(char s[])
{
/****************************************
* Iterate through chars in string s
***************************************/
for (int i = 0; s[i] != '\0'; i++)
{
/****************************************
* Check if string should be expanded AND
* That doing so will not pass MAX_LENGTH
* NOTE: The second part of checking if
* string should be expanded is not
* included here as it is irrelevent
***************************************/
if (s[i] == LAST_CHAR && i + 1 >= MAX_LENGTH)
{
return false; // Return error
}
/****************************************
* Check if string should be expanded
***************************************/
else if (s[i] == LAST_CHAR && s[i + 1] == '\0')
{
s[i] = FIRST_CHAR; // Roll LAST_CHAR over to FIRST_CHAR
s[i + 1] = FIRST_CHAR; // Expand string
break;
}
/****************************************
* Since string should not be expanded
* roll-over LAST_CHAR to FIRST_CHAR
***************************************/
else if (s[i] == LAST_CHAR)
{
s[i] = FIRST_CHAR; // Roll LAST_CHAR over to FIRST_CHAR
}
/****************************************
* If all else is not needed, simply increment
* the current char
***************************************/
else
{
s[i]++; // Iterate it
break;
}
}

// Return success
return true;
}
``````

While you'll have to adapt this to accommodate to the specific problem, this is the essence of one possible solution.