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

Question

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!

Answer 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.