3

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!

2
  • 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 '18 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 – colossal Apr 24 '18 at 15:49
1

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .