Brute force algorithm for printing all possible alphanumeric combinations

Question

I'm still very much a beginner, so I don't really know much about best practices or the speed of any particular C functions.

You'll notice that I included a "cs50" library. This is from a MOOC I'm taking, all it does in this program is allow me to use their "bool" data type. I realize I don't need to delegate all of this code to so many functions, but this is part of a bigger problem set from said MOOC, where I am to crack a password, so I thought to make the functions now rather than later.

The program loops through and prints all possible iterations of alphanumeric combinations (no uppercase) from length 1-8. The algorithm in its current state is very slow. I've also never run it to the very end:

#include <cs50.h> //GetString, booleans, and string datatype
#include <stdio.h> //printf
#include <string.h> //strlen
#define LOOP_MAX 8
bool BruteForceIntializer();
int looper (int amt, int count);
char engWord[9];
char alphaNum[36] = {"0123456789abcdefghijklmnopqrstuvwxyz"};
int maxSize = sizeof(alphaNum);
int main(void)
{
 if (BruteForceIntializer() == true)
 printf("Success.\n");
 else
 printf("Failure.\n");
}
bool BruteForceIntializer()
{ 
 int count;
 for (int amt = 0; amt < LOOP_MAX; amt++)
 {
 memset(engWord, '0円', 9);
 count = 0;
 if (looper(amt, count) == 0)
 {
 continue;
 } 
 }
 return true; //only exits loop if all chars are looped successfully
}
int looper(int amt, int count)
{
 for(int i = 0; i < maxSize; i++)
 {
 engWord[count] = alphaNum[i];
 if (count == amt) //check if we're at the last character
 {
 printf("%s\n", engWord);
 if (i == (maxSize-1))
 return 0;
 }
 if (count != amt)
 {
 if (looper(amt, count+1) == 0)
 continue;
 }
 }
 return 1;
}

• Hugh Bothwell: I'm not surprised it's slow; you are generating about 2.9 trillion results. At a million combinations a second, that will take slightly more than a month.
• Jon: @HughBothwell :D How could I do this without generating that many results?
• Jon: Math checks out: (36^8) + (36^7) + (36^6) + (36^5) + (36^4) + (36^3) + (36^2) + (36) = 2 901 713 047 668

Answer 1

I must say that this looks pretty clean for a beginner. There are no obvious problems with indentation and whitespace (common with beginners), which is a great start. This especially makes it easier for others to read your code and for reviewers to focus on the more important aspects.

• In most cases, don't use global variables:

  char engWord[9];
  char alphaNum[36] = {"0123456789abcdefghijklmnopqrstuvwxyz"};
  int maxSize = sizeof(alphaNum);
  

  This is highly discouraged because they're exposed to all the code and can be modified from anywhere, making maintenance and debugging much more difficult. Instead, you can just put them in looper() since only that function uses them. That way, if they're modified by accident, you'll know where to look.

  In addition, alphaNum and maxSize should be const since they're not meant to be modified:

  const char alphaNum[36] = {"0123456789abcdefghijklmnopqrstuvwxyz"};
  const int maxSize = sizeof(alphaNum);
  

• Some other issues seem to be with the naming:

  • There is one inconsistency: the naming convention of both non-main functions. It's common for functions in C to start with a lowercase letter (either in camelCase or snake_case), so BruteForceInitializer() should be renamed as such.

  • It doesn't seem to make sense for BruteForceInitializer() to return bool if it's actually initializing something. It looks like this function is doing most of the work anyway. You could consider renaming this function in the verb form, which is common with functions (since they're performing a task). It'll also help the check in main() to make more sense.

  • The name looper() doesn't quite seem clear, especially with the values it returns. Based on the one comment in there, perhaps this function should also return bool.

• Jon: Thanks! The looper function actually does most of the work (I should have made that more clear). The intializer function just calls the looper function, telling it how many times to make a recursive call. The looper function does much more than my single comment alludes to. I should probably comment more. It loops through all the chars in alphaNum. This is only a smaller piece of the problem set, so I will be returning more values than true or false from looper -> which is why I chose to return int. I've implemented your other feedback :) What can be done to improve performance?
• Jamal: @TomJacob: I'm not too sure about performance, but the recursion in looper() may cause a slowdown.
• Jon: How else could this code be implemented? If not using recursion. I wanted to the code to be pretty terse. It's obviously not very terse, but how else would you do it elegantly without recursion?
• Jamal: @TomJacob: I'm not sure how else. The recursion within the iteration just stuck out to me. Someone else may come by and provide a performance review.

Answer 2

I am not quite sure what count is used for in your BruteFourceInitializer it seems to be set to 0 and then passed to looper and never changes its value. It could be instead declared inside looper instead of being passed.

When you do memset, use sizeof the array instead of some number

e.g.

memset(engWord, 0, sizeof(engWord)); 

that way you will be sure it always works even if you change the size of engWord one day.

using meaningful variable names and functions would be better, looper is not very descriptive.

To use boolean include instead stdbool.h

• Jon: ' if (count != amt) { if (looper(amt, count+1) == 0) continue; }' The count is an argument that is sent in the recursive call to looper(it is also incremented by 1). I think if I declared it inside of looper, it would be set to 0, each time that the function is run.
• Jon: Thank you for your other improvements, I've implemented them now :) If I include a library, but only use one function from that library, will that mean I could make the program faster if I used something like stdbool in lieu of CS50 (a library with lots of functions). I would think not, but would it affect performance at all?